Skip to content →

Category: games

Penrose’s aperiodic tilings

Around 1975 Sir Roger Penrose discovered his aperiodic P2 tilings of the plane, using only two puzzle pieces: Kites (K) and Darts (D)



The inner angles of these pieces are all multiples of $36^o = \tfrac{180^o}{5}$, the short edges have length $1$, and the long edges have length $\tau = \tfrac{1+\sqrt{5}}{2}$, the golden ratio. These pieces must be joined together so that the colours match up (if we do not use this rule it is easy to get periodic tilings with these two pieces).

There is plenty of excellent online material available:

  • The two original Martin Gardner Scientific American articles on Penrose tiles have been made available by the MAA, and were reprinted in “Penrose Tiles to Trapdoor Ciphers”. They contain most of Conway’s early discoveries about these tilings, but without proofs.
  • A JavaScript application by Kevin Bertman to play around with these tilings. You can deflate and inflate tilings, find forced tiles and much more. Beneath the app-window there’s a detailed explanation of all the basics, including inflation and deflation of the P2-tiles, the seven types of local vertex configurations (naming by Conway, of course),




    proofs of aperiodicity (similar to the one for Conway’s musical sequences), that every tile lies within an ace (similar to the LSL-subword in musical sequences) with application to local isomorphism (again similar to the $1$-dimensional case).
  • Course notes of an Oxford masterclass in geometry Lectures on Penrose tilings by Alexander Ritter, again with proofs of all of the above and a discussion about the Cartwheel tilings (similar to that in the post on musical sequences), giving an algorithm to decide whether or not a partial tiling can be extended to the entire plane, or not.

There’s no point copying this material here. Rather, I’d like to use some time in this GoV series of posts to talk about de Bruijn’s pentagrid results. For this reason, I now need to make the connection with Penrose’s ‘other’ tilings, the P3 tiles of ‘thin’ and ‘thick’ rhombi (sometimes called ‘skinny’ and ‘fat’ rhombi).



Every Penrose P2-tiling can be turned into a P3-rhombic tiling, and conversely.

From kites and darts to rhombi: divide every kite in two halves along its line of reflection. Then combine darts and half-kites into rhombi where a fat rhombus consists of a dart and two half-kites, joined at a long edge, and a skinny rhombus is made of two half-kites, joined at a short edge. This can always be done preserving the gluing conditions. It suffices to verify this for the deflated kite and dart (on the left below) and we see that the matching colour-conditions are those of the rhombi.




From rhombi to kites and darts: divide every fat rhombus into a dart (placed at the red acute angle) and two half-kites, joined at a long edge, and divide every skinny rhombus into two half-kites along its short diagonal.

All results holding for Kites and Darts tilings have therefore their versions for Rhombic tilings. For example, we have rhombic deflation and inflation rules



A Rhombic tiling can be seen as an intermediate step in the inflation process of a Penrose tiling $P$. Start by dividing all kites in two halves along their long diagonal and all darts in two halves along their short diagonal (the purple lines below).



If we consider all original black lines together with the new purple ones, we get a tiling of the plane by triangles and we call this the $A$-tiling. There are two triangles, s small triangle $S_A$ (the whiter ones, with two small edges ofd length $1$ and one edge of length $\tau$) and a large triangle $L_A$ (the greyer ones, with two edges of length $\tau$ and one edge of length $1$).

Next, we remove the black lines joining an $S_A$-triangle with an $L_A$-triangle, and get another tiling with triangles, the $B$-tiling, with two pieces, a large triangle $L_B$ with two sides of length $\tau$ and one side of length $1+\tau$ (the white ones) (the union of an $L_A$ and a $S_A$), and a small triangle $S_B$ which has the same form as $L_A$ (the greyer ones). If we now join two white triangles $L_B$ along their common longer edge, and two greyer triangles $S_B$ along their common smaller edge, we obtain the Rhombic tiling $R$ corresponding to $P$.



We can repeat this process starting with the Rhombic tiling $R$. We divide all fat rhombi in two along their long diagonals, and the skinny rhombi in two along their short diagonals (the purple lines). We obtain a tiling of the plane by triangles, which is of course just the $B$-tiling above.



