Category: Games

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. 

Chomp (The Esthetics of Not Knowing)

Mathematics has a few peculiarities (inherited by their owners, the mathematicians) that irritate the uninitiated. One of them is the non-constructive aspect of many of its statements. A delicious example is the game Chomp, played with a chocolate bar. Traditionally, the top left piece is poisoned. Two players take turns selecting a piece, breaking it off together with the rectangular chunk of the pieces that are to the right or below of that piece, and instantly eating all of it. Here is an example sequence of turns. The lighter brown indicates which pieces the player is about to eat. We see that here Two has the last bite. Let’s not talk about it.Chomp 1 01

As with each move the number of uneaten chocolate pieces decreases, the game necessarily ends, and there is no draw. Mathematicians conclude from this that either One or Two has a winning strategy, i.e. a way of choosing chocolate pieces so that they win (survive), no matter what the other is doing. In Chomp, the situation is more surprising: One can always win, no matter how large the chocolate bar, but we are generally clueless how One can accomplish this. This is done by an argument that is called strategy stealing, and uses a perplexing indirect proof. So let’s assume, by contradiction, that Two has a winning strategy.

Chomp 2 01

One steals this strategy as follows: One takes the bottom right piece, and sees what Two is doing. Two will make a winning move, removing another piece and everything below and to the right. But One could have done the exact same thing, reaching the same position in the first place (as the bottom right piece will disappear with that move as well). But the nagging question remains unanswered: How does One win? What is the winning move? This happens to be a very difficult question. We not only have to consider the whole, intact chocolate bar, but also the ones that arise while chomping, and we can (very plausibly) even allow bars where some of the chocolate pieces have already been eaten (by someone) before the game even starts. For instance, below are all 132 fragmentary chocolate bars that fit in a 2×6 box where the moving player will lose, assuming the other player has their wits together.

2x6

Out of decency I have removed the poisoned piece in the top left corner, the game now simply ends when one player has no move left, meaning they lose, but keep at least their life. Below are the 182 losing positions that fit in a 3×4 box.

3x4

This is incomprehensible determinism made visible. There are patterns, though. If one encodes all possible positions that fit in a 2×10 box by a pair of binary numbers and plots the losing positions as dots in a 1024×1024 square, one gets the following:

Losers10b

Some of the patterns (like the emerging periodicity) have been partially understood, and I’ll write about that later, time and comprehension permitting.

Euclid’s Game

One of the most fundamental algorithms in mathematics is the Euclidean Algorithm to compute (among other things) the greatest common divisor of two numbers. 

Euclid’s Game is a two person strategy game, invented by Cole and Davie in 1969, employing this algorithm, and, maybe not surprisingly, connected to the Golden Ratio. It is played with a pair of positive integers, like (11,27). A move consists of taking away from one number a non-zero multiple of the other number, so that the result is still non-negative.

 

So from (11,27), we can move to either (11,16) or to (11,5).
The players take turns until one number becomes zero, so that the other player is out of moves and has lost.

Here is a complete sample game:

(11,27)➔(11,5)➔(1,5)➔(1,3)➔(1,0)

Below is a way to visualize the possible moves by placing a blue pair (a,b) in a coordinate grid. If a<b, the possible yellow moves are obtained by decreasing the x-coordinate by a, until we get below the x-axis.

Euclid2 moves

We would like to find out when the first player has a winning strategy.

Here is a simple case: If one number is a multiple of the other, the first player can reduce the larger number to 0 and win in a single move. In particular, all pairs (a,a) are a win for the first player. By symmetry, we can from now on restrict our attention to the case that a<b.

How many different moves are possible for the pair (a,b)? We can list the moves (using the floor notation [x] for the largest integer less than or equal to x) as

(a,b-a), (a,b-2a), … , (a,b-[b/a] a),

so there are [b/a] possible moves. You can check this in the diagram above, too.

In many games, it is a good strategy to force the other player’s moves, and this turns out to be the case here as well. The first player should try to reach a pair (a’,b’) with 1< b’/ a’ <2, so that the second player has only one move left.

We will now prove:

Theorem: The first player has a winning strategy if and only if b/a is an integer, or b/a>𝜑, where 𝜑=(√5+1/2) ≈ 1.6180<2 is the Golden Ratio.
In the first case, the player wins by making the larger number 0, in the second case by moving to a position (a’,b’) where 1<b’/a'<2.

