|
|
|
Let's play a game. I'll be the computer, and you be the human, OK? I'll hand you a slip of paper on which will be printed two numbers -- all numbers are nonnegative integers. Then you can reduce one or both of the two numbers by any positive integer amount, but you can't make either number negative, and then you can hand me back the slip of paper. We take turns reducing one or both of the numbers until one of us reduces both numbers to 0, winning the game.
What is a good strategy for winning the game?
Would you like to play the game while you think some more about it?
Source: Wythoff's Game
As in the game of nim, there are "safe leaves". A "safe leave" is a board position in which you can end your turn safely. The characteristics of a safe leave are (1) that the opponent can't turn it into another safe leave, so he's required to end his turn with an unsafe leave -- unsafe for him, that is -- and (2) any unsafe leave can be turned into a safe leave with some valid move.
Obviously 0,0 is a safe leave. That's the move that wins you the game, so there's nothing safer than that! Searching for the next larger safe leave, I reasoned that it can't have 0 as one of its two elements, and its two elements can't be the same. That is, the smallest element must be larger than 0, and the difference between the elements must be larger than 0 as well. The smallest pair that satisfies those conditions is 2,1, a safe leave because my opponent can't turn it into a safe leave for him, but any move on his part can be turned into a safe leave by me. (WLOG I'll list the larger number first.)
The next larger safe leave can't contain 0, 1, or 2, because then my opponent could turn it into a safe leave for him. Also, the difference between the elements must be larger than that of any smaller safe leave, or else my opponent could subtract the same number from both elements to make a safe leave for him. So the smaller element must be 3 and the difference between the elements must be bigger than 1. That makes 5,3.
Now I'm thinking Fibonacci. 
Each successive safe leave has the property that its smallest element is the smallest number that isn't an element of a smaller safe leave, and the difference between the elements is one larger than the differences of all previous safe leaves. To prove that each of the pairs generated this way is a safe leave, you need only observe that (1) there is no way for the opponent to turn it into a safe leave, because there is no smaller safe leave with either the same difference between elements or having one of the elements, and (2) whatever the opponent does, he must either reduce the difference or reduce the smaller element. Either way, his result can be turned into a safe move for me, because all smaller differences, and all smaller smaller-elements are represented by previous safe leaves.
This proves that an,bn are safe leaves when they satisfy the recurrence relations a0=b0=0 and bn isn't equal to any ak or bk for any k<n, and an=bn+n.
The additional factoid that an=floor(nφ2) and bn=floor(nφ), where φ is the Golden Ratio, (sqrt(5)+1)/2, is perhaps the thing you want to prove. The easy part is that an-bn=n, of course, because it follows from φ2-φ=1. The hard part is showing that (1) no element (other than 0) of either sequence is contained in the other, and (2) every integer is in either an or bn.
That part of the proof comes from the world of Beatty Sequences. If a and b are positive irrational numbers and 1/a + 1/b = 1, then the Beatty sequences A = floor(a), floor(2a), floor(3a), ... and B = floor(b), floor(2b), floor(3b), ... together contain all the positive integers without repetition.
Proof: suppose integers n and m exist such that floor(na)=floor(mb). Let k=floor(na)=floor(mb). Then,
k < na < k+1 and k < mb < k+1.
(The inequality is strict because na and mb are irrational and so not integers.) Taking reciprocals,
1/k > 1/(na) > 1/(k+1)
and
1/k > 1/(mb) > 1/(k+1).
Multiplying the first equation by n and the second by m,
n/k > 1/a > n/(k+1)
and
m/k > 1/b > m/(k+1).
Now, adding them together, taking reciprocals, and multiplying through by n+m,
(n+m)/k > 1 > (n+m)/(k+1)
k/(n+m) < 1 < (k+1)/(n+m)
k < n+m < k+1
But there is no integer between k and k+1, a contradiction, showing that no positive integer is in both set A and set B.
To show that every positive integer is in set A or set B, consider the total number of elements of A and B that are smaller than N. Let n=floor(N/a), and let m=floor(N/b). Then the n elements of A smaller than N are floor(a), floor(2a), ..., floor(na); and the m elements of B smaller than N are floor(b), floor(2b), ..., floor(mb), so altogether, there are n+m elements of the union of A and B smaller than N.
n < N/a < n + 1
m < N/b < m + 1
Adding these inequalities together,
n+m < N < n+m+2
There's only one integer between n+m and n+m+2, so n+m=N-1, proving that the number of elements of the union of A and B that are smaller than N is N-1, and so every positive integer must be in one of those sets.
The sequence an,bn, of safe leaves, begins as follows:
n an bn 0 0 0 1 2 1 2 5 3 3 7 4 4 10 6 5 13 8 6 15 9 7 18 11 8 20 12 9 23 14 10 26 16 11 28 17 12 31 19 13 34 21 14 36 22 15 39 24 16 41 25 17 44 27 18 47 29 19 49 30 20 52 32 21 54 33 22 57 35 23 60 37 24 62 38 25 65 40 26 68 42 27 70 43 28 73 45 29 75 46 30 78 48 31 81 50 32 83 51 33 86 53 34 89 55 35 91 56 36 94 58 37 96 59 38 99 61
This list will help you whenever you feel the urge to play Wythoff's Game.
Mathworld: Nim
Mathworld: Wythoff's Game
Mathworld: Beatty Sequences are complementary when the reciprocals of their bases sum to one.
Cut-the-knot: Nim
Arkansas State University: Nim ( www.csm.astate.edu/Nim.html )
OEIS: A001950 and A000201 are the sequences I call an and bn.
Consecutive Integer Products has some proofs using the "floor" function.
The webmaster and author of this Math Help site is Graeme McRae.