Remove the edge joining a small $S_B$ with a large $L_B$ triangle, then we get a new tiling by triangles, the $\tau A$-tiling consisting of large triangles $L_{\tau A}$ (the white ones) with two long edges of length $1+\tau$ and one short edge of length $\tau$ (note that $L_{\tau A}$ is $\tau$ times the triangle $L_A$), and a smaller one $S_{\tau A}$ (the grey ones) having two short edges of length $\tau$ and one long edge of length $1+\tau$ (again $S_{\tau A}$ is $\tau$ times the triangle $S_A$). If we join two $L_{\tau A}$-triangles sharing a common long edge we obtain a Kite ($\tau$-times larger than the original Kite) and if we joint two $S_{\tau A}$-triangles along their common small edge we get a Dart ($\tau$ times larger than the original Dart). The Penrose tiling we obtain is the inflation $inf(P)$ of the original $P$.

If we repeat the whole procedure starting from $inf(P)$ instead of $P$ we get, in turn, triangle tilings of the plane, subsequently the $\tau B$-tiling, the $\tau^2 A$-tiling, the $\tau^2 B$-tiling and so on, the triangles in a $\tau^n A$-tiling being of size $\tau^2$-times those of the $A$-tiling, and those in the $\tau^n B$-tiling $\tau^n$-times as large as those of the $B$-tiling.

The upshot of this is that we can associate to a Penrose tiling $P$ of the plane a sequence of $0$’s and $1$’s. Starting from $P$ we have an infinite sequence of associated triangle tilings
\[
A,~B,~\tau A,~\tau B,~\tau^2 A, \dots,~\tau^n A,~\tau^n B,~\tau^{n+1} A, \dots \]
with larger and larger triangle tiles. Let $p$ be a point of the plane lying in the interior of an $A$-tile, then we define its index sequence
\[
i(P,p) = (x_0,x_1,x_2,\dots ) \quad x_{2n} = \begin{cases} 0~\text{if $p \in L_{\tau^n A}$} \\ 1~\text{if $p \in S_{\tau^n A}$} \end{cases}~ x_{2n+1} = \begin{cases} 0~\text{if $p \in L_{\tau^n B}$} \\ 1~\text{if $p \in S_{\tau^n B}$} \end{cases} \]
That is, $x_0=1$ if $p$ lies in a small triangle of the $A$-tiling and $x_0=1$ if it lies in a large triangle, $x_1=1$ if $p$ lies in a small triangle of the $B$-tiling and is $0$ if it lies in a large $B$-triangle, and so on.

The beauty of this is that every infinite sequence $(x_0,x_1,x_2,\dots )$ whose terms are $0$ or $1$, and in which no two consecutive terms are equal to $1$, is the index sequence $i(P,p)$ of some Penrose tiling $P$ in some point $p$ of the plane.

From the construction of the sequence of triangle-tilings it follows that a small triangle is part of a large triangle in the next tiling. For this reason an index sequence can never have two consecutive ones. An index sequence gives explicit instructions as to how the Penrose tiling is constructed. In each step add a large or small triangle as to fit the sequence, together with the matching triangle (the other half of a Penrose or Rhombic tile). Next, look at the patches $P_i$ of Kites and Darts (in the $\tau^i A$ tiling), for $i=0,1,\dots$, then $P_{i-k}$ is contained in the $k$-times inflated $P_i$, $i^k(P_i)$ (without rescaling), for each $i$ and all $1 \leq k \leq i$. But then, we have a concentric series of patches
\[
P_0 \subset i(P_1) \subset i^2(P_2) \subset \dots \]
filling the entire plane.



The index sequence depends on the choice of point $p$ in the plane. If $p’$ is another point, then as the triangle tiles increase is size at each step, $p$ and $p’$ will lie in the same triangle-tile at some stage, and after that moment their index sequences will be the same.

As a result, there exists an uncountable infinity of distinct Penrose tilings of the plane.

