The Big Lock-Down Math-Off, Match 8

Welcome to the eighth match in this year’s Big Math-Off. Take a look at the two interesting bits of maths below, and vote for your favourite.

You can still submit pitches, and anyone can enter: instructions are in the announcement post.

Here are today’s two pitches.

Peter Rowlett – Quarto games of different sizes

Peter Rowlett is a maths lecturer at Sheffield Hallam University. You can find him on Twitter at @peterrowlett.

About Quarto

Quarto is a fun, commercially-available game. It’s played on a \(4 \times 4 \) grid. The game pieces are all unique, and have four attributes taking one of two values: colour, height, shape and whether it has a dimple in the top or not.

Since each combination of attributes is used once each, and each can take two values, the game uses \( 2^4=16 \) pieces. This is the same as the number of spaces on the board, which is \( 4 \times 4 = 16 \).

The aim of the game is to be the player who places the fourth piece in a row that matches in at least one attribute (i.e., the fourth tall piece, the fourth dimpled piece, etc.). The twist? You don’t choose your own piece — your opponent chooses the piece you will play, and you choose theirs.

Quarto game size

Let’s say it’s essential for a game of Quarto to have the same number of pieces as spaces on the board. This is so the game can end in a draw with all pieces used and all spaces filled.

This works for the standard Quarto you buy, because there are \( 2^4=16 \) pieces on a board with \( 4 \times 4 = 16 \) spaces.

Using this constraint, we can’t play on an arbitrary-sized board, even if we vary the number of attributes we use. For example, we can’t play on a \( 3 \times 3 \) board, because this would have \( 9 \) spaces but three binary attributes would only generate \( 2^3 = 8 \) pieces.

Stop reading and have a think about what size boards work for valid games? How many pieces would these use?

Rather than thinking about numbers of pieces directly, it helps to think about the number of attributes we have. If we have \(m\) binary attributes (each taking two values), this generates \(2^m\) pieces.

Say we play on an \( n \times n \) board, using pieces which have \( m \) binary attributes. Then we require

\[ n^2 = 2^m \text{.} \]

This can be rearranged to give

\[ m = 2 \log_2(n) \text{,} \]

meaning, for a viable game (i.e. \(m\) and \(n\) as positive integers), we need \(m\) to be even and \(n\) to be a power of \(2\).

For example, we can play Quarto on a \( 8 \times 8 \) board if we use pieces with \(6\) binary attributes, because \( 8^2 = 2^6 \); and we can play Quarto on a \( 128 \times 128 \) board if we use \( 14 \) attributes, because \( 128^2 = 2^{14} \).

Notation for Quarto pieces

How would we arrange a game using more attributes? We could invent new attributes for our game, say making pieces spotty or not, have handles or not, and … You can see that as we increase the number of attributes, we are going to run out of ways to make pieces quite quickly.

One way around this is to invent a notation. Since attributes can take two values, label them \(0\) or \(1\). For example, label the pieces in standard \(4 \times 4 \) Quarto as follows: white (\(0\)), black (\(1\)); short (\(0\)), tall (\(1\)); round (\(0\)), square (\(1\)); dimpled (\(0\)), flat (\(1\)).

Using this labelling in this order, we can represent Quarto pieces as binary strings. For example, \(0100\) would be white, tall, round and dimpled; \(1001\) would be black, short, round and flat-topped. The winning condition is met if four pieces in a line share one digit in common. For example, \(0100\) and \(1001\) are both round, so both have third digit \(0\).

You now have the notation you need to play Quarto with larger numbers of attributes, or in settings where you don’t have a shared game board. I recently enjoyed a game of \( 4 \times 4 \) Quarto over Slack; some years ago I spent a summer playing \( 8 \times 8 \) Quarto via Twitter with a student.

More flexibility

To generalise further, we could think about attributes which have more different values, e.g. three different colours, seven different heights, etc. Say we have \(m\) different attributes each taking one of \(k\) different values, then we have \(k^m\) pieces and require that

\[ k^m = n^2 \text{.} \]

This means we can play using our \( 3 \times 3 \) game board after all, by using two attributes taking each of three values (\(k=3\),\(m=2\)), for:

\[ 3^2 = 3^2 \text{.} \]

Higher-dimensional thinking