Below is a diagram showing all winning pairs (a,b) for the first player with a,b<30 in green. 

Euclid2 30

We first pin down the role of the Golden Ratio.

Lemma: If 1<b/a<𝜑, there is only one move from (a,b), namely to (a’,b’)=(b-a,a), and we have b’/a’>𝜑.

Proof:
We have

Frac a b = frac
so that

Frac b a > fra
In other words, if we can move the other player into the region 1<b/a<𝜑, they are forced to move us back into the claimed winning region b’/a’ >𝜑.

The next lemma tells us when that is possible:

Lemma: Let k be a positive integer.
If k<𝜑+k-1<b/a<k+1, we can move to (a’,b’) = (b-k a, a), and this pair satisfies 1<b’/a'<𝜑. In other words, we subtract the largest amount we are allowed to.

Proof:
We have
Phi 1< frac a b
Taking reciprocals proves the claim.

We will now take care of the remaining possible ratios. Here, we take away one times less than would be allowed:

Lemma: Let k be a positive integer.
If k+1<b/a<𝜑+k, we can move to (a’,b’) = (a, b-k a). From there, only one move is possible, namely to (a”,b”) = (b-(k+1)a, a), and this pair satisfies b”/a”>𝜑.

Proof:
That the chosen move to (a, b-k a) is valid is clear, because the assumptions imply that a<b-ka. Moreover,

Frac b a = fra 1
so there is only one move possible, namely to (a”,b”) = (b-(k+1)a, a). Now we have

Frac a b = f
which proves that a”<b” and that b”/a”>𝜑.

The proof of the theorem now follows by combining the three lemmas.

Euclid3 20b

Life gets more complicated in three dimensions. One can play this game also with triples, allowing to subtract multiples of one number from either of the other two. Above is the set of winning triples in the first octant, marked with small green dots, while the losing positions are big and red. One can see they form a tetrahedral cone, but the cone is not solid, meaning that it probably won’t be as easy to find a simple winning strategy. As an impartial game, Euclid is equivalent to the game of of Nim in any dimension, it’s just not so clear, what the size of the Nim pile is.

Grow, Contact, and Trinity (Cooperation Games VII)

Let’s bring back a bit of color. Today we get a trio of games, played with similar cards and similar mechanics. The simplest version I call Grow, and it’s a game for two players One and Two, to be played with triangular cards on a triangular board. The pieces are called (top to bottom) root, branch, and twig.

Triangle pieces 01

We will need a single root-piece, 12 twigs for player One, and 12 branches for player Two. We begin by placing the root somewhere on the triangular board. Then we take turns by adding twigs and branches so that adjacent edges match and we have a connected growing tree.

Rules 01

There are two more rules: We don’t allow loops, and the branches must branch away from the root. The layout above on the left is still correct, but in the middle we illegally have closed a loop, and on the right we closed a loop and are also branching in the wrong direction.Triangle game 01

Above are two solutions. The players need to collaborate in order to fill the entire board. Can we find a solution for every position of the root-tile? Can we solve this on a triangle with edge length 7 instead of 5?

Contact pieces 01

Contact uses tiles with two colors, and adds leaf tiles. We begin by placing two socially distanced roots, one of each color, inside a regular hexagon of edge length 6, like so, for instance. 

Contact start 01

Again this game is played with two players, Orange and Green, but this time a player controls all pieces of the same color. There is only one root tile of each color, and sufficiently many leaves, twigs, and branches. The goal is to tile the entire hexagon by taking turns, so that all twigs and branches end in leaves, as shown below. Note in particular that no loose ends of twigs or branches are allowed on the boundary of the hexagon.

Contact game 01

However, this solution has a flaw: We have used 27 orange and only 20 green tiles. Can we do it with the same number of tiles for Orange and Green?

Trinity pieces 01

Finally, Trinity is played with pieces in three colors, and two chiral leaf tiles. Again, each of the three players controls one color. This time, multiple roots are allowed, but watch out that different trees of the same color don’t grow together.

At the beginning, each player places one root tile on the board, again socially distanced. Then we take turns either growing our own tree, placing a leaf tile that fits at least our own tree, or placing a root for a new tree. Below are two solutions on a hexagon of edge length 6. Enjoy.

Trinity game 01

Ninety-Six (Collaboration Games VI)

Today Alan Schoen is celebrating his 96th birthday (below you can see him at the youthful age of 93), 

