How to Solve Our Three John Conway-Inspired Puzzles

Our October Insights puzzle celebrated the work of the legendary mathematician John Horton Conway by inviting you to play with two math questions related to his work and to explore an open-ended game similar to his famous Game of Life. I was delighted with the enthusiastic response from readers.

Here are the puzzles and their solutions:

Puzzle 1: Digital Perfection

There is a mysterious 10-digit decimal number, abcdefghij. Each of the digits is different, and they have the following properties:

• a is divisible by 1
• ab is divisible by 2
• abc is divisible by 3
• abcd is divisible by 4
• abcde is divisible by 5
• abcdef is divisible by 6
• abcdefg is divisible by 7
• abcdefgh is divisible by 8
• abcdefghi is divisible by 9
• abcdefghij is divisible by 10

What’s the number?

The answer is: 3,816,547,290.

Several readers solved this puzzle. Nigix, Pawel Dabrowski, Douglas Felix, Alexandre Tussiot, Paolo Abiuso and Lazar Ilic gave detailed explanations of how it could be done using pen and paper.

To solve this, we need to remember some familiar elementary divisibility shortcuts, from which I’ve derived more specific rules for solving this puzzle.

• A number divisible by 2 is even.
• A number divisible by 10 always ends in 0.
• A number divisible by 5 ends in 5 or 0.
• The sums of the digits of numbers divisible by 3, 6 or 9 are divisible by 3.
• The decimal number formed by the last two digits of any number divisible by 4 is also divisible by 4. If the first digit is odd, the second one is either 2 or 6. If the first digit is even, the second one has to be 0, 4 or 8. (This follows from the fact that the number 20 is divisible by 4, and therefore so are 40, 60, 80 and 100.)
• The decimal number formed by the last three digits of any number divisible by 8 is also divisible by 8. More specifically, if the first digit of the three is even, and the second digit is odd, then the last digit is 2 or 6, and the last two digits must be 16, 32, 56, 72 or 96. (This follows from the fact that 200 is divisible by 8, and therefore so are 400, 600, 800 and 1000.)
• There is no simple rule for divisibility by 7. This has to be checked manually.

Armed with these, let’s solve Conway’s digital perfection puzzle.

• Because b, d, f, h and j must be even, we know that the remaining digits a, c, e, g and i are odd.
• By the rule for 10, j must be 0.
• By the rule for 5, e must be 5.
• By the rules for 3, 6 and 9, a + b + c, d + e + f and g + h + i are all divisible by 3. Since e is 5, the only multiple of three that’s reachable by d + e + f is 15. So d and f must be {2, 8} or {4, 6} in any order.
• By the rules for 4, d must be 2 or 6 since c is odd, so def is either 258 or 654.
• Let’s try def = 258 By the rules for 8, since f is even and g is odd, gh is either 16 or 96, and ghi can only be 963 in order to make g + h + i a multiple of 3. So b has to be 4, and a and c must be {1, 7}, as these are the only digits left. So the first 7 digits must be 1472589 or 7412589, neither of which is divisible by 7. So def cannot equal 258 and must be 654 instead.
• If def is 654, then gh must be 32 or 72, and b is 8. Possible values for ghi are 321, 327, 723 or 729, for which a and c are {7, 9}, {1, 9}, {1, 9} or {1, 3}, respectively.
• This gives eight numbers to check for divisibility by 7, with six different six-digit stems with 654 in the fourth to sixth positions:

7896543, 9876543, 1896543, 1896547, 9816543, 9816547, 1836547 and 3816547. Only the last one is divisible by 7.

• Hence the number is 3,816,547,290

Puzzle 2: The Ambiguous Triangles

There is an isosceles triangle that contains an angle of x degrees. The ratio of the two different lengths of its sides is y. It turns out that not one but two different triangles have the exact same values of x and y!

What are the values of x and y for these two isosceles triangles? What’s special about the triangles, and how do they relate to Conway’s work?

We can find the angle x by applying the law of sines. It says that the ratios of the sides of a triangle divided by the sines of the corresponding angles are equal for all sides:

$latex  \frac{a}{\sin A}$ = $latex  \frac{b}{\sin B}$ = $latex  \frac{c}{\sin C}$

or for a pair of angles and sides,

$latex \frac{a}{b}$ sin B = sin A

Let angle B measure x degrees in both triangles, as a base angle in the first triangle and as an apex angle in the other. This makes the measure of the other angle A = 180 − 2x degrees in the first triangle and 90 − x/2 in the second. We are told that the ratio of the sides (a/b) is equal in both triangles, and angle B is x degrees in both triangles, so the left side of the equation is the same in the two triangles. Therefore,

sin(180 − 2x) = sin(90 − x/2)

But sines of complementary angles are equal, so sin(180 − 2x) equals sin 2x. So we have 2x = 90 − x/2. Solving for x gives x = 36 degrees. So the first triangle has angles of 36, 36 and 108 degrees, and the second has angles of 36, 72 and 72 degrees.

The figure shows how these two types of triangles can mesh together. The large triangle has angles measuring 36, 72 and 72 degrees. It has been divided into two triangles by bisecting the base angle on the left side. The lower triangle is similar to the large triangle, while the upper one is the other type of triangle with angles measuring 36, 36 and 108 degrees.

If the length of the base of the lower triangle (at the right) is 1 unit and the base of the large triangle is P units, then the common ratio of the two different sides is P. This ratio in the large triangle is (P + 1)/P.

Equating the two, we get P = (P + 1)/P or P² = P + 1. The only positive root of this equation is:

$latex  \frac{1+\sqrt{5}}{2}$

which is the golden ratio!

These two triangles are known as Robinson triangles, and they play a huge part in the infinite aperiodic tessellations of the plane known as Penrose tilings. Much of the theory behind these tessellations was developed by Conway and Roger Penrose. Here is one such tiling made entirely of these triangles.

Each blue triangle is one type of Robinson triangle, and each yellow triangle is the other type. A pair of the blue triangles, joined along one of their longer sides forms a figure, which Conway called a kite, and a pair of the yellow triangles joined along one of their shorter sides forms a figure, which he called a dart. A kite and a dart fit together to form a rhombus with angles of 72 and 108 degrees. Kites and darts form the basic units of another kind of Penrose tiling for which Conway proved many interesting theorems about their uncountability, pentagonal symmetry and their other connections to the golden ratio.

Lazar Ilic pointed out the connection of the Robinson triangles to pentagons, and J S illustrated it. With angles of 36, 72 and 108 degrees, the triangles’ connection to pentagons is natural and also allows the triangles to combine in many ways around a vertex.

Douglas Felix pointed out that the golden ratio also appears in the game of Conway’s soldiers, “in the proof that the 5th row of the board can not be achieved by the player.”

Puzzle 3: The Game of Tile

Our final “no-player never-ending” Conway-esque  game, invented by reader Jona Raphael, is played as follows:

You have an infinite plane on which you place square tiles. One at a time, you add new tiles randomly such that each new tile shares at least one edge with a previously placed tile. The probability of a tile being placed in any given location is proportional to the number of edges of previously placed tiles that border that location. We define the “hairiness” (H) or exteriority of any configuration as the number of exposed tile edges divided by the number of tiles.

(For examples and figures, please refer to the original puzzle column.)

I posed some questions to help readers start their own explorations.

1. A new tile may be placed next to a single edge (touching only one tile), at a corner (touching two), inside a “U” (touching three) or inside a hole (touching all four). How does each placement affect the number of exposed edges in the new configuration?

Answer: Single edge: +2; corner (which could also be a “sandwich” or “bridge,” as several readers pointed out): 0; “U”: −2; hole: −4.

2. What are the minimum and maximum values of H, and what kinds of tile patterns do they correspond to? Can you come up with an approximate or exact formula for the maximum and minimum values of Has the number of tiles (n) increases?

Minimum

