Sieves And Wythoff’s Nim

In math, a sieve is used to divide the integers in two piles, the good ones and the bad ones. The oldest example is the Sieve of Eratosthenes, used to find the list of prime numbers: We start with the list 2, 3, 4, 5, 6,… of all integers greater than one. The first element in the list is declared good, and all multiples are declared bad. This leaves us with the list 3,5,7,9,11,13,15,17,… of all odd numbers greater than one. Again the first element in the list is declared good, and all multiples are declared bad, leaving us with 5, 7, 11, 13, 17, 19, … If we keep going like this, the good numbers become the list of all prime numbers.

Wythoff 3

A much simpler sieve proceeds as follows. We start with all positive integers. In step n, we declare the first element (say a) as good, and the element a+n as bad. So in step 1, 1 is good, 2 =1+1 is bad, and we are left with the list 3, 4, 5, 6….. In the second step, 3 becomes good while 5=3+2 goes bad, leaving us with 4, 6, 7, 8, 9, …. In the third step 4 becomes good and 7=4+3 goes bad, etc.

This separates the positive integers into the sequence a(n)=1, 3, 4, 6, 8, 9, 11, 12, 14, 16, … of good integers and the sequence b(n)=2, 5, 7, 10, 13, 15, 18, 20, 23, 26, … of bad integers.

 

Wythoff 4

Miraculously, there is a simple formula for these sequences. We have a(n)=[n 𝜑] and b(n)=[n (𝜑+1)], where [x] denotes the largest integer less than or equal to x, and 𝜑 = (1+√5)/2 is the Golden Ratio. Sequences of the form [n 𝛂] are called Beatty sequences, and Raleigh’s miraculous theorem states that [n 𝛂] and [n 𝛃] are complementary if and only if 1/𝛂+1/𝛃=1. Even more miraculous is that Raleigh’s theorem isn’t so difficult to prove, but this has to wait here until I find a picture proof of it. Given all this, it is not difficult to see that the good and evil sequences are indeed the Beatty sequences as claimed.

Wywin 1 01

But there is more, these sequences are also relevant for a Nim-variant called Wythoff’s game. This is played with two heaps of tokens, and the two players take turns taking an arbitrary amount of tokens from either pile, or the same amount of tokens from both piles. The game ends with the winner making the last move.

Wywin 2 01

If we label a position of two piles of size a and b as a point (a,b) in the first quadrant, the top picture shows all legal moves from the purple position as green positions.

The second picture shows a sample game, ending with orange losing, because they are out of moves.

Wythoff 1

How do we find a strategy? We mark (third image) all positions where the first player can win as green. The unmarked positions closest to the point (0,0) are then certain losing positions, because the first player has to move from them to green. We mark these two as orange, and again all positions from where those can be reached as green (fourth image).

Wythoff 2

This process of separating positions in winners and losers is just the sieve we used to create the a(n) and b(n) sequences — in fact, the positions (0,0), (a(n), b(n)) and (b(n), a(n)) are exactly the losing positions for Wythoff Nim. You can use the last image to contemplate this. If you are above the orange or below the cyan line on a white position, you can win by moving down or left to an orange or cyan position, because the two Beatty sequences are complementary. If you are between the two lines, you can move diagonally down-left to an orange or cyan position, because the differences b(n)-a(n)=n exhaust all integers. 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s