From the discussions we see that a Penrose tiling is determined by the index-sequence in any point in the plane $(x_0,x_1,\dots )$ consisting of $0$’s and $1$’s having no two consecutive $1$’s, and that another such sequence $(x’_0,x’_1,\dots )$ determines the same Penrose tilings if $x_n=x’_n$ for all $n \geq N$ for some number $N$. That is, the Penrose tiling is determined by the the equivalence class of such sequences, and it is easy to see that there are uncountably many such equivalence classes.

If you want to play a bit with Penrose tiles, you can order the P2 tiles or the P3 tiles from
Cherry Arbor Design.

Leave a Comment

The strange logic of subways

“A subway is just a hole in the ground, and that hole is a maze.”

“The map is the last vestige of the old system. If you can’t read the map, you can’t use the subway.”

Eddie Jabbour in Can he get there from here? (NYT)

Sometimes, lines between adjacent stations can be uni-directional (as in the Paris Metro map below in the right upper corner, 7bis). So, it is best to view a subway map as a directed graph, with vertices the different stations, and directed arrows when there’s a service connecting two adjacent stations.



Aha! But, directed graphs form a presheaf topos. So, each and every every subway in the world comes with its own logic, its own bi-Heyting algebra!

Come again…?

Let’s say Wally (or Waldo, or Charlie) is somewhere in the Paris metro, and we want to find him. One can make statements like:

$P$ = “Wally is on line 3bis from Gambetta to Porte des Lilas.”, or

$Q$ = “Wally is traveling along line 11.”

Each sentence pinpoints Wally’s location to some directed subgraph of the full Paris metro digraph, let’s call this subgraph the ‘scope’ of the sentence.

We can connect such sentences with logical connectives $\vee$ or $\wedge$ and the scope will then be the union or intersection of the respective scopes.

The scope of $P \vee Q$ is the directed subgraph of line 11 (in both directions) together with the directed subgraph of line 3bis from Gambetta to Porte des Lilas.

The scope of $P \wedge Q$ is just the vertex corresponding to Porte des Lilas.

The scope of the negation $\neg R$ of a sentence $R$ is the subgraph complement of the scope of $R$, so it is the full metro graph minus all vertices and directed edges in $R$-scope, together with all directed edges starting or ending in one of the deleted vertices.

For example, the scope of $\neg P$ does not contain directed edges along 3bis in the reverse direction, nor the edges connecting Gambetta to Pere Lachaise, and so on.

In the Paris metro logic the law of double negation does not hold.



$\neg \neg P \not= P$ as both statements have different scopes. For example, the reverse direction of line 3bis is part of the scope of $\neg \neg P$, but not of $P$.

So, although the scope of $P \wedge \neg P$ is empty, that of $P \vee \neg P$ is not the full digraph.

The logical operations $\vee$, $\wedge$ and $\neg$ do not turn the partially ordered set of all directed subgraphs of the Paris metro into a Boolean algebra structure, but rather a Heyting algebra.

Perhaps we were too drastic in removing all “problematic edges” from the scope of $\neg R$ (those with a source or target station belonging to the scope of $R$)?

We might have kept all problematic edges, and added the missing source and/or target stations to get the scope of another negation of $R$: $\sim R$.

Whereas the scope of $\neg \neg R$ always contains that of $R$, the scope of $\sim \sim R$ is contained in $R$’s scope.

The scope of $R \vee \sim R$ will indeed be the whole graph, but now $R \wedge \sim R$ does no longer have to be empty. For example, $P \wedge \sim P$ has as its scope all stations on line 3bis.

In general $R \wedge \sim R$ will be called the ‘boundary’ $\partial(R)$ of $R$. It consists of all stations within $R$’s scope that are connected to the outside of $R$’s scope.

The logical operations $\vee$, $\wedge$, $\neg$ and $\sim$ make the partially ordered set of all directed subgraphs of the Paris metro into a bi-Heyting algebra.

There’s plenty more to say about all of this (and I may come back to it later). For the impatient, there’s the paper by Reyes and Zolfaghari: Bi-Heyting Algebras, Toposes and Modalities.

Right now, I’m more into exploring whether this setting can be used to revive an old project of mine: Heyting Smullyanesque problems (btw. the algebra in that post is not Heyting, oops!).

Leave a Comment

Heyting Smullyanesque problems