Schoen 2017

and this gives me the opportunity to congratulate him with a puzzle. Its mechanics is motivated by the genus 3 Riemann surface which is the double cover branched over the vertices of a cube, the Riemann surface that underlies the Schwarz P surface, the Diamond surface, and Alan’s Gyroid, his best known discovery. Not quite incidentally, this surface has 96 symmetries. Today’s puzzle is also motivated by Alan’s puzzle RotoTiler.

P1 01

Above is the first version of the puzzle, consisting of 12 squares. You are allowed to put two of them next to each other if the adjacent edges have the same color and the same orientation of arrows, but opposite shading. It is also prohibited to place two tiles next to each other that use the same pair of edge colors. All that is forbidden is shown below (wrong edge colors, wrong edge direction, wrong shading, same edge pairs).

P4 01

It’s not that hard to lay out all 12 squares in a single connected way. You will notice that it is impossible to place four squares around a single vertex.

P3 01

As a simple puzzle: The above layout fits in a 4×7 rectangle. Can you find a solution that fits into a smaller rectangle?

And, if you have a partner to play: print say 8 sets of the tiles so that you have 96. One player gets all the dark squares, the other the light squares, and you take turns creating a connected layout of all tiles. It is quite easy to get stuck, so the players have to collaborate.

P2 01

The two crosses above give a hint how this is related to cubes. They can each be wrapped around a cube, one from the inside, the other from the outside, so that the two tiles on each face differ only in shading.

R 1 01

Next we have a rhombic version of the same puzzle, now with 24 different tiles. This more truthfully can be used to represent a walk on the Schwarz P-surface. We have one additional rule: 60º vertices are not allowed to meet with 120º vertices. All that’s forbidden is listed below:

R 2 01

Below are a few partial layouts. None of them can be extended.

R 3 01

Can you lay out all 24 tiles in a single, connected figure? That you can’t has to do with the Schwarz P surface having congruent insides and outsides, and it being impossible to reach the inside from the outside.

R 4 01

More down to earth is the following explanation: You can lay out all 24 tiles in the two rings above, but no tile from the left ring can be legally placed next to a tile from the right ring. To remedy this, we can relax the rules a bit. If we allow that two tiles that use the same pair of colored edges can be placed next to each other, a single chain can be found:

R 5 01

This was not so easy. Can you find smaller displays? And again, you can play with two player, using four sets of tiles, and take turns trying to complete a single layout.

 

Happy Birthday, Alan!

 

 

Binomino (Cooperation Games V)

Here is yet another domino variation. Below are the eight 3-binominoes:

Binominoes 3 01

You place them sideways so that colors of adjacent squares match. This is, alas, impossible, unless you use two identical binominoes. Therefore we are generous and allow the binominoes to be shifted up or down by one square, so that they have contact only along two squares. A chain using all eight might look like this:Rules 01

The connectivity graph is surprisingly complicated. I have drawn the directed version, the target of an edge connects to the source by sliding it down one square.

Graph 3 01

A simple game for two players divides the eight binominoes in two sets of four. Each player gets one set, and they take turns placing binominoes in a chain so they match along two squares. If a player can’t play (either because their binominoes don’t fit, or because they are out of them), they have to take one from either end of the chain. The goal is for both players to finish simultaneously.Binominoes 01

Above is a circular version with 4-binominoes, ragged so that not only the colors have to match, but the notches as well. I hope this looks appealing. The same rules apply, but now the goal is to create a closed chain, like so:

Wheel4 01

Here this is even done so that the binominoes are always shifted the same way. In other words, this solution represents a Hamiltonian cycle in the directed connectivity graph. I believe this graph is always Hamiltonian, for n-binominoes with arbitrary n.

 

In Chains (Cooperation Games IV)

We continue with translucent trominoes, add an I-tromino, and select those that have two translucent squares (gray with red border). There are just three of them, shown below to the left. To the right are how they can be attached to each other, overlapping in exactly one translucent square:

Linkages 01

What we don’t allow today is that two trominoes overlap in both of their translucent squares, as below.

Nono 01

This has the interesting consequence that the gray squares will necessarily form chains or loops, which adds useful structure. A tiling is complete if all translucent squares are covered twice. We will then have twice as many translucent squares visible than colored squared.

Chains 01

Below is an example of a complete tiling of a 6×6 board.

6x6 01