But why stop there? Just like we can make 3D Noughts and Crosses by stacking three boards on top of each other to form a cube, and 4D Noughts and Crosses by stacking three cubes on top of each other (in the fourth dimension) to make a hypercube, we can play Quarto in different dimensions.

A Quarto board with side length \(n\) on a board in \(d\) dimensions, would have \(n^d\) spaces.

\[ n^d = k^m \iff m = d\log_k(n) \]

for a valid game, with \(n\), \(d\), \(m\) and \(k\) all positive integers.

So now you can play Quarto on all sorts of boards! Setting \( n = k^p \) to give \( m = dp \) allows viable game configurations to be generated for positive integer \(p\).

For example, playing pieces which have 15 ternary attributes on a \( 27 \times 27 \times 27 \times 27 \times 27 \) 5-cube would use \( 3^{15}=27^5=14,\! 348,\! 907 \) pieces.

For a simpler example, if you have a standard Quarto set, you can play using the standard binary pieces on a \( 2 \times 2 \times 2 \times 2 \) hypercube.

You might wonder how to play on a \( 2 \times 2 \times 2 \times 2 \) hypercube. Here I took inspiration from David Butler’s 4D rules for Noughts and Crosses. Because there are just so many ways to win with lines in 4-dimensions, it seems to make sense to make a plane be a winning move. Visualising planes in 4D is mind-bending, so I present a 4D Quarto worksheet to try to help you through. Take a look, have a play and let me know how you get on!

---

Zeno Rogue – A truly self-referential formula

Zeno Rogue works mostly in theoretical computer science and non-Euclidean geometry. They tweet at @zenorogue, and made the non-Euclidean game HyperRogue.

In Match 2, Sam Shah has shown us the formula known as the Tupper’s self-referential formula.This is a formula which, where we draw its graph at a specific point, can be read as the formula itself.

But is it really self-referential? I would argue that it is not. It is possible to encode all 17 pixel tall pictures made of white and black squares into integer values (by replacing all black squares as 1 and white squares as 0, and considering the result, read column by column, as the binary representation of a number \(k\)). Tupper’s formula works like a decoder: given the number encoding (by looking close to \(k\)), we get back the original picture.

You could say, so what? It can encode anything, so it can be used to draw itself, so it is self-referential! The problem here is that this formula is not self-referential by itself — it can only draw itself when supplied with external information (the correct window of arguments). Being able to produce a copy of self, without external information, is a much more difficult task! Tupper himself did not call his formula self-referential.

Let’s try to encode the data in the formula itself. Let \(\frac{1}{2} < p(x,y)\) be Tupper’s formula, and \(k\) be the value where we get the self-referential window. We could try something as follows:

\[ \frac{1}{2} < p(x,y+k) \wedge y>0 \wedge y<106 \]

Well, did we succeed?

• If we draw the whole graph of this, we can read Tupper’s formula. But this is not exactly the formula above!
• Of course, we can change the value of \(k\), to get another image as a result. We could choose \(k_1\) whichreads the formula above. But it still refers to \(p\) which is not defined!
• Of course we can replace \(p\) by the definition of Tupper’s formula. This will be a bit better, but the formula still does not tell us what \(k_1\) we shall use!
• We can try to replace \(k_1\) in the formula with our current value of \(k_1\), and get a new \(k\) (let’s call it \(k_2\)) whichproduces the formula with \(k_1\). Still not self-referential — as we can easily imagine, \(k_2\) will be a different number than \(k_1\) (it will be greater)!

We can try to continue this process: get a \(k_3\) which displays \(k_2\), then get an \(k_4\) which display \(k_3\), and so on. But that does not help: the \(k\)-number we use will be always greater than the \(k\)-number we get as a result. It appears that we cannot get a truly self-referential formula using this method. But is it really the end? Maybe it is possible by using some other method? If possible, would not it be much more impressive?…

It is a bit difficult to find a truly self-referential formula if we think about numbers and pure mathematics. So let’s move to the programming world, where everything will be easier. In Python we can write a program print(k) which prints whatever is given as k.

This program is very similar to Tupper’s formula: it can output anything, given the correct k. It is “self-referential” in the same sense as Tupper’s formula is: if k is "print(k)", it will print itself. We could attempt to write a program like print("print(k)"), or print("print(\"print(k)\")") — these attempts are similar to the our attempts at making a truly self-referential formula, and fail for similar reasons.

But if we think a bit, we can actually solve this. The trick is that we do not really have to make the value \(k\) include a description of itself! We can have \(k\) which lists the whole program except for the value of \(k\); we can let our program fill the ‘hole’ itself. This works as follows:

  k=   def insert(text, q):    # insert a quotation of q after the second character of text    # return text  s = replace(k, k)  print(s)

except that after “=” we should insert the quotation of the program above. Look, a truly self-referential program! We have left some details as an exercise, but if you do not want to have some programming fun, look here. Such programs are called quines.

Now let’s go back to the world of pure mathematics. Can we use the same trick? It is difficult, but we can! We already have print(s): this is the Tupper’s formula. We have to write a mathematical function ‘replace’ which checks that the two coordinates \(k\) and \(s\) are in the following relation: Tupper’s images of \(k\) and \(s\) are similar, except that \(s\) inserts some extra columns after the column \(i\) which contain a drawing of the number \(k\). This can be done, as follows:

\[ s = k{\rm\ mod\ }2^{17i} + \lfloor k / 2^{17i} \rfloor k \cdot 2^{17i} \cdot 2^{170 \lceil \log_10 k \rceil} + \sum_{j} 2^{17i+170j} d(\lfloor k/10^j\rfloor{\rm\ mod\ }10) 2^{17i} \]

where \(d(0)\) to \(d(9)\) are 10×17 Tupper representations of the digits 0 to 9.

The whole self-referential formula will be:

\[ k=\ \wedge s = k{\rm\ mod\ }2^{17i} + \lfloor k / 2^{17i} \rfloor k \cdot 2^{17i} \cdot 2^{170 \lceil \log_10 k \rceil} + \sum_{j} 2^{17i+170j} d(\lfloor k/10^j\rfloor{\rm\ mod\ }10) 2^{17i} \wedge \frac{1}{2} < p(x,y+s) \wedge y>0 \wedge y < S \]

but where we first replace \(i\) and \(d\) with their correct values, \(S\) by the size, and then we replace \(p\) with Tupper’s formula. After this, we insert the Tupper representation of the obtained formula after \(k=\). And this way, we get a truly self-referential formula!

This puzzle actually has very deep consequences. For example, we can construct a formula \(\phi\) which says that:

“preceded by its own quotation cannot be proven” preceded by its own quotation cannot be proven

Note that \(\phi\) works similar to our quines above: it actually talks about itself! \(\phi\) says that \(\phi\) cannot be proven. It could be false or true. If it was false, this would mean that \(\phi\) could be proven, and hence \(\phi\) would have to be true. So \(\phi\) is a formula which is true but could not be proven. So not everything that is true in mathematics could be proven. (Note: it is very easy to misunderstand Gödel’s theorem — claiming that we understand it after reading this short, popular explanation is definitely not recommended.)

Another consequence of self-reference is the life itself. Live beings are also able to create copies of themselves. If you know a bit about biology, you should recognize the parts of our quine in our cells. The number \(k\) is our genetic code. We have a biological machinery \(p\) which can use the genetic code to create proteins; this machinery can construct a copy of itself, given the correct genetic code. However, this machinery does not construct a copy of the genetic code itself; the genetic code is simply copied using another special biological machinery \(r\). I have read some popular articles about the origin of life, claiming that chemical molecules such as RNA and proteins could appear spontaneously on the young Earth quite easily, and that’s how life was created. But is it really life? I could believe that something like a biological Tupper’s formula could easily appear spontaneously, but to create life, we actually need all three components \(k\), \(p\) and \(r\) at the same time: \(k\) is worthless without \(p\) to copy it, and \(p\) is worthless without \(k\) to describe it. It seems that the spontaneous creation of life is as likely as randomly writing out the self-referential formula above! (But if the universe is infinite, it must happen somewhere!)

---

So, which bit of maths made you say “Aha!” the loudest? Vote:

Note: There is a poll embedded within this post, please visit the site to participate in this post's poll.

The poll closes at 9am BST on the 27th, when the next match starts.

If you’ve been inspired to share your own bit of maths, look at the announcement post for how to send it in. The Big Lockdown Math-Off will keep running until we run out of pitches or we’re allowed outside again, whichever comes first.