Category: Mathematics

Raleigh’s Theorem

We all love natural numbers. Let’s take a sequence of real numbers 0 = a0 < a1 < a2 < …and corresponding intervals An = [an, an+1]. We call an interval An lucky if it contains a natural number:ScaleHere the intervals A1, A2, A4, A5 are lucky and marked in green. We don’t want intervals to be too lucky and therefore insist that intervals are shorter than unit length. We also want each natural number to know where it belongs, so we don’t want our sequences to contain any natural numbers.

To increase happiness, we consider two such sequences an and bn shown on top of each other at height +1 and -1, respectively. Corresponding intervals An and Bn are upper and lower edges of quadrilaterals Qn. Golden

In this particular example the sequences are linear, namely an = n(𝛗-1) and bn= n(2-𝜑), where 𝜑 is the Golden Ratio once more. We note that either An or Bn is lucky, but never both. So each quadrilateral has precisely one lucky edge. 

In order to understand how this can possibly be true, we consider more generally two increasing sequences an and bn such that an + bn = n, and such that intervals are shorter than 1. Then the average sequence is cn = (an + bn)/2 = n/2, which we include in the next figure at height 0 between the sequences an and bn.

Nodouble

As already noted, no interval An or Bn can contain two natural numbers. If both contain a natural number, we can join them by a red segment within Qn which intersects the height 0 line in a point whose x-coordinate is of the form n/2, where n is a natural number. But all these points with half-integral coordinates are already taken by the (blue) sequence cn. So at most one of the intervals An or Bn can be lucky.

Nonone

Now suppose that neither An or Bn are lucky. Then both intervals An and Bn are contained in integer intervals of length 1, marked as green dots to the left and right of the orange quadrilateral. The endpoints average to points with integral coordinates (green crosses) that are 1 unit apart and outside the orange quadrilateral. But both blue crosses on the orange quadrilateral have half integral coordinates, which can’t be. Thus either An or Bn is lucky.

As promised, this proves Raleigh’s Theorem: If irrational 𝛂, 𝛃 > 0 satisfy 1/𝛂 + 1/𝛃 = 1, then 𝛂n = [n 𝛂] and 𝛃n = [n 𝛃] are complementary, i.e. each natural number occurs in precisely one of the two sequences. 

To see this, let a=1/𝛂 and b=1/𝛃, an = n a  and bn= n b. Now observe that An contains a natural number k if and only if
an < k < an+1 if and only if n< k 𝛂 < n+1 if and only if n = [k 𝛂] (and likewise for Bn).

 

The argument in terms of intervals is a mere geometric formulation of the standard proof of Raleigh’s theorem but gives a more general result that is not so apparent in the purely algebraic version.

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. 

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.

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 Trominoes (Cooperation Games III)

After the translucent dominoes let’s continue with translucent L-trominoes. There are eight of them:

 

 

Trominoes 01

The dark-gray one is a solid tromino, which will be a bit lonely, as it can’t connect to the others.

As before, a region is tiled if either any square is covered by a solid color or by two translucent (gray) squares.

Tromino mono

Let’s begin with a simple puzzle. Above you see an attempt to tile the 5×5 square just with copies of the purple tromino. This is of course impossible, because each purple tromino tiles 1+1/2+1/2 = 2 squares, so it can only tile regions with an even number of squares. Clearly one can tile a 2×2 square, and thus every 2n x 2n square. But can you also tile a say 6×6 square so that the tiles are all connected?

Tromino5x5

Above is an example how you can tile a 5×5 square with two copies of each tromino except the orange and the dark gray one. There is an abundance of tiling problems like this. You usually begin by determining for a set of tiles the total number of squares they will cover, counting each gray piece as 1/2. As all eight trominoes cover 18 full squares, two sets of them should be enough to cover a 6×6 square. One solution is shown below.

6x6 01

This suggests the following cooperative game for two players: Each gets a set of the seven trominoes without the dark gray one, shuffled, and stacked face up. They take turns by either

— placing the top tromino from their stack on a 6×6 board so that the newly placed tromino connects to the network of previously placed trominoes; or
— removing a previously placed tromino from the board so that the network remains connected, and placing it under their pile.

The goal is to leave at the end just room for the two dark gray trominoes. The example above is therefore no solution, because the network has too many components.

 

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.

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.

Recursion (Solitaire XXV)

Time for another Isolation Puzzle while the days grow darker. Here are all 30 squares whose sides are colored in four different colors, chosen from five available colors. Print and cut them all out:

Fivecolors 01

Pick one of them. The first easy puzzle is to assemble it using four of the remaining 29 squares, like so, for instance:

Puzzle0 01

Notice that the border of the 2×2 square matches the border of the chosen square, and squares that touch must match along their common sides, too. The second not quite so easy puzzle is actually four puzzles, namely to assemble each of the four squares on the right using 16 of the remaining 25 squares. No duplicate usage is allowed! Below is a solution for the top left square. 

Puzzle1 01

Do this with the other three squares. The solution is by no means unique, and it is well possible that you get stuck and have to revise your choices. When done, you are left with 9 remaining squares. The final not at all easy puzzle consists of assembling them into a 3×3 square so that the sides are in one color each, and again tiles match their colors along joint sides. Like so:

3x3 01

In the above example (yours might well be very different), can you also have dark green occur on the sides of the 3×3 square? And, has this anything to do with dark green missing in the square we started with? Sometimes the past is going to haunt us…

And finally (but maybe this is impossible), can you make the 3×3 square so that its border is an enlarged version of the square we started with?