Perfect squares: If n is a perfect square, the pattern that gives the minimum value of hairiness for its size is a filled square of side a, which has H = 4a/n or 4/a, or 4/$latex  \frac{sqrt[n]}$ where n is the number of tiles in the square.  The value is highest, H = 4, for n = 1. This value approaches 0 as the square gets very large.

Non-squares: If n is not a perfect square, then the minimum H is achieved “by constructing squares layer by layer,” in the words of Lazar Ilic. If a² is the largest square lower than n, then:

Case 1: If (a² + 1) ≤ n ≤ (a² + a) then the minimum H is (4a + 2)/n. You initiate and fill an extra (a + 1)th row of tiles along either the vertical or the horizontal border of the square.

Case 2: If (a² + a + 1) ≤ n ≤ (a² + 2a) then the minimum H is (4a + 4)/n. You initiate and fill another single row along one of the two other perpendicular borders after completing the first (a + 1)th row.

Some readers expected that the minimum value of H would be reached when the configuration attained a disklike shape because a circle has the smallest perimeter for a given area. However, on a square matrix, a “circle” will always have many corners and projections that will tend to increase the perimeter beyond that of squares, whose borders are much smoother.

Maximum

The maximum value for a given number of tiles n is given by a simple line of tiles stuck end to end, which has H = 2 + 2/n. This value approaches 2 for large n.

3. What’s the expected value of H(approximate or exact) for a given value of n?

This is a hard problem, as it requires enumerating all the tilings that can be generated by placing n tiles and then summing their edges weighted by their probability to calculate the expected H. In the table below, the first five expected values are exact, and the rest are approximate, based on the simulation by Philippe C-.

As the table shows, the minimum, maximum and expected values of H are the same for n = 1, 2 and 3.  For very large n, the maximum approaches 2, and the minimum and expected values approach 0 at different rates.

3. Find the smallest tiling that is “balanced,” such that the addition of the next tile is as likely to increase the number of exposed edges as it is to decrease it. Can you find a symmetrical configuration that has this property?

For a tiling to be balanced, the expected number of edges added by placing a new tile must be 0. As we saw, edges are only added by singles (two additional edges with a weight of 1). Corners (and bridges) are neutral, while U’s reduce edges by two (with a weight of 3) and holes reduce edges by four (with a weight of 4). So single edges need to be balanced with U’s and/or holes using the following formulas:

Singles(s) and U’s (u) only: s = 3u
Singles, holes (h) and U’s:  2s = 16h + 6u
Singles and holes only: s = 8h

Here are the smallest tilings for each of the above cases:

4. Find the smallest tiling for which the expected value of Hremains the same after you add one tile. What’s the next-smallest tiling for which this property is true?

The smallest such configuration is a 2-by-2 square, which has four tiles and eight edges, for an H of 2. Adding one tile anywhere gives five tiles and 10 edges, maintaining an H of 2.

The next-smallest tiling, contributed by Lazar Ilic, is the one shown below of size 16 with 24 edges (H = 1.5), with probabilities 3/4 and 1/4 of moving to 26 or staying at 24 edges, respectively. This gives 17 tiles with an expectation of 25.5 edges, maintaining an expected H of 1.5.

Readers explored this game in interesting ways. Ty Rex even took a stab at extending the game to multiple dimensions. Thank you all for contributing. I hope you all had fun.

As for the name of the game, I’ve adopted “Game of Tile,” which was suggested by Glenn Gould as a tribute to Conway.

I would like to recommend Philippe C-’s excellent simulation, which gives you a visual sense of how the configuration grows. It’s available at http://logicien.fr/conway/.

Because of the high probability of filling U’s and holes, the overall shape becomes very blobby and not hairy at all as the number of tiles increases (Ty Rex’s suggested name for the game was “Blob”). At my suggestion, Philippe C- incorporated the ability to assign custom weights to each number of edges, which allows more interesting and hairy configurations to emerge that you can play with in the simulation.

The Quanta Conway prize for this puzzle goes to Lazar Ilic. Congratulations!

See you for new Insights in February 2021. In the meantime, stay safe and have happy holidays.