Raymond Smullyan brought Knights and Knaves puzzles to a high art in his books. Here’s the setting:

On Smullyan’s islands there are Knights, who always tell true statements, Knaves, who always lie, and sometimes also Normals, who sometimes tell the truth and sometimes lie.


(image credit MikeKlein)

Problems of this sort can be solved by classical propositional logic, replacing every sentence $P$ told by inhabitant $A$ by the formula $k_A \leftrightarrow P$ where $k_A$ is the sentence “A is a Knight”.

Some time ago I asked for Smullyanesque problems in a non-classical logic, where we replace the usual truth-values $T$ (true) and $F$ (false) of propositional logic by elements of an Heyting algebra.

Jason Rosenhouse wrote a paper Knights, Knaves, Normals, and Neutrals for The College Mathematics Journal, containing more information than in his blog post, as well as some nice challenging puzzles. Here’s Rosenhouse’s setting:

Apart from Knights, Knaves and Normals there’s also the tribe of Neutrals (which he describes as a sort of trans-Knights or trans-Knaves) who can only tell sentences with truth value $N$ in the Heyting algebra $\{ T,N,F \}$ with logical connectives

A typical sentence of truth value $N$ is “A is a Knight” or “A is a Knave” whereas, in reality, $A$ is Neutral. Here are the truth values of sentences about a person (the column headings) with respect to the actual situation (the row headings)

A good way into such problems is to focus on sentence like “A is a Neutral” as they have only classical truth values $T$ or $F$ and to remember that Neutrals can never say a sentence with classical truth value. Here’s an example (only Knights,Knaves or Neutrals present):

Problem 1: Suppose you meet three people, named Dave, Evan and Ford. They make the following statements:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral.

Can you determine the types of all three people?

Solution: Ford’s sentence has value $T$ or $F$, so Ford cannot be Neutral so must be a Knight or Knave. But then Evan’s sentence also has classical truth value, so he can’t be Neutral either, and by the same reasoning also Dave cannot be neutral. So, we know that all three people must be either Knights or Knaves and then it follows at once that Ford is a Knave (because he lied) and that Evan and Dave must be knights.

These puzzles become more interesting once we use logical connectives.

Problem 2: What can you conclude from this dialog?

Mimi: Olaf is a Knight and Olaf is not a Knight.
Nate: Olaf is a Knave or Olaf is not a Knave.
Olaf: Mimi is a Knight or Nate is a Knave or I am Neutral.

Solution: Mimi’s sentence can only have truth value $F$ or $N$ so she can’t be a Knight. Nate’s sentence has value $T$ or $N$ so he cannot be a Knave.
The two first parts of Olaf’s line cannot be $T$ so must be either $N$ or $F$. So, Olav’s line has total value $T$ only if the last part ‘I am Neutral’ is $T$. So, Olaf can neither be a Knight (because then the last part is $F$) nor Neutral (because then the line would have value $T$ and Neutrals can only speak $N$-sentences). So, Olaf must be a knave. Nate must then be a Knight and Mimi a Knave (because the first part of her line is $F$ and so must be the whole sentence).

The situation becomes even more complicated when we allow Normals (who sometimes lie and sometimes tell the truth but never say sentences with value $N$) to be present. Here’s Rosenhouse’s ‘Grand Finale’:

Problem 3: One day a visitor encountered eight people, among them exactly two Knights, two Knaves, two Normals and two Neutrals. What can you conclude from this dialog:

Sara: Walt is a Neutral or Vera is a Neutral.
Todd: Xara is a Knave and Yoav is a Knave.
Ursa: If Sara is a Knight, then Todd and Yoav are Normals.
Vera: I am not a Neutral.
Walt: If Vera is not a Neutral, then neither is Todd.
Xara: Todd is a Knight if and only if Zack is a Neutral.
Zack: Xara is a Neutral if and only if Walt is not a Normal.

You will solve this problem much quicker than to read through the long explanation in Rosenhouse’s paper.

These puzzles beg to be generalised to more complicated Heyting algebras.

What about a book on “Knights, Knaves and Knols”? A Knol (or $X$-Knol) has knowledge limited to sentences with truth value $X$, an element in the Heyting algebra.

Leave a Comment

Knights and Knaves, the Heyting way

(image credit: Joe Blitzstein via Twitter)

Smullyan’s Knights and Knaves problems are classics. On an island all inhabitants are either Knights (who only tell true things) and Knaves (who always lie). You have to determine their nature from a few statements. Here’s a very simple problem:

“Abercrombie met just two inhabitants, A and B. A made the following statement: “Both of us are Knaves.” What is A and what is B?”

Now, this one is simple enough to solve, but for more complicated problems a generic way to solve the puzzles is to use propositional calculas, as explained in Smullyan’s Logical Labyrinths”, chapter 8 “Liars, truth-tellers and propositional logic’.

If an inhabitants $A$ asserts a proposition $P$, and if $k_A$ is the assertion ‘$A$ is a Knight’, then the statement can be rephrased as

\[
k_A \Leftrightarrow P \]

for if $A$ is a Knight, $P$ must be true and if $A$ is a Knave $P$ must be false.

Usually, one can express $P$ as a propositional statement involving $k_A,k_B,k_C,\dots$.
The example above can be rephrased as

\[
k_A \Leftrightarrow (\neg k_A \wedge \neg k_B) \]

Assigning truth values to $k_A$ and $k_B$ and setting up the truth-table for this sentence, one sees that the only possibility for this to be true is that $k_A$ equals $0$ and $k_B$ equals $1$. So, $A$ is a Knave and $B$ is a Knight.

Clearly, one only requires this approach for far more difficult problems.

In almost all Smullyan puzzles, the only truth values are $0$ and $1$. There’s a short excursion to Boolean algebras (sorry, Boolean islands) in chapter 9 ‘Variable Liars’ in Logical Labyrinths. But then, the type of problems are about finding equivalent notions of Boolean algebras, rather that generalised Knights&Knaves puzzles.

Did anyone pursue the idea of Smullyanesque puzzles with truth values in a proper Heyting algebra?

I only found one blog-post on this: Non-Classical Knights and Knaves by Jason Rosenhouse.

He considers three valued logic (the Heyting algebra corresponding to the poset 0-N-1, and logical connectives as in the example on the Wiki-page on Heyting algebras.

On his island the natives cycle, repeatedly and unpredictably, between the two states. They are knights for a while, then they enter a transitional phase during which they are partly knight and partly knave, and then they emerge on the other side as knaves.

“If Joe is in the transitional phase, and you say, “Joe is a knight,” or “Joe is a knave,” what truth value should we assign to your statement? Since Joe is partly knight and partly knave, neither of the classical truth values seems appropriate. So we shall assign a third truth value, “N” to such statements. Think of N as standing for “neutral” or “neither true nor false.” On the island, vague statements are assigned the truth value N.

Just to be clear, it’s not just any statement that can be assigned the truth value N. It is only vague statements that receive that truth value, and for now our only examples of such statements are attributions of knight-hood and knave-hood to people in the transitional phase.

For the natives, entering the transitional phase implied a disconcerting loss of identity. Uncertain of how to behave, they hedged their bets by only making statements with truth value N. People in the transitional phase were referred to as neutrals. So there are now three kinds of people: Knights, who only make true statements; Knaves, who only make false statements; and Neutrals, who only make statements with the truth value N.”

He gives one example of a possible problem:

“Suppose you meet three people, named Dave, Evan and Ford. They make the following statements:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral.

Can you determine the types of all three people?”

If you know of more of these Smullanesque problems using Heyting algebras, please leave a comment.

Leave a Comment

a SNORTgo endgame

SNORT, invented by Simon NORTon is a map-coloring game, similar to COL. Only, this time, neighbours may not be coloured differently.

SNORTgo, similar to COLgo, is SNORT played with go-stones on a go-board. That is, adjacent stones must have the same colour.

SNORT is a ‘hot’ game, meaning that each player is eager to move as most moves will improve your position. In COL players are reluctant to move, because a move limits your next moves.

For this reason, SNORT positions are much harder to evaluate, and one needs the full force of Conways’s ONAG.

Here’s a SNORTgo endgame. Who has a winning strategy?, and what is the first move in that strategy?

The method to approach such an endgame is similar to that in COLgo. First we remove all dead spots from the board.

What remains, are a 4 spots available only to Right (white) and 5 spots available only to Left (bLack). Further, there a 3 ‘live’ regions: the upper righthand corner and the two lower corners.

The value of these corners must be computed inductively.

Here’s the answer:

For example, Right’s best option in the left-most game (corresponding to the upper righthand corner of the endgame) is to put his stone on N12, resulting in a game in which neither player can move (the zero game).

On the other hand, Left can put a stone at either N11, N12 or N13 leaving a game in which she has two more moves, whereas Right han none (the $2$ game).

The other positions are computed similarly.

To get the value of the endgame we have to sum up all these values.

This can either be done using the addition rule given in ONAG, or by using programs in combinatorial game theory.

There’s Combinatorial Game Suite, developed by Aaron Siegel. But, for some reason I can no longer use it on macOS High Sierra.

Fortunately, the older program David Wolfe’s toolkit is still available, and runs on my MacBook.

The sum game evaluates to $\{ \{3|2 \}|-1 \}$, which is a ‘fuzzy’ game, that is, its value is confused with $0$.

This means that the first player to move has a winning strategy in the endgame.

Can you spot the (unique) winning move for Right (white) and one (of two) winning move for Left (bLack)?

Spoiler alert : solution in the comments.

One Comment

a COLgo endgame

COL is a map-colouring game, attibuted to Colin Vout. COLgo is COL played with Go-stones on a go-board.

The two players, bLack (left) and white (right) take turns placing a stone of their colour on the board, but two stones of the same colour may not be next to each other.

The first player unable to make a legal move looses this game.

As is common in combinatorial game theory we do not specify which player has the move. There are $4$ different outcomes, the game is called:

– positive, if there is a winning strategy for Left (bLack),
– negative, if there is a winning strategy for Right (white),
– zero, if there is a winning strategy for the second-player,
– fuzzy, if there is a winning strategy for the first player.

Here’s an endgame problem: who wins this game?

Spoiler alert: solution below.

First we can exclude all spots which are dead, that is, are excluded for both players. Example, F11 is dead because it neighbors a black as well as a white stone, but F10 is alive as it can be played by white (Right).

If we remove all dead spots, we are left with 4 regions (the four extremal corners of the board) as well as 5 spots, 3 for white and 2 for black.

That is, the game reduces to this “sum”-game, in which a player chooses one of the regions and does a legal move in that component, or takes a stone of its own colour from the second row.

Next, we have to give a value to each of the region-games.

– the right-most game has value $0$ as the second player has a winning strategy by reflecting the first player’s move with respect to the central (dead) spot.

– the left-most game is equivalent to one black stone. Black can make two moves in the game, independent of the only move that white can make. So it has value $+1$.

– the sum-game of the two middle games has value zero. The second player can win by mirroring the first player’s move in the other component. This is called the Tweedledee-Tweedledum argument.

But then, the total value of the endgame position is

zero, so the first player to move looses the game!

Leave a Comment

Chomp and the moonshine thread

Chomp is a 2-player game, usually played with chocolate bars.

The players take turns in choosing one chocolate block and “eat it”, together with all other blocks that are below it and to its right. There is a catch: the top left block contains poison, so the first player forced to eat it dies, that is, looses the game.

If you start with a rectangular bar, the first player has a winning strategy, though it may take you too long to actually find the correct first move. See this post for the strategy-stealing argument.

If you label the blocks of the rectangular bar by $(a,b)$ with $0 \leq a \leq k$ and $0 \leq b \leq l$, with the poisonous one being $(0,0)$, then this can be viewed as choosing a divisor $d$ of $N=p^k q^l$ and removing all multiples of $d$ from the set of divisors of $N$. The first person forced to name $1$ looses.

This allows for higher dimensional versions of Chomp.

If you start with the set of all divisors of a given natural number $N$, then the strategy-stealing argument shows that the first player has a winning move.

A general position of the game corresponds to a finite set of integers, closed under taking divisors. At each move the player has to choose an element of this set and remove it as well as all its multiples.

The thread of $(N|1)$, relevant in understanding a moonshine group of the form $(n|m)+e,f,\dots$ with $N=n \times h$, consists of all divisors of $N$.

But then, the union of all threads for all 171 moonshine groups is a position in higher dimensional Chomp.

Who wins starting from this moonshine thread?

Perhaps not terribly important, but it forces one to imagine the subgraph of the monstrous moonshine picture on the $97$ number-lattices way better than by its Hasse diagram.

Click on the image for a larger version.

By the way, notice the (slight) resemblance with the ‘monstrous moonshine painting’ by Atria

Here’s how the Hasse diagram of the moonshine thread was produced. These are ‘notes to self’, because I tend to forget such things quickly.

1. Work though the list of 171 moonshine groups in Monstrous Moonshine, pages 327-329. Add to a list all divisors of $N$ for a group of type $N+e,f,\dots$ or $n|h+e,f,\dots$ with $N=n \times h$. This should give you these $97$ integers:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,38,39,40,41,42,44,45,46,47,48,50,51,52,54,55,56,57,59,60,62,
63,64,66,68,69,70,71,72,78,80,84,87,88,90,92,93,94,95,96,104,105,110,112,117,
119,120,126,136,144,160,168,171,176,180,208,224,252,279,288,360,416

2. Let $L$ be this list and use Sage:

P=Poset((L,attrcall("divides")),linear_extension=True)
H=P.hasse_diagram()
H.graphviz_string()

3. Copy the output to a file, say chomp.dot, and remove all new-line breaks from it.

4. Install Graphviz on Mac OS X.

5. In Terminal, type
dot -Tpng chomp.dot -o chomp.png

Leave a Comment

Life on Gaussian primes

At the moment I’m re-reading Siobhan Roberts’ biography of John Horton Conway, Genius at play – the curious mind of John Horton Conway.

In fact, I’m also re-reading Alexander Masters’ biography of Simon Norton, The genius in my basement – the biography of a happy man.

If you’re in for a suggestion, try to read these two books at about the same time. I believe it is beneficial to both stories.

Whatever. Sooner rather than later the topic of Conway’s game of life pops up.

Conway’s present pose is to yell whenever possible ‘I hate life!’. Problem seems to be that in book-indices in which his name is mentioned (and he makes a habit of checking them all) it is for his invention of the game of Life, and not for his greatest achievement (ihoo), the discovery of the surreal numbers.

If you have an hour to spare (btw. enjoyable), here are Siobhan Roberts and John Conway, giving a talk at Google: “On His LOVE/HATE Relationship with LIFE”

By synchronicity I encounter the game of life now wherever I look.

Today it materialised in following up on an old post by Richard Green on G+ on Gaussian primes.

As you know the Gaussian integers $\mathbb{Z}[i]$ have unique factorization and its irreducible elements are called Gaussian primes.

The units of $\mathbb{Z}[i]$ are $\{ \pm 1,\pm i \}$, so Gaussian primes appear in $4$- or $8$-tuples having the same distance from the origin, depending on whether a prime number $p$ remains prime in $\mathbb{Z}[i]$ or splits.

Here’s a nice picture of Gaussian primes, taken from Oliver Knill’s paper Some experiments in number theory

Note that the natural order of prime numbers is changed in the process (look at the orbits of $3$ and $5$ (or $13$ and $17$).

Because the lattice of Gaussian integers is rectangular we can look at the locations of all Gaussian primes as the living cell in the starting position on which to apply the rules of Life.

Here’s what happens after one move (left) and after three moves (right):

Knill has a page where you can watch life on Gaussian primes in action.

Even though the first generations drastically reduce the number of life spots, you will see that there remains enough action, at least close enough to the origin.

Knill has this conjecture:

When applying the game of life cellular automaton to the Gaussian primes, there is motion arbitrary far away from the origin.

What’s the point?

Well, this conjecture is equivalent to the twin prime conjecture for the Gaussian integers $\mathbb{Z}[i]$, which is formulated as

“there are infinitely pairs of Gaussian primes whose Euclidian distance is $\sqrt{2}$.”

2 Comments

The geometry of football

Soon, we will be teaching computational geometry courses to football commentators.

If a player is going to be substituted we’ll hear sentences like: “no surprise he’s being replaced, his Voronoi cell has been shrinking since the beginning of the second half!”

David Sumpter, the author of Soccermatics: Mathematical Adventures in the Beautiful Game, wrote a nice article over at Medium The geometry of attacking football.

As an example, he took an attack of Barcelona against Panathinaikos.


and explained the passing possibilities in terms of the Delaunay triangulation between the Barca-players (the corresponding Voronoi cell decomposition is in the header picture).

He concludes: “It is not only their skill on the ball, but also their geometrically accurate positioning that allows them to make the pass.”

Jaime Sampaoi produced a short video of changing Voronoi cells from kick-off by the blue team, with the red team putting pressure until a faulty pass is given, leading to a red-attack and a goal. All in 29 seconds.



I’d love to turn this feature on when watching an actual game.

Oh, and please different cell-colours for the two teams.

And, a remote control to highlight the Voronoi cell of a particular player.

Please?

One Comment

human-, computer- and fairy-chess

It was fun following the second game last night in real time. Carlsen got a winning endgame with two bishops against a rook, but blundered with 62. Bg4?? (winning was Kf7), resulting in stalemate.

There was this hilarious message around move 60:

“The computer has just announced that white mates in 31 moves. Of course, the only two people in the building who don’t benefit from that knowledge are behind the pieces.”

[section_title text=”Alice’s game from ‘Through the Looking-Glass'”]

The position below comes from the preface of Lewis Carroll’s Through the Looking-Glass



The old notation for files is used:

a = QR (queen’s side rook)
b = QKt (queen’s side knight)
c = QB (queen’s side bishop)
d = Q (queen)
e = K (king)
f = KB (king’s side bishop)
g = KKt (king’s side knight)
h = KR (king’s side rook)

Further, the row-number depends on whose playing (they both count starting from their own side). Here’s an animated version of the game:



And a very strange game it is.

White makes consecutive moves, which is allowed in some versions of fairy chess.

And, as the late Martin Gardner explains in his book The Annotated Alice:

“The most serious violation of chess rules occurs near the end of the
problem, when the White King is placed in check by the Red Queen without
either side taking account of the fact. “Hardly a move has a sane purpose,
from the point of view of chess,” writes Mr. Madan. It is true that both sides
play an exceedingly careless game, but what else could one expect from the
mad creatures behind the mirror? At two points the White Queen passes up
a chance to checkmate and on another occasion she flees from the Red
Knight when she could have captured him. Both oversights, however, are in
keeping with her absent-mindedness.”

In fact, the whole game reflects the book’s story (Alice is the white pawn travelling to the other side of the board), with book-pages associated to the positions listed on the left. Martin Gardner on this:

“Considering the staggering difficulties involved in dovetailing a chess
game with an amusing nonsense fantasy, Carroll does a remarkable job. At
no time, for example, does Alice exchange words with a piece that is not
then on a square alongside her own. Queens bustle about doing things while
their husbands remain relatively fixed and impotent, just as in actual chess
games. The White Knight’s eccentricities fit admirably the eccentric way in
which Knights move; even the tendency of the Knights to fall off their
horses, on one side or the other, suggests the knight’s move, which is two
squares in one direction followed by one square to the right or left. In order
to assist the reader in integrating the chess moves with the story, each move
will be noted in the text at the precise point where it occurs.”

The starting position is in itself an easy chess-problem: white mates in 3, as explained by Gardner:

” It is amusing to note that it is the Red Queen who persuades Alice to advance along her file to the eighth square. The Queen is protecting herself with this advice, for white has at the outset an easy, though inelegant, checkmate in three moves.
The White Knight first checks at KKt.3. If the Red King moves to either Q6
or Q5, white can mate with the Queen at QB3. The only alternative is for
the Red King to move to K4. The White Queen then checks on QB5,
forcing the Red King to K3. The Queen then mates on Q6. This calls, of
course, for an alertness of mind not possessed by either the Knight or
Queen. ”

Leave a Comment