And here is our game: Each player gets the same number of tiles. For two players, is a good choice, say three of each kind. The players take turns placing one tile on the table so that 

  1. each new tile links with a previous tile
  2. two linked tiles are of different color

Alternatively, a player can also remove the last played tile and replace it by another one.

The goal is to create a complete closed chain when all tiles are used up. 

Below is an example of a successfully closed loop of length 8.

Loop 01

Translucent Dominoes (Cooperation Games II)

Most tiling problems are strictly segregational, i.e. the tiles are not allowed to overlap. To change this, let’s consider tiles that are partially translucent, so that in order to really tile a part of the plane, one needs to cover it multiple times.

This is the first in a series of posts about partially translucent polyominoes, and we begin with translucent dominoes, of which there are three:

Dominoes 01

The purple one is a regular (non-translucent) domino, and to the right you can see my feeble attempt to tile a 4×4 square of which two opposite squares have been removed (This is of course a very classical puzzle). The other two dominoes have one or two translucent squares, which are shown as gray. This translucency means that in order to properly tile a square with dominoes, we need to cover it either with a single solid color square, or with two translucent (gray) squares, i.e. the gray portions of two dominoes must overlap, like so: Connect 01

The left image shows two fully translucent dominoes that overlap in the middle square, while the left and right squares are still only covered once. By counting the small connector squares you can see how many gray squares sit on top of each other. In the middle is a chain of four dominoes, all gray tiles are doubled. And to the right we have covered the middle gray square three times, which is illegal for now. 

If we use only the blue singly translucent domino to tile, two of them need to overlap to form a single classical (segregational) tromino, so tiling with these dominoes alone is equivalent to tiling with trominoes.

Domino tromino 01

You should try to tile the 4×4 square (with two opposite corners removed as above) with copies of either the singly or the doubly  translucent domino. In both cases, this is impossible (and impossible for larger squares as well, again with opposite corners removed. You will enjoy finding the arguments). Tiling becomes easier when you allow both types of translucent tiles, a simple solution to the 4×4 puzzle is shown below to the right. The left figure gives a hint what limitations you face when you try to tile with the doubly translucent domino alone.

Domino4x4 01

As a cooperative game, start with a 6×6 square, mark a few tiles as forbidden, and then take turns to place translucent dominoes on the board with the goal to tile the board completely, following the translucency rule.

Weed (Cooperation Games I)

It’s time for change.

Weed is a cooperative card game for 1-4 players. There are three different types of cards, in four colors:

Types 01

They can be laid out to grow weeds, like so:

Weed 1 01

When placing the cards, there are a couple of things we shouldn’t do. We won’t:

Nonos 01

Below is a full set of cards, and here a printable pdf.

Cards 01

Now for the game: The players first agree on a board size, like a 6×6 square. As many cards as there are players are placed face down onto the board so that they don’t share an edge, not share an edge with the boundary of the board, and then turned over. The remaining cards are dealt to the players. They take turns to grow weeds, only placing cards that match previously placed cards. For every completed weed the players get one point. For each square of the board that can’t be tiled one point is being subtracted. The goal is to come out positive, of course.

Below is a perfectly completed 6×6 board. Sample 01

 

Enjoy, and go in peace.

Recursion – Solution (Solitaire XXVI)

To keep this week’s frustration to the necessary minimum, here is a discussion of last week’s recursion puzzle:

 

I first asked to assemble any of the 30 squares whose sides are colored in four distinct colors out of five from four smaller squares so that edge colors match, and we don’t use the square we start with, like so:

 

Rec2 1 01

As we can see, there are seven different solutions. It doesn’t matter which square you start with, permuting the colors will reduce everything to this example. Next we need to pick one of these seven solutions, and assemble each of the four sub-squares using 16 of the the remaining squares. It turns out that

  1. this is only possible for the fifth solution above;
  2. each subsquare can be assembled in two distinct ways:

Rec2 2 01

But only two of the 16 possible choices satisfies the condition that we are not allowed to reuse squares, namely these two:

Rec2 3 01

Pretty? Now the remaining squares 9 can be, in each case, assembled into a 3×3 square in exactly one way:

Rec2 4 01

Here are a few hints about this: First note that the dark green color has to occur an even number of times, the other colors an odd number each. This forces the other colors to constitute the boundary, so dark green is confined to the interior. A bit trial and error shows that the only green-free square has to be at the center, and the green edges assemble in a pattern as above.