Tag Archives: recreational mathematics

Automorphic Numbers

In this post we discuss automorphic numbers. Note that all numbers involved in this post are non negative integers.

Definition: Let x have n digits in its base 10 representation. Then x is said to be automorphic if x^2\equiv x\pmod {10^n}.

In our base 10 representation this means that the last n digits of x^2 are precisely x. In other words, the digits of x are appended to x^2. Note that since the digits of x are appended to x^2 they are also appended to x^m for any m\ge 1.

A list of some automorphic numbers can be found here. Our aim here is to characterize all such numbers in base 10.

Theorem: The automorphic numbers in base 10 are given by \{0,1\}\cup\{5^{2^m}\pmod {10^m}:m\ge 1\}\cup\{16^{5^m}\pmod {10^m}:m\ge 1\}.

Proof: Suppose x is an automorphic number of n digits. Then,

x(x-1)\equiv 0\pmod {10^n}

which is equivalent to

\Big(x\equiv 0\text{ or }1\pmod{2^n}\Big) \text{ and } \Big(x\equiv 0\text{ or }1\pmod{5^n}\Big)

which is equivalent to the occurrence of exactly one of the following:

Case 1: x\equiv 0\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}

Case 2: x\equiv 1\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}

Case 3: x\equiv 1\pmod {2^n} \text{ and } x\equiv 0\pmod {5^n}

Case 4: x\equiv 0\pmod {2^n} \text{ and } x\equiv 1\pmod {5^n}

Now we consider all these cases one by one. Case 1 is equivalent to x\equiv 0\pmod {10^n}. Since x had n digits so this means x=0. Similarly x=1 in case 2.

Now suppose case 3 holds. By the Chinese Remainder theorem there exists a unique solution to these two congruences modulo 10^n. We show that 5^{2^n} is a solution to them. By uniqueness it will then follow that case 3 is equivalent to saying that x\equiv 5^{2^n}\pmod {10^n}. Since x has n digits and 5^{2^n}\pmod {10^n} has at most n digits so we will therefore have x equal to 5^{2^n}\pmod {10^n}. Hence x\in\{5^{2^m}\pmod {10^m}:m\ge 1\}.

We first show that 5^{2^n}\equiv 1\pmod {2^n}. Proceed by induction on n. For n=1 note that 5^{2}\equiv 1\pmod 2.

Now assume the result for k. Then 5^{2^k}=q2^k+1 and squaring yields 5^{2^{k+1}}=q^2 2^{2k}+q2^{k+1}+1=(q^2 2^{k-1}+q)2^{k+1}+1 and so 5^{2^{k+1}}\equiv 1\pmod {2^{k+1}} thereby completing the induction step. Next observe that as n<2^n so 5^{2^n}\equiv 0\pmod {5^n} follows immediately, thereby completing case 3.

Note that our argument also implies that any number of the form 5^{2^m}\pmod{10^m} is automorphic. Indeed, if a=5^{2^m}\pmod{10^m} had t\le m digits then we have shown that a^2\equiv a\pmod {10^m}. Now as 10^t divides 10^m so a^2\equiv a\pmod {10^t}, i.e. a is automorphic.

To finish the proof we now consider case 4. We show that 16^{5^n} is a solution to the congruences of case 4. Clearly 16^{5^n}\equiv 0\pmod {2^n} as n<4.5^n. To show 16^{5^n}\equiv 1\pmod {5^n} we proceed by induction as before. The base case may be explicitly worked out or be shown to hold by invoking Fermat’s theorem: m^p\equiv m\pmod p, for any prime p and integer m. Next assume the result for k, so that 16^{5^k}=q5^k+1. Raising both sides to the fifth power yields the result for k+1. The rest of the argument is similar.\Box

Advertisements

Leave a comment

Filed under Miscellaneous, Number theory, Recreational Mathematics

A ball game and Konig’s lemma

In this post we will examine an application of Konig’s lemma to investigate a game proposed by Raymond Smullyan.

Imagine there is an unlimited supply of balls with us, with positive integers painted on each. It is very much possible that a particular positive integer is repeated many times on various balls. We do not know anything else about the distribution of numbers on the balls. Further imagine that there is a box with a ball initially within it.

To play the game we may do either of two things:

(1) We may remove a ball from the box and replace it with any finite number of balls, arbitrarily chosen, but constrained to have numbers painted on them which are less then the number of the ball removed. For example, if we have a number 1000 ball we may remove it and replace it by 6000 balls: 3000 balls on which 657 is painted, and 3000 balls on which 999 is painted.

(2) We may remove a ball from the box and not do any replacement.

After playing the game once we can continue playing provided there are balls left in the box.

The question is: Is it possible to play the ball game indefinitely? Can we ensure that the box will never be empty?

Smullyan himself answered this problem in the negative by using Konig’s lemma.

Theorem: The Smullyan game terminates after a finite number of steps.

Proof: For any play of the Smullyan game define a (rooted) tree as follows:
1. The vertices are the painted balls used during the game.
2. The root is the painted ball intially within the box.
3. The edges are given by the following criteria: There is an edge between the vertices x and y iff during some move of the game, the ball y is among the balls which replaces the ball x (or vice-versa).

By the definition of the game this is a rooted tree where each level is finite. Can there be an infinite path in the tree? No there can’t. This is because, by definition an infinite path would correspond to a infinite strictly decreasing sequence of positive integers which is absurd. By the contrapositive form of Konig’s lemma we can therefore conclude that the tree is finite. In other words only finitely many balls were used and so the game terminated after finitely many steps.

An alternate proof without using Konig’s lemma is available here.

Leave a comment

Filed under Game Theory, Graph theory, Miscellaneous

Mathematics and brainvita

In this post, I will analyse the single player game brainvita (also known as peg solitaire). The game is described by having a board with holes having the pattern:

Initially all holes except the central one are filled with pegs. The player may jump a peg horizontally or vertically over another peg into an empty hole. The jumped peg is then removed by the player. The objective is to finish the game with just one peg left.

The aim of this post is to show that there are (at most) 5 ending board positions in brainvita. In other words, assuming the player wins, his last peg left on the board can be only among 5 fixed board positions.

The proof uses abstract algebra. Suppose that the pegs correspond to coordinates in the plane in the natural fashion described below: The central peg is at (0,0), and all others have integer coordinates as well. For convenience adjacent pegs may be taken a unit distance apart. Some coordinates are described below:

Now consider all possible ways of placing pegs on the board. There are 2^{33} of them. Many of these ways are impossible to reach in a valid game. Regardless of this fact, let W be the set of all possible ways and for a given w\in W, let C_w denote the set of all the coordinates where there is a peg in w. Now define a function f:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} by f(w)=\sum_{(m,n)\in C_w}x^{m+n} where \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} is the finite field on 4 elements. (If there are no pegs on the board we define f to be 0.)

The function f has the property that for any given way w of placing pegs on the board, if a legal move is performed to yield another way w' then f(w)=f(w'). To see this, suppose that in the way w there were pegs at (m,n) and (m+1,n) positions and the hole at the (m+2,n) position was empty. A legal move may be performed by jumping the (m,n) peg over the (m+1,n) peg to yield a way w' where the holes at (m,n) and (m+1,n) are empty and there is a peg at (m+2,n). Clearly the only change between f(w) and f(w') occurs on account of these three coordinates and f(w)-f(w')=x^{m+n}+x^{m+1+n}-x^{m+2+n}. But as x^{m+n}+x^{m+1+n}-x^{m+2+n}=x^{m+n}(1+x-x^2)=x^{m+n}.0=0 in \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} so f(w)-f(w')=0 following which f(w)=f(w'). The same holds if instead of moving a peg to the right we had moved it above, below or to the left. Moreover all this is regardless of the fact whether the way w can actually be reached by a valid sequence of moves in the game.

Now we define another function g:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)} by g(w)=\sum_{(m,n)\in C_w}x^{m-n} (the no pegs way means g is 0) and by a similar piece of reasoning conclude that g also has the same property enjoyed by f. It is also easy to observe that both f and g are onto functions and so f(W)\times g(W) has 16 elements.

Next we partition the set W as follows. Any w\in W corresponds with a pair (f(w),g(w)) and so with exactly one among the 16 elements of f(W)\times g(W). In this way all the 2^{33} elements of W are partitioned in 16 parts. Further each part has the curious property that for any w in that part, any sequence of legal moves will never change the value of (f(w),g(w)) and so the resultant w' will also be in the same part. It is now obvious that among these 16 parts one and only part consists of all the w's which can actually occur in a game of brainvita. All other w's correspond to ways which can never occur in a legal game.

What is the value of (f(w),g(w)) that this one special part corresponds to? The initial board (assuming it corresponds with i\in W) is set up so that f(i)=g(i)=1. So any way w that arises during the game also has f(w)=g(w)=1. Assume now that the game has been successfully finished with a single peg at (m,n), and that this corresponds to the way w^*. We therefore have f(w^*)=g(w^*)=1. But by definition f(w^*)=x^{m+n} and g(w^*)=x^{m-n}. So we must have x^{m+n}=1. Since the multiplicative group \{1,x,x^2\} is cyclic of order 3 so as a consequence of Lagrange’s theorem we must have 3|(m+n). Similarly we have 3|(m-n). Combining these facts together we have 3 dividing both m and n. The only five coordinates which satisfy this condition are (-3,0),(0,-3),(3,0),(0,3) and (0,0). So the player has to end up at one among these 5 positions. This completes the proof.

It should be noted that we have only found an upper bound on the number of positions the final peg can end up at. However by explicitly giving a sequence of moves for each of these 5 coordinates it is possible to show that all these endings are indeed possible.

1 Comment

Filed under Algebra, Game Theory