MATHS BITE: Brouwer Fixed Point Theorem

The Brouwer Fixed Point Theorem is a result in topology that has proven to be extremely useful in mathematics.

2D

Suppose you take two sheets of paper with one lying directly above the other. If you crumple the top sheet and place it on top of the other sheet, then Brouwer’s theorem states that there is at least one point that has not moved, i.e. there is at least one point on the top sheet that is directly above the corresponding point on the bottom sheet.

3D

Take a cup of coffee, and mix it around. The theorem states that after mixing there must be some point in the coffee, which is in the exact spot that it was before the mixing. Furthermore, if you try to move that point out of its original position then you will inevitably move another point into its original position.

Formally

A continuous function from an n-ball into an n-ball must have a fixed point. Note that continuity of the function is essential.

Click here for the proof.

 

Advertisements

MATHS BITE: Stars and Bars

A common problem in combinatorics is when we are asked to count the number of ways to group identical objects, such as placing indistinguishable balls into labelled urns. Popularised by William Feller in his book on probability, the Stars and Bars methods aims to solve such problems.

Theorem

The number of ways to put n indistinguishable balls into k labelled urns is

Related image

Proof using Stars and Bars:

Represent n balls by n adjacent stars and consider inserting k – 1 bars between the starts to separate them into k groups.

For example, for n = 12 and k = 5 the following is a possible arrangement:

**|****||***|***

Here, urns 1, 2, 3, 4 and 5 are of size 2, 4, 0, 3 and 3 respectively.

There are a total of n + k – 1 positions, of which n are stars and k – 1  are bars. So, the number of ways to place n indistinguishable balls into k labeled urns in the same as the number of ways of choosing n positions (or k – 1 positions) amount n + k – 1 spaces, with all the remaining positions taken as bars (stars), i.e.

Related image

ways.

M x

MATHS BITE: Sierpinski Number

A Sierpinski number is an odd natural number k such that {\displaystyle k\times 2^{n}+1} is not prime for all natural numbers n. In 1960, Sierpinski proved that there are infinitely many odd integers k with this property, but failed to give an example. Numbers in such a set with odd k and k < 2^n are called Proth numbers.

78557, 271129, 271577, 322523, 327739, 482719, 575041, 603713, 903983, 934909,….

-List of some known Sierpinski Numbers

Sierpinski Problem

The Sierpinski problem asks what the smallest Sierpinski number is. In 1967, Sierpinski and Selfridge conjectured that 78557 is the smallest Sierpinski number. To show this is true, we need to show that all the odd numbers smaller than 78557 are not Sierpinski numbers, i.e. for every odd k below 78557 there is a positive interger n such that {\displaystyle k\times 2^{n}+1} is prime. There are only five numbers which have not been eliminated:

k = 21181, 22699, 24737, 55459, and 67607

Numberphile Video

Find out more here. M x

MATHS BITE: 6174

6174 is known as Kaprekar’s Constant. Why is this number important? Perform the following process (called Kaprekar’s Routine):

  1. Take any two digit number whose digits are not all identical.
  2. Arrange the digits in descending and then ascending order to get two four digit numbers.
  3. Subtract the smaller number from the bigger number.
  4. Go to step 2 and repeat.

This process will always reach its fixed point 6174 in at most 7 iterations. 6174 is a fixed point as once it has been reached, the process will continue yielding 7641 – 1467 = 6174.

Example: 3141

4311-1134=3177
7731-1377=6354
6543-3456=3087
8730-0378=8352
8532-2358=6174
7641-1467=6174

The Maths Behind it

Each number in the sequence uniquely determines the next number. As there are only finitely many possibilities, eventually the sequence must return to a number it has already hit. This leads to a cycle.

So any starting number will give a sequence that eventually cycles.

There can be many cycles, but for 4 digit numbers in base 10, there happens to be 1 non – trivial cycle, which involves the number 6174.

To read more, click here.

Numberphile Video

 

Click here for my previous post about Kaprekar. M x

MATHS BITE: Wythoff’s Game

Wythoff’s game is a two-player mathematical strategy game. It is played with two piles of counters and goes as follows:

Players take turns to remove counters from one, or both piles (if they are removing stones from both piles, they must remove the same number of stones from each). The game ends when one person removes the last counter, or counters, thus winning.

It is name Wythoff’s game, as it was Dutch mathematician W. A. Wythoff that published a mathematical analysis of the game in 1907, although it was previously know in China as tsyan-shidzi (“choosing stones”).

Optimal Strategy?

Any position of the game can be described by a pair of integers (x,y) where x≤y. This describes the size of both piles in the position.

The strategy of the game involves cold and hot positions:

  • A cold position is one where the player whose turn it is to move will lose, even with his best move;
  • A hot position is one where the player whose turn it is to move will win with his best move.

Thus, the optimal strategy for a person in a hot position is to move to a cold position.

We can classify the positions as hot or cold recursively, using 3 simple rules:

  1. (0,0) is a cold position;
  2. Any position from which a cold position can be reached in a single move is a hot position;
  3. If every move leads to a hot position then the position is cold.

For example (taken from Wikipedia):

“all positions of the form (0, y) and (y, y) with y > 0 are hot, by rule 2. However, the position (1,2) is cold, because the only positions that can be reached from it, (0,1), (0,2), and (1,1), are all hot. The cold positions (x, y) with the smallest values of x and y are (0, 0), (1, 2), (3, 5), (4, 7),(6,10) and (8, 13).”

Connection with the Golden Ratio

Wythoff discovered that the cold positions can be determined using the Golden Ratio. Namely, if n is any natural number, then

Screen Shot 2017-11-05 at 5.54.53 PM.png

is a cold position (where we use the floor function and φ is the Golden Ratio).

To read more, click here.

M x

MATHS BITE: Kaprekar Numbers

Consider an n-digit number k. Square it, and then add the right n digits to the left n or n-1 digits (by convention, the second part may start with the digit 0, but must be nonzero). If the result is k then it is called a Kaprekar number. They are named after D. R. Kaprekar, a recreational mathematician from India.

We can extend the definition to any base b:

Let  X  be a non-negative integer and  n a positive integer.  X  is an n-Kaprekar number for base  b  if there exist non-negative integer A, and positive integer B  satisfying:

X2 = Abn + B, where 0 < B < bn
X = A + B

-Wikipedia

Examples in Base 10

  • 297: 2972 = 88209, which can be split into 88 and 209, and 88 + 209 = 297.

  • 999: 9992 = 998001, which can be split into 998 and 001, and 998 + 001 = 999.
  • In particular, 9, 99, 999… are all Kaprekar numbers.
  • More generally, for any base b, there exist infinitely many Kaprekar numbers, including all numbers of the form bn − 1.
  • 100: 100 is NOT a Kaprekar number as, although 1002 = 10000 and 100 + 00 = 100, the second part here is zero.

    M x

    (P.S. Another post on Kaprekar is coming soon!)

MATHS BITE: Even or Odd?

What are even and odd functions? These two terms get used very frequently in order to simplify problems such as integration or when finding Fourier coefficients, for example.

Even Function

An even function is such that for all x in the domain

f(x) = f(-x)

An even function is symmetric with respect to the y-axis.

Screen Shot 2017-10-11 at 5.20.23 PM
Even Function | mathsisfun

Examples:

  • Any polynomial p, where n is even for all xn. For example f(x) = x2+2x4 – 6. Note that (x+1)2 is not even.
  • f(x) = cos(x)

Screen Shot 2017-10-11 at 5.24.53 PM.png

Odd Function

An odd function is such that for all x in the domain

f(x) = -f(-x)

An odd function is symmetric with respect to the origin.

Screen Shot 2017-10-11 at 5.20.18 PM
Odd Function | mathsisfun

Examples:

  • x, x3, x5,… etc. Note that unlike even functions, an expression such as x3 + 1 is not odd.
  • f(x) = sin(x)

Screen Shot 2017-10-11 at 5.30.14 PM.png

Odd and/or Even?

A function can be neither odd nor even, for example x− x + 1:

Screen Shot 2017-10-11 at 5.31.18 PM.png
Neither odd nor even | mathsisfun

Additionally, the only function that is even and odd is f(x) = 0.

Properties:

  • Adding two even (odd) functions will give an even (odd) function.
  • Adding an even and an odd function will give a function that is neither odd nor even.
  • Both the product of two even functions and the product of two odd functions is even.
  • The product of an even function and an odd function is odd.