The Library of Babel II

Today we are taking the 2-dimensional floor plans of the Library of Babel  to the third dimension. The simplest way is to use a single floor plan and copy it for every level of the library. For instance, last time’s finite hexagon becomes a daunting infinite tower, at least in our imagination.

Babel hex 01

One could also do the same with several separate hexagons, but the resulting library would consist of several buildings, which, while not explicitly prohibited by Borges, seems unacceptable.

Doublyplus 01

But there is another possibility. For instance, using the arrangement of hexagons in horizontal lines, and repeating them vertically (as on the left above), but then, on the second floor, using the same floor plan albeit rotated by 90º (as in the middle), and then repeating this periodically, we arrive at a single building where it is sometimes necessary to climb up, walk across, and then down again to reach a different room on the same floor.

Nearby places can sometimes be terribly far away.

In the double floor plan up above on the right we see that this can be done by aligning the vestibules in a square pattern, leaving star-shaped Voids. Below is a partial view of this magnificent library:

Babel3The condition that the staircases in the vestibules extend infinitely in both directions is quite limiting, even if one doesn’t require that each staircase can be reached at every floor. A good strategy for designing even more complicated libraries is to begin with a floor plan that includes hexagons and squares, and use on each floor a different subset of these squares and hexagons as vestibules and galleries. For instance, we can start with this Archimedean tiling that has large dodecagonal Voids:Archi2 01


One individual floor then could look like this, seemingly giving each gallery three exits to vestibules with staircases, one of which, however, will be blocked off by a bookshelf on two of its sides:

Third 01

This floor plan will be rotated by 120º on each subsequent floor (about the center of one of the dodecagonal Voids), creating a single labyrinthian library.

Here is a deliciously maddening view into the resulting skeleton of this library. I haven’t closed off the inaccessible staircases yet, so please watch your step.


Happy are those of us who can get lost in a single book like in this Borgesian library. 

The Library of Babel I

In the story The Library of Babel, Jorge Luis Borges describes a library whose design follows near axiomatic principles:

It is composed of an indefinite, perhaps infinite number of hexagonal galleries. In the center of each gallery is a ventilation shaft, bounded by a low railing. From any hexagon one can see the floors above and below—one after another, endlessly. The arrangement of the galleries is always the same.Babel2

One of the hexagon’s free sides opens onto a narrow sort of vestibule, which in turn opens onto another gallery, identical to the first—identical in fact to all. […] Through this space, too, there passes a spiral staircase, which winds upward and downward into the remotest distance.

If we remove all the cosmetics, we might end up with a design like the above, clearly unsatisfactory. Nothing is said about the underlying geometry of the library, Euclidean, spherical, hyperbolic, or even more esoteric. We will assume that the universe is Euclidean, for now, because this is still interesting enough. In this first post I will discuss the floor plans of a single floor. The combination of hexagonal galleries and square vestibules suggests that we are looking at floor plans that can be derived from this Archimedean tiling of the plane:

Babel 1

Of course the triangles will be Voids, and we have too many square vestibules. We get one more clue (or axiom) from Borges: Twenty bookshelves, five to each side, line four of the hexagon’s six sides […]

This means that each gallery has just two vestibules where one can enter or exit. As all galleries are identical, this leaves us with three distinct possibilities how a gallery can look like.

Babel straight 01

If we assume that the vestibules are placed at opposite sides of a gallery, our floor plan will necessarily look like the one above (which is used in the top image, too), representing a favorite labyrinth of Borges, the line (!). In the other extreme case, when the vestibules are at adjacent sides of each hexagon, there are two possible floor plans:

Babel 60

As a single floor plan, neither looks exciting, but we’ll see. There is one more option when between the two exits to the vestibules there is just one wall with shelves, like so:

Babel 120a 01

And fascinatingly, this last options allows for much more intricate floor plans, like this infinite double spiral:

Babel spiral 01

Next time we will investigate how the connections between different floors makes the life of the librarians even more exciting.

Tripods III

After realizing that while choices allow for free will, too many choices make everything possible and create only an illusion of free will. So let’s allow very few choices in our tripod-universe:

Two 1

Above are the tripods we are allowed to use, and below the first three generations of our expanding universe if we pick the first of the three above and place it at the center:


Two 2 01

We see that at each step, there are only two choices that occur along precisely one branch (marked red). So while the number of possible universe histories grows exponentially, the overwhelming majority of its inhabitants (i.e. the leaves at the end of the trees) don’t have a choice, their future is predetermined and can’t even be affected by the single monarch who can only determine their own future. More choice is needed.

Two 3

So let’s allow all six tripods that use three colors with just one color occurring twice as leaves. We choose one of them for the Big Bang at time 0. At time 1 we already have 27 different possible histories, because at each leaf there are always 3 choices that can be made:

Two 4

In the next generation, we will have already 19683 different possibilities. This looks promising, so let’s see how much these tripods can control their future. Below are two universes at time 2 that use only the colors yellow/green and yellow/blue at the leaves. Can you find a universe where all leaves are yellow? Or blue?

Two 5

Some more questions:

  • Suppose you succeeded in making all leaves yellow. How many more generations does it take you to make all leaves blue?
  • Can you have a universe where no two neighboring leaves have the same color?
  • Below is a universe where in generations 1,2, and 3 each we have an equal number of leaves of each color. Eg, in the current generation 3, there are 8 green, blue, and yellow leaves. Can you continue like this? Is there a recipe for it?


Two 6

HOF+ (Tetrasticks I)

A polystick is a connected finite subgraph of the grid graph, and a tetrastick is a polystick with four edges. There are 25 of them, counting mirror copies.

Tetrasticks 25 01

In other words, these are squiggles you can make with four strokes. They’d make a nice alphabet for people who are addicted to abstraction.

Hof 01


Today we are focussing on six of them, fattened and colored above. They are denoted by the letters H, O, F, +, and the mirrors of H and F. For reasons to become clear later we consider O and + also as mirrors of each other in a certain sense. The goal is to tile rectangles with them, like in the 3×7 and 2×12 rectangles below.

Example 01

There are many constraints on what tiles one can use, and how many. For instance, an a x b rectangular grid has a(b+1) vertical and (a+1)b horizontal edges, for a total of 2ab+a+b edges. This number is divisible by 4 only if a-b is divisible by 4, so squares are good for tiling, as are the two rectangles above. They both consist of 52 segments and thus require 13 tetrasticks. Below is a different example.

Example2 01

Note that all our 6 letter except for H and its mirror use two horizontal and two vertical segments. As the 3×7 rectangle has 4 more horizontal edges than vertical ones, we need at least four H-tetrasticks (or its mirrors) to tile this rectangle. We can use more, but then only an even number of them. Likewise, we need at least two H-tetrasticks to tile the 2×12 rectangle.

Example3 01

This brings us to today’s puzzle: Tile the 3×7 rectangle with your choice of 13 tetrasticks from our selection of six, and then use the same set to tile the 2×12 rectangle. The examples on this page are attempts that require to flip an H or an F into its mirror (or an O into +). Can you find a perfect solution that doesn’t require flipping a tetrastick over?

Raleigh’s Theorem

We all love natural numbers. Let’s take a sequence of real numbers 0 = a< a< a< …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.


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 Qwhich 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.


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
a< 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:


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’>𝜑.

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.

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”>𝜑.

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