The Game of Googol

Here’s a puzzle from a recent issue of Quanta, an online science magazine:

Puzzle 1: I write down two different numbers that are completely unknown to you, and hold one in my left hand and one in my right. You have absolutely no idea how I generated these two numbers. Which is larger?

You can point to one of my hands, and I will show you the number in it. Then you can decide to either select the number you have seen or switch to the number you have not seen, held in the other hand. Is there a strategy that will give you a greater than 50% chance of choosing the larger number, no matter which two numbers I write down?

At first it seems the answer is no. Whatever number you see, the other number could be larger or smaller. There’s no way to tell. So obviously you can’t get a better than 50% chance of picking the hand with the largest number—even if you’ve seen one of those numbers!

But “obviously” is not a proof. Sometimes “obvious” things are wrong!

It turns out that, amazingly, the answer to the puzzle is yes! You can find a strategy to do better than 50%. But the strategy uses randomness. So, this puzzle is a great illustration of the power of randomness.

If you want to solve it yourself, stop now or read Quanta magazine for some clues—they offered a small prize for the best answer:

• Pradeep Mutalik, Can information rise from randomness?, Quanta, 7 July 2015.

Greg Egan gave a nice solution in the comments to this magazine article, and I’ll reprint it below along with two followup puzzles. So don’t look down there unless you want a spoiler.

I should add: the most common mistake among educated readers seems to be assuming that the first player, the one who chooses the two numbers, chooses them according to some probability distribution. Don’t assume that. They are simply arbitrary numbers.

The history of this puzzle

I’d seen this puzzle before—do you know who invented it? On G+, Hans Havermann wrote:

I believe the origin of this puzzle goes back to (at least) John Fox and Gerald Marnie’s 1958 betting game ‘Googol’. Martin Gardner mentioned it in his February 1960 column in Scientific American. Wikipedia mentions it under the heading ‘Secretary problem’. Gardner suggested that a variant of the game was proposed by Arthur Cayley in 1875.

Actually the game of Googol is a generalization of the puzzle that we’ve been discussing. Martin Gardner explained it thus:

Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size of a googol (1 followed by a hundred 0s) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned.

So, the puzzle I just showed you is the special case when there are just 2 slips of paper. I seem to recall that Gardner incorrectly dismissed this case as trivial!

There’s been a lot of work on Googol. Julien Berestycki writes:

I heard about this puzzle a few years ago from Sasha Gnedin. He has a very nice paper about this

• Alexander V. Gnedin, A solution to the game of Googol, Annals of Probability (1994), 1588–1595.

One of the many beautiful ideas in this paper is that it asks what is the best strategy for the guy who writes the numbers! It also cites a paper by Gnedin and Berezowskyi (of oligarchic fame). 

Egan’s solution

Okay, here is Greg Egan’s solution, paraphrased a bit:

Pick some function such that:

•

•

• is strictly increasing: if then

There are lots of functions like this, for example

Next, pick one of the first player’s hands at random. If the number you are shown is compute Then generate a uniformly distributed random number between 0 and 1. If is less than or equal to guess that is the larger number, but if is greater than guess that the larger number is in the other hand.

The probability of guessing correctly can be calculated as the probability of seeing the larger number initially and then, correctly, sticking with it, plus the probability of seeing the smaller number initially and then, correctly, choosing the other hand.

Say the larger number is and the smaller one is Then the probability of guessing correctly is

This is strictly greater than since so .

So, you have a more than 50% chance of winning! But as you play the game, there’s no way to tell how much more than 50%. If the numbers on the other players hands are very large, or very small, your chance will be just slightly more than 50%.

Followup puzzles

Here are two more puzzles:

Puzzle 2: Prove that no deterministic strategy can guarantee you have a more than 50% chance of choosing the larger number.

Puzzle 3: There are perfectly specific but ‘algorithmically random’ sequences of bits, which can’t predicted well by any program. If we use these to generate a uniform algorithmically random number between 0 and 1, and use the strategy Egan describes, will our chance of choosing the larger number be more than 50%, or not?

But watch out—here come Egan’s solutions to those!

Solutions

Egan writes:

Here are my answers to your two puzzles on G+.

Puzzle 2: Prove that no deterministic strategy can guarantee you have a more than 50% chance of choosing the larger number.

Answer: If we adopt a deterministic strategy, that means there is a function that tells us whether on not we stick with the number x when we see it. If we stick with it, if we swap it for the other number.

If the two numbers are and with then the probability of success will be:

This is exactly the same as the formula we obtained when we stuck with with probability but we have specialised to functions valued in

We can only guarantee a more than 50% chance of choosing the larger number if is monotonically increasing everywhere, i.e. whenever But this is impossible for a function valued in To prove this, define to be any number in such that such an must exist, otherwise would be constant on and hence not monotonically increasing. Similarly define to be any number in such that We then have but

Puzzle 3: There are perfectly specific but ‘algorithmically random’ sequences of bits, which can’t predicted well by any program. If we use these to generate a uniform algorithmically random number between 0 and 1, and use the strategy Egan describes, will our chance of choosing the larger number be more than 50%, or not?

Answer: As Philip Gibbs noted, a deterministic pseudo-random number generator is still deterministic. Using a specific sequence of algorithmically random bits

to construct a number between and means takes on the specific value:

So rather than sticking with with probability for our monotonically increasing function we end up always sticking with if and always swapping if This is just using a function as in Puzzle 2, with:

if

if

So all the same consequences as in Puzzle 2 apply, and we cannot guarantee a more than 50% chance of choosing the larger number.

Puzzle 3 emphasizes the huge gulf between ‘true randomness’, where we only have a probability distribution of numbers and the situation where we have a specific number generated by any means whatsoever.

We could generate using a pseudorandom number generator, radioactive decay of atoms, an oracle whose randomness is certified by all the Greek gods, or whatever. No matter how randomly is generated, once we have it, we know there exist choices for the first player that will guarantee our defeat!

This may seem weird at first, but if you think about simple games of luck you’ll see it’s completely ordinary. We can have a more than 50% chance of winning such a game even if for any particular play we make the other player has a move that ensures our defeat. That’s just how randomness works.

Hexagonal Hyperbolic Honeycombs

This post is just for fun.

Roice Nelson likes geometry, and he makes plastic models of interesting objects using a 3d printer. He recently created some great pictures of ‘hexagonal hyperbolic honeycombs’. With his permission, I wrote about them on my blog Visual Insight. Here I’ve combined those posts into a single more polished article.

But the pictures are the star of the show. They deserve to be bigger than the 450-pixel width of this blog, so please click on them and see the full-sized versions!

The {6,3,3} honeycomb

 

This is the {6,3,3} honeycomb.

How do you build this structure? Take 4 rods and glue them together so their free ends lie at the corners of a regular tetrahedron. Make lots of copies of this thing. Then stick them together so that as you go around from one intersection to the next, following the rods, the shortest possible loop is always a hexagon!

This is impossible in ordinary flat 3-dimensional space. But you can succeed if you work in hyperbolic space, a non-Euclidean space where the angles of a triangle add up to less than 180°. The result is the {6,3,3} honeycomb, shown here.

Of course, this picture has been projected onto your flat computer screen. This distorts the rods, so they look curved. But they’re actually straight… inside curved space.

The {6,3,3} honeycomb is an example of a ‘hyperbolic honeycomb’. In general, a 3-dimensional honeycomb is a way of filling 3d space with polyhedra. It’s the 3-dimensional analogue of a tiling of the plane. Besides honeycombs in 3d Euclidean space, we can also have honeycombs in 3d hyperbolic space. The {6,3,3} honeycomb is one of these.

But actually, when I said a honeycomb is a way of filling 3d space with polyhedra, I was lying slightly. It’s often true—but not in this example!

For comparison, in the {5,3,4} honeycomb, space really is filled with polyhedra:

You can see a lot of pentagons, and if you look carefully you’ll see these pentagons are faces of dodecahedra:

In the honeycomb, these dodecahedra fill hyperbolic space.

But in the {6,3,3} honeycomb, all the hexagons lie on infinite sheets. You can see one near the middle of this picture:

These sheets of hexagons are not polyhedra in the usual sense, because they have infinitely many polygonal faces! So, the {6,3,3} honeycomb is called a paracompact honeycomb.

But what does the symbol {6,3,3} mean?

It’s an example of a Schläfli symbol. It’s defined in a recursive way. The symbol for the hexagon is {6}. The symbol for the hexagonal tiling of the plane is {6,3} because 3 hexagons meet at each vertex. Finally, the hexagonal tiling honeycomb has symbol {6,3,3}, because 3 hexagonal tilings meet at each edge of this honeycomb.

So, we can build a honeycomb if we know its Schläfli symbol. And there’s a lot of information in this symbol.

For example, just as the {6,3} inside {6,3,3} describes the hexagonal tilings inside the {6,3,3} honeycomb, the {3,3} describes the vertex figure of this honeycomb: that is, the way the edges meet at each vertex. {3,3} is the Schläfli symbol for the regular tetrahedron, and in the {6,3,3} honeycomb each vertex has 4 edges coming out, just like the edges going from the center of a tetrahedron to its corners!

The {6,3,4} honeycomb

 

This is the {6,3,4} honeycomb.

How do you build this structure? Make 3 intersecting rods at right angles to each other. Make lots of copies of this thing. Then stick them together so that as you go around from one intersection to the next, following the rods, the shortest possible loop is always a hexagon!

This is impossible in ordinary flat 3-dimensional space. You can only succeed if the shortest possible loop is a square. Then you get the familiar cubic honeycomb, also called the the {4,3,4} honeycomb:

To get hexagons instead of squares, space needs to be curved! You can succeed if you work in hyperbolic space, where it’s possible to create a hexagon whose internal angles are all 90°. In ordinary flat space, only a square can have all its internal angles be 90°.

Here’s the tricky part: the hexagons in the {6,3,4} honeycomb form infinite sheets where 3 hexagons meet at each corner. You can see one of these sheets near the center of the picture. The corners of the hexagons in one sheet lie on a flat plane in hyperbolic space, called a horosphere.

That seems to make sense, because in flat space hexagons can have all their internal angles be 120°… so three can meet snugly at a corner. But I just said these hexagons have 90° internal angles!

Puzzle 1. What’s going on? Can you resolve the apparent contradiction?

The Schläfli symbol of this honeycomb is {6,3,4}, and we can see why using ideas I’ve already explained. It’s made of hexagonal tilings of the plane, which have Schläfli symbol {6,3} because 3 hexagons meet at each vertex. On the other hand, the vertex figure of this honeycomb is an octahedron: if you look at the picture you can can see that each vertex has 6 edges coming out, just like the edges going from the center of an octahedron to its corners. The octahedron has Schläfli symbol {3,4}, since it has 4 triangles meeting at each corner. Take {6,3} and {3,4} and glue them together and you get {6,3,4}!

We can learn something from this. Since this honeycomb has Schläfli symbol {6,3,4}, it has 4 hexagonal tilings meeting at each edge! That’s a bit hard to see from the picture.

All the honeycombs I’ve been showing you are ‘regular’. This is the most symmetrical kind of honeycomb. A flag in a honeycomb is a vertex lying on an edge lying on a face lying on a cell (which could be a polyhedron or an infinite sheet of polygons). A honeycomb is regular if there’s a symmetry sending any flag to any other flag.

The {6,3,3} and {6,3,4} honeycombs are also ‘paracompact’. Remember, this means they have infinite cells, which in this case are the hexagonal tilings {6,3}. There are 15 regular honeycombs in 3d hyperbolic space, of which 11 are paracompact. For a complete list of regular paracompact honeycombs, see:

• Regular paracompact honeycombs, Wikipedia.

The {6,3,5} honeycomb

 

This is the {6,3,5} honeycomb. It’s built from sheets of regular hexagons, and 5 of these sheets meet along each edge of the honeycomb. That explains the Schläfli symbol {6,3,5}.

If you look very carefully, you’ll see 12 edges coming out of each vertex here, grouped in 6 opposite pairs. These edges go out from the vertex to its 12 neighbors, which are arranged like the corners of a regular icosahedron!

In other words, the vertex figure of this honeycomb is an icosahedron. And even if you can’t see this in the picture, you can deduce that it’s true, because {3,5} is the Schläfli symbol for the regular icosahedron, and it’s sitting inside {6,3,5}, at the end.

But now for a puzzle. This is for people who like probability theory:

Puzzle 2. Say you start at one vertex in this picture, a place where edges meet. Say you randomly choose an edge and walk down it to the next vertex… each edge being equally likely. Say you keep doing this. This is the most obvious random walk you can do on the {6,3,5} honeycomb. Is the probability that eventually you get back where you started equal to 1? Or is it less than 1?

If that’s too hard, try the same sort of question with the usual cubical honeycomb in ordinary flat 3d space. Or the square lattice on the plane!

In one dimension, where you just take steps back and forth on the integers, with equal chances of going left or right each time, you have a 100% chance of eventually getting back where you started. But the story works differently in different dimensions—and it also depends on whether space is flat, spherical or hyperbolic.

The {6,3,6} honeycomb

 

This is the {6,3,6} honeycomb. It has a lot of sheets of regular hexagons, and 6 sheets meet along each edge of the honeycomb.

The {6,3,6} honeycomb has a special property: it’s ‘self-dual’. The tetrahedron is a simpler example of a self-dual shape. If we draw a vertex in the middle of each face of the tetrahedron, and draw an edge crossing each edge, we get a new shape with a face for each vertex of the tetrahedron… but this new shape is again a tetrahedron!

If we do a similar thing one dimension up for the {6,3,6} honeycomb, this amounts to creating a new honeycomb with:

• one vertex for each infinite sheet of hexagons in the original honeycomb;

• one edge for each hexagon in the original honeycomb;

• one hexagon for each edge in the original honeycomb;

• one infinite sheet of hexagons for each vertex in the original honeycomb.

But this new honeycomb turns out to be another {6,3,6} honeycomb!

This is hard to visualize, at least for me, but it implies something cool. Just as each sheet of hexagons has infinitely many hexagons on it, each vertex has infinitely many edges going through it.

This self-duality comes from the symmetry of the Schläfli symbol {6,3,6}: if you reverse it, you get the same thing!

Okay. I’ve showed you regular hyperbolic honeycombs where 3, 4, 5, or 6 sheets of hexagons meet along each edge. Sometimes in math patterns go on forever, but sometimes they end—just like life itself. And indeed, we’ve reached the end of something here! You can’t build a regular honeycomb in hyperbolic space with 7 sheets of hexagons meeting at each edge.

Puzzle 3. What do you get if you try?

I’m not sure, but it’s related to a pattern we’ve been seeing. The hexagonal hyperbolic honeycombs I’ve shown you are the ‘big brothers’ of the tetrahedron, the octahedron, the icosahedron and the triangular tiling of the plane! Here’s how it goes:

• You can build a tetrahedron where 3 triangles meet at each corner:

For this reason, the Schläfli symbol of the tetrahedron is {3,3}. You can build a hyperbolic honeycomb where the edges coming out of any vertex go out to the corners of a tetrahedron… and these edges form hexagons. This is the {6,3,3} honeycomb.

• You can build an octahedron where 4 triangles meet at each corner:

The Schläfli symbol of the octahedron is {3,4}. You can build a hyperbolic honeycomb where the edges coming out of any vertex go out to the corners of an octahedron… and these edges form hexagons. This is the {6,3,4} honeycomb.

• You can build an icosahedron where 5 triangles meet at each corner:

The Schläfli symbol of the icosahedron is called {3,5}. You can build a hyperbolic honeycomb where the edges coming out of any vertex go out to the corners of an icosahedron… and these edges form hexagons. This is the {6,3,5} honeycomb.

• You can build a tiling of a flat plane where 6 triangles meet at each corner:

This triangular tiling is also called {3,6}. You can build a hyperbolic honeycomb where the edges coming out of any vertex go out to the corners of a triangular tiling… and these edges form hexagons. This is the {6,3,6} honeycomb.

The last one is a bit weird! The triangular tiling has infinitely many corners, so in the picture here, there are infinitely many edges coming out of each vertex.

But what happens when we get to {6,3,7}? That’s the puzzle.

Coxeter groups

I’ve been telling you about Schläfli symbols, but these are closely related to another kind of code, which is deeper and in many ways better. It’s called a Coxeter diagram. The Coxeter diagram of the {6,3,3} honeycomb is

●—6—o—3—o—3—o

What does this mean? It looks a lot like the Schläfli symbol, and that’s no coincidence, but there’s more to it.

The symmetry group of the {6,3,3} honeycomb is a discrete subgroup of the symmetry group of hyperbolic space. This discrete group has generators and relations summarized by the unmarked Coxeter diagram:

o—6—o—3—o—3—o

This diagram says there are four generators obeying relations encoded in the edges of the diagram:

together with relations

and

Marking the Coxeter diagram in different ways lets us describe many honeycombs with the same symmetry group as the hexagonal tiling honeycomb—in fact, 2⁴ – 1 = 15 of them, since there are 4 dots in the Coxeter diagram! For the theory of how this works, illustrated by some simpler examples, try this old post of mine:

• Symmetry and the Fourth Dimension (Part 9).

or indeed the whole series. The series is far from done; I have a pile of half-written episodes that I need to finish up and publish. This post should, logically, come after all those… but life is not fully governed by logic.

Similar remarks apply to all the hexagonal hyperbolic honeycombs I’ve shown you today:

{6,3,3} honeycomb

●—6—o—3—o—3—o
3 hexagonal tilings meeting at each edge
vertex figure: tetrahedron

 

{6,3,4} honeycomb

●—6—o—3—o—4—o
4 hexagonal tilings meeting at each edge
vertex figure: octahedron

 

{6,3,5} honeycomb

●—6—o—3—o—5—o
5 hexagonal tilings meeting at each edge
vertex figure: icosahedron

 

{6,3,6} honeycomb

●—6—o—3—o—6—o
6 hexagonal tilings meeting at each edge
vertex figure: hexagonal tiling

Finally, one more puzzle, for people who like algebra and number theory:

Puzzle 4. The symmetry group of 3d hyperbolic space, not counting reflections, is . Can you explicitly describe the subgroups that preserve the four hexagonal hyperbolic honeycombs?

For the case of {6,3,3}, Martin Weissman gave an answer on G+:

Well, it’s , of course!

Since he’s an expert on arithmetic Coxeter groups, this must be about right! Theorem 10.2 in this paper he showed me:

• Norman W. Johnson and Asia Ivic Weiss, Quadratic integers and Coxeter Groups, Canad. J. Math. Vol. 51 (1999), 1307–1336.

is a bit more precise. It gives a nice description of the even part of the Coxeter group discussed in this article, that is, the part generated by products of pairs of reflections. To get this group, we start with 2 × 2 matrices with entries in the Eisenstein integers: the integers with a cube root of -1 adjoined. We look at the matrices where the absolute value of the determinant is 1, and then we ‘projectivize’ it, modding out by its center. That does the job!

They call the even part of the Coxeter group [3,3,6]⁺, and they call the group it’s isomorphic to , where is their notation for the Eisenstein integers, also called . The weird little line over the is a notation of theirs: stands for 2 × 2 matrices with determinant 1, but is their notation for 2 × 2 matrices whose determinant has absolute value 1.

Can you say more about this case? What about the other cases?

Geometry Puzzles

Here are four puzzles about areas, in approximate order of increasing difficulty.

Mysteries of the equilateral triangle

Puzzle: Show the area of the orange circle equals the total area of the two blue regions.

In case you’re wondering, the picture above shows an equilateral triangle with a small circle inscribed in it and a big circle circumscribed around it.

The puzzle is easy if you think about it the right way. I never knew this cool fact until last month, when I read this fun free book:

• Brian McCartin, Mysteries of the equilateral triangle.

I’ve given talks on the numbers 5, 8, and 24. I’ve imagined writing a book that had chapters on all my favorite natural numbers, starting with Chapter 0. But it would be very hard to write Chapter 3, since this number has too many interesting properties! McCartin’s book covers a lot of them.

Square the lune to the tune of Claire de Lune

Puzzle: Show the crescent has the same area as the triangle.

Greek mathematicians really wanted to square the circle, by which I mean: use straightedge and compass to first draw a circle and then construct a square with the same area.

In 440 BC, Hippocrates of Chios figured out how to square the above crescent-shaped region, which lies between the circle centered at O and the smaller circle centered at D. So, this region is called the Lune of Hippocrates.

I’ve heard it said that this result gave some Greek geometers hope that the circle could be squared. I’m not sure this is true; Hippocrates himself was probably too smart to be fooled. But in any event, it would have been a false hope. Much later, around 1885, Lindemann and Weierstrass proved that squaring the circle was impossible.

Any crescent-shaped region formed by two circular arcs is called a lune. It’s widely believed that there are only 5 squarable lunes. In other words, there are only 5 shapes of lune constructible by straightedge and compass whose area equals that of a square constructible using straightedge and compass. (Obviously these lunes can come in many different sizes.)

Hippocrates discovered three squarable lunes. Two more were discovered by Martin Johan Wallenius in 1766. A proof that these are the only squarable lunes was given by Tchebatorew and Dorodnow, and summarized by the famous topologist Postnikov:

• M. M. Postnikov, The problem of squarable Lunes, translated from the Russian by Abe Shenitzer, American Mathematical Monthly, 107 (Aug.-Sep. 2000), 645–651.

However, there may be a loophole in this proof: Will Jagy claims that these Russians assumed without proof that the ratio of two angles involved in the construction of the lune is rational. With this assumption, finding a squarable lune amounts to finding a rational number and a constructible number such that

Puzzle: Why should be rational? Do you know the true state of the art here?

(My puzzles include hard questions I don’t know the answer to, and this is one.)

For a nice discussion of the 5 squarable lunes, with pictures, see this page:

• The five squarable lunes, MathPages.

Twice in a blue lune

Puzzle: Show the area of this right triangle equals the total area inside the blue lunes. The outside of each lune is a semicircle. The inside of each lune is part of the circle containing the points A, B, and C.

The circle through all 3 corners of a triangle is called its circumcircle. You can construct the circumcircle using a straightedge and compass, if you want.

Again this is a famous old problem. The two blue lunes here are called the Lunes of Alhazen. This problem was later posed and solve by Leonardo da Vinci!

This puzzle is a lot of fun, so I urge you not to give up—but if you do, you can see da Vinci’s solution here.

The arbelos

Puzzle: show the area of the green shape equals the area of the circle.

The green shape is called an arbelos, which means ‘shoemaker’s knife’ in Greek, since it looks a bit like that. It shows up in Propositions 4-8 of the Book of Lemmas. This book goes back at least to Thābit ibn Qurra, a mathematician, astronomer and physician who live in Baghdad from 826 to 901 AD. Ibn Qurra said the book was written by Archimedes! But nobody is sure.

So, when you do this puzzle, you may be matching wits with Archimedes. But you’ll certainly be sharing some thoughts with Thābit ibn Qurra.

Math has been called the world’s longest conversation. Perhaps this is an exaggeration: people have been passing on stories for a long time. But Babylonians were computing the square root of two back in 1700 BC, probably using techniques that are still interesting today… so it really is remarkable how old mathematics still makes good sense, unlike the old creation myths.

For more on the arbelos try:

• Arbelos, Wikipedia.

and

• Thomas Schoch, Arbelos references, 2013.

For the 15 propositions in the Book of Lemmas, see:

• Book of Lemmas, Wikipedia.

Two semicircles is half a circle

Puzzle: show the total area of the two semicircles is half the area of the large circle.

Amazingly, it seems this fact was noticed only in 2011:

• Andrew K. Jobbings, Two semicircles fill half a circle, The Mathematical Gazette 95 (Nov. 2011), 538–540.

However, Andrew Jobbings is a genius when it comes to ‘recreational mathematics’. For more of his work, check out this page:

• Andrew Jobbings, Arbelos.

I learned about this puzzle from Alexander Bogomolny, who has a wonderful website full of Javascript geometry demonstrations:

• Alexander Bogomolny, A property of semicircles.

You’ll get a scary warning asking “Do you want to run this application?” Say yes. You’ll get an applet that lets you slide the point where the semicircles touch: no matter where it is, the semicircles have the same total area! Click “hint” and you’ll get a hint. If you’re still stuck, and too impatient to solve the puzzle yourself, scroll down and see a proof!

However, that proof is long and confusing. With geometry I like demonstrations where after some thought you can simply see that the result is true. For this puzzle, such a demonstration was provided by Greg Egan.

Click here if you give up on this puzzle and want to see Egan’s solution. You may need to ponder it a bit, but when you’re done you should say “yes, this result is clear!”

As a separate hint: the answers to this puzzle and the previous one are similar, in a very nice way!

An Entropy Challenge

If you like computer calculations, here’s a little challenge for you. Oscar Dahlsten may have solved it, but we’d love for you to check his work. It’s pretty important for the foundations of thermodynamics, but you don’t need to know any physics or even anything beyond a little algebra to tackle it! First I’ll explain it in really simple terms, then I’ll remind you a bit of why it matters.

We’re looking for two lists of nonnegative numbers, of the same length, listed in decreasing order:

that sum to 1:

and that obey this inequality:

for all (ignoring ), yet do not obey these inequalities:

for all

Oscar’s proposed solution is this:

Can you see if this works? Is there a simpler example, like one with lists of just 3 numbers?

This question came up near the end of my post More Second Laws of Thermodynamics. I phrased the question with a bit more jargon, and said a lot more about its significance. Suppose we have two probability distributions on a finite set, say and We say majorizes if

for all when we write both lists of numbers in decreasing order. This means is ‘less flat’ than , so it should have less entropy. And indeed it does: not just for ordinary entropy, but also for Rényi entropy! The Rényi entropy of is defined by

where or . We can also define Rényi entropy for by taking a limit, and at we get the ordinary entropy

The question is whether majorization is more powerful than Rényi entropy as a tool to to tell when one probability distribution is less flat than another. I know that if majorizes its Rényi entropy is less than than that of for all Your mission, should you choose to accept it, is to show the converse is not true.

Tidbits of Geometry

Since I grew up up reading Martin Gardner, I’ve often imagined it would be fun to write about math and physics in a way that nonexperts might enjoy. Right now I’m trying my hand at this on Google+. You can read that stuff here.

Google+ encourages brevity—not as much as Twitter, but more than a blog. So I’m posting things that feature a single catchy image, a brief explanation, and URL’s to visit for more details.

Lately I’ve been talking about geometry. I realized that these posts could be cobbled together into a kind of loose ‘story’, so here it is. I couldn’t resist expanding the posts a bit, but the only really new stuff is more about Leonardo Da Vinci and the golden ratio, and five puzzles—only one of which I know the answer to!

The golden ratio

Sure, the golden ratio, Φ = (√5+1)/2, is cool… but if you think ancient Greeks ran around in togas talking about the “golden ratio” and writing it as “Φ”, you’re wrong. This number was named Φ after the Greek sculptor Phidias only in 1914, in a book called The Curves of Life by the artist Theodore Cook. And it was Cook who first started calling 1.618… the golden ratio. Before him, 1/Φ = 0.618… was called the golden ratio! Cook dubbed this number “φ”, the lower-case baby brother of Φ.

In fact, the whole “golden” terminology can only be traced back to 1826, when it showed up in a footnote to a book by one Martin Ohm, brother of Georg Ohm—the guy with the law about resistors. Before then, a lot of people called 1/Φ the “Divine Proportion”. And the guy who started that was Luca Pacioli, a pal of Leonardo da Vinci who translated Euclid’s Elements. In 1509, Pacioli published a 3-volume text entitled De Divina Proportione, advertising the virtues of this number.

Greek texts seem remarkably quiet about this number. The first recorded hint of it is Proposition 11 in Book II of Euclid’s Elements. It also shows up elsewhere in Euclid, especially Proposition 30 of Book VI, where the task is “to cut a given finite straight line in extreme and mean ratio”, meaning a ratio A:B such that A is to B as B is to A+B. This is later used in Proposition 17 of Book XIII to construct the pentagonal face of a regular dodecahedron.

The regular pentagon, and the pentagram inside it, is deeply connected to the golden ratio. If you look carefully, you’ll see no fewer than twenty long skinny isosceles triangles, in three different sizes but all the same shape!

They’re all ‘golden triangles’: the short side is φ times the length of the long sides.

And the picture here lets us see that φ is to 1 as 1 is to 1+φ. A little algebra then gives

which you can solve to get

and thus

For more, see:

• John Baez, Tales of the Dodecahedron.

Da Vinci and the golden ratio

Did Leonardo da Vinci use the golden ratio in his art? It would cool if he did. Unfortunately, attempts to prove it by drawing rectangles on his sketches and paintings are unconvincing. Here are three attempts you can see on the web; click for details if you want:

The first two make me less inclined to believe Da Vinci was using the golden ratio, not more. The last one, the so-called
Vitruvian Man, looks the most convincing, but only if you take on faith that the ratio being depicted is really the golden ratio!

Puzzle 1. Carefully measure the ratio here and tell us what you get, with error bars on your result.

It would be infinitely more convincing if Da Vinci had written about the golden ratio in his famous notebooks. But I don’t think he did. If he didn’t, that actually weighs against the whole notion.

Indeed, I thought the whole notion was completely hopeless until I discovered that Da Vinci did the woodcuttings for Pacioli’s book De Divina Proportione. And even lived with Pacioli while this project was going on! So, we can safely assume Da Vinci knew what was in this book.

It consists of 3 separate volumes. First a volume about the golden ratio, polygons, and perspective. Then one about the ideas of Vitruvius on math in architecture. (Apparently Vitruvius did not discuss the golden ratio.) Then one that’s mainly an Italian translation of Piero della Francesca’s Latin writings on polyhedra.

De Divina Proportione was popular in its day, but only two copies of the original edition survive. Luckily, it’s been scanned in!

• Luca Pacioli, De Divina Proportione.

The only picture I see that might be about using the golden ratio to draw the human figure is this:

The rectangles don’t look very ‘golden’! But the really important thing is to read the text around this picture, or for that matter the whole book. Unfortunately my Renaissance Italian is… ahem… a bit rusty. The text has been translated into German but apparently not English.

Puzzle 2. What does Luca Pacioli say on this page?

The picture above is on page 70 of the scanned-in file. Of course some scholar should have written a paper about this already… I just haven’t gotten around to searching the literature.

By the way, here’s something annoying. This picture on the Wikipedia article about De Divina Proportione purports to come from that book:

Again most of the rectangles don’t look very golden, even though it says “Divina Proportio” right on top. But here’s the big problem: I can’t find it in the online version of the book! Luca Luve, who spotted the online version for me in the first place, concurs.

Puzzle 3. Where is it really from?

Luca Pacioli

Luca Pacioli had many talents: besides books on art, geometry and mathematics, he also wrote the first textbook on double-entry bookkeeping! This portrait of him multitasking gives some clue as to how he accomplished so much. He seems to be somberly staring at a hollow glass cuboctahedron half-filled with water while simultaneously drawing something completely different and reading a book:

Note the compass and the regular dodecahedron. The identity of the other figure in the painting is uncertain, and so is that of the painter, though people tend to say it’s Jacopo de’ Barbari.

Piero della Francesca

This creepy painting shows three people calmly discussing something while Jesus is getting whipped in the background. It’s one of the first paintings to use mathematically defined rules of perspective, and it’s by Piero della Francesca, the guy whose pictures of polyhedra fill the third part of Pacioli’s De Divina Proportione.

Piero della Francesca seems like an interesting guy: a major artist who actually quit painting in the 1470’s to focus on the mathematics of perspective and polyhedra. If you want to know how to draw a perfect regular pentagon in perpective using straightedge and compass, he’s your guy.

Constructing the pentagon

I won’t tell you how to do it in perspective, but here’s how to construct a regular pentagon with straightedge and compass:

Just pay attention to how it starts. Say the radius of the circle is 1. We bisect it and get a segment of length 1/2, then consider a segment at right angles of length 1. But

so these are the sides of a right triangle whose hypotenuse has length √5/2, by the Pythagorean theorem!

Yes, I know I didn’t explain the whole construction… just the start. But the golden ratio is √5/2 + 1/2, so we’ve clearly on the right track. If you’re ever stuck on a desert island with nothing to do but lots of sand and some branches, you can figure out the rest yourself.

Or if you’ve got the internet on your desert island, read this:

• Pentagon, Wikipedia.

But here’s the easy way to make a regular pentagon: just tie a simple overhand knot in a strip of paper!

The pentagon-decagon-hexagon identity

The most bizarre fact in Euclid’s Elements is Proposition XIII.10. Take a circle and inscribe a regular pentagon, a regular hexagon, and a regular decagon. Take the edges of these shapes, and use them as the sides of a triangle. Then this is a right triangle!

How did anyone notice this??? It’s long been suspected that this fact first came up in studying the icosahedron. But nobody gave a proof using the icosahedron until I posed this as a challenge and Greg Egan took it up. The hard part is showing that the two right triangles here are congruent:

Then AB is the side of the pentagon, BC is the side of the decagon and AC’ is the radius of the circle itself, which is the side of the hexagon!

For details, see:

• John Baez, This Week’s Finds in Mathematical Physics (Week 283).

and

• Pentagon-decagon-hexagon identity, nLab.

The octahedron and icosahedron

Platonic solids are cool. A regular octahedron has 12 edges. A regular icosahedron has 12 vertices. Irrelevant coincidence? No! If you cleverly put a dot on each edge of the regular octahedron, you get the vertices of a regular icosahedron! But it doesn’t work if you put the dot right in the middle of the edge—you have to subdivide the edge in the exactly correct ratio. Which ratio? The golden ratio!

This picture comes from R. W. Gray.

According to Coxeter’s marvelous book Regular Polytopes, this fact goes back at least to an 1873 paper by a fellow named Schönemann.

Puzzle 4. What do you get if you put each dot precisely in the center of the edge?

The heptagon

The golden ratio Φ is great, but maybe it’s time to move on? The regular pentagon’s diagonal is Φ times its edge, and a little geometry shows the ratio of 1 to Φ equals the ratio of Φ to Φ+1. What about the regular heptagon? Here we get two numbers, ρ and σ, which satisfy four equations, written as ratios below! So, for example, the ratio of 1 to ρ equals the ratio of ρ to 1+σ, and so on.

For more see:

• Peter Steinbach, Golden fields: a case for the heptagon, Mathematics Magazine 70 (Feb., 1997), 22-31.

He works out the theory for every regular polygon. So, it’s not that the fun stops after the pentagon: it just gets more sophisticated!

Constructing the heptagon

You can’t use a straightedge and compass to construct a regular heptagon. But here’s a construction that seems to do just that!

If you watch carefully, the seeming paradox is explained. For more, see:

• Heptagon, Wikipedia.

Trisecting the angle

When I was a kid, my uncle wowed me by trisecting an angle. He wasn’t a crackpot: he was bending the usual rules! He marked two dots on the ruler, A and B below, whose distance equaled the radius of the circle, namely OB. Then the trick below makes φ one third of θ.

Drawing dots on your ruler is called neusis, and the ancient Greeks knew about it. You can also use it to double the cube and construct a regular heptagon—impossible with a compass and straightedge if you’re don’t draw dots on it. Oddly, it fell out of fashion. Maybe purity of method mattered more than solving lots of problems?

Nowadays we realize that if you only have a straightedge, you can only solve linear equations. Adding a compass to your toolkit lets you also take square roots, so you can solve quadratic equations. Adding neusis on top of that lets you take cube roots, which—together with the rest—lets you solve cubic equations. A fourth root is a square root of a square root, so you get those for free, and in fact you can even solve all quartic equations. But you can’t take fifth roots.

Puzzle 5. Did anyone ever build a mechanical gadget that lets you take fifth roots, or maybe even solve general quintics?

Archimedean Tilings and Egyptian Fractions

Ever since I was a kid, I’ve loved Archimedean tilings of the plane: that is, tilings by regular polygons where all the edge lengths are the same and every vertex looks alike. Here’s my favorite:

There are also 11 others, two of which are mirror images of each other. But how do we know this? How do we list them all and be sure we haven’t left any out?

The interior angle of a regular -sided polygon is obviously

since it’s a bit less than 180 degrees, or and how much?— well, times a full turn, or But these ‘s are getting annoying: it’s easier to say ‘a full turn’ than write Then we can say the interior angle is

times a full turn.

Now suppose we have an Archimedean tiling where polygons meet: one with sides, one with sides, and so on up to one with sides. Their interior angles must add up to a full turn. So, we have

or

or

So: to get an Archimedean tiling you need n whole numbers whose reciprocals add up to one less than n/2.

Looking for numbers like this is a weird little math puzzle. The Egyptians liked writing numbers as sums of reciprocals, so they might have enjoyed this game if they’d known it. The tiling I showed you comes from this solution:

since it has 3 polygons meeting at each vertex: a 4-sided one, a 6-sided one and a 12-sided one.

Here’s another solution:

It gives us this tiling:

Hmm, now I think this one is my favorite, because my eye sees it as a bunch of linked 12-sided polygons, sort of like chain mail. Different tilings make my eyes move over them in different ways, and this one has a very pleasant effect.

Here’s another solution:

This gives two Archimedean tilings that are mirror images of each other!

Of course, whether you count these as two different Archimedean tilings or just one depends on what rules you choose. And by the way, people usually don’t say a tiling is Archimedean if all the polygons are the same, like this:

They instead say it’s regular. If modern mathematicians were inventing this subject, we’d say regular tilings are a special case of Archimedean tilings—but this math is all very old, and back then mathematicians treated special cases as not included in the general case. For example, the Greeks didn’t even consider the number 1 to be a number!

So here’s a fun puzzle: classify the Archimedean tilings! For starters, you need to find all ways to get whole numbers whose reciprocals add up to one less than . That sounds hard, but luckily it’s obvious that

since an equilateral triangle has the smallest interior angle, of any regular polygon, and you can only fit 6 of them around a vertex. If you think a bit, you’ll see this cuts the puzzle down to a finite search.

But you have to be careful, since there are some solutions that don’t give Archimedean tilings. As usual, the number 5 causes problems. We have

but there’s no way to tile the plane so that 2 regular pentagons and 1 regular decagon meet at each vertex! Kepler seems to have tried; here’s a picture from his book Harmonices Mundi:

It works beautifully at one vertex, but not for a tiling of the whole plane. To save the day he had to add some stars, and some of the decagons overlap! The Islamic tiling artists, and later Penrose, went further in this direction.

If you get stuck on this puzzle, you can find the answer here:

• Michal Krížek, Jakub Šolc, and Alena Šolcová, Is there a crystal lattice possessing five-fold symmetry?, AMS Notices 59 (January 2012), 22-30.

• Combinations of regular polygons that can meet at a vertex, Wikipedia.

Not enough?

In short, all Archimedean tilings of the plane arise from finding whole numbers whose reciprocals sum to But what if the total is not enough? Don’t feel bad: you might still get a tiling of the hyperbolic plane. For example,

so you can’t tile the plane with 3 heptagons meeting at each corner… but you still get this tiling of the hyperbolic plane:

which happens to be related to a wonderful thing called Klein’s quartic curve.

You don’t always win… but sometimes you do, so the game is worth playing. For example,

so you have a chance at a tiling of the hyperbolic plane where five equilateral triangles and a square meet at each vertex. And in this case, you luck out:

For more beautiful pictures like these, see:

• Uniform tilings in hyperbolic plane, Wikipedia.

• Don Hatch, Hyperbolic tesselations.

Too much?

Similarly, if you’ve got reciprocals that add up to more than , you’ve got a chance at tiling the sphere. For example,

and in this case we luck out and get the snub dodecahedron. I thought it was rude to snub a dodecahedron, but apparently not:

These tilings of the sphere are technically called Archimedean solids and (if all the polygons are the same) Platonic solids. Of these, only the snub dodecahedron and the ‘snub cube’ are different from their mirror images.

Fancier stuff

In short, adding up reciprocals of whole numbers is related to Archimedean tilings of the plane, the sphere and the hyperbolic plane. But this is also how Egyptians would write fractions! In fact they even demanded that all the reciprocals be distinct, so instead of writing 2/3 as , they’d write

It’s a lousy system—doubtless this is why King Tut died so young. But forget about the restriction that the reciprocals be distinct: that’s silly. If you can show that for every the number can be written as for whole numbers you’ll be famous! So far people have ‘only’ shown it’s true for up to a hundred trillion:

• Erdös–Straus conjecture, Wikipedia.

So, see if you can do better! But if you’re into fancy math, a less stressful activity might be to read about Egyptian fractions, tilings and ADE classifications:

• John Baez, This Week’s Finds in Mathematical Physics (Week 182).

This only gets into ‘Platonic’ or ‘regular’ tilings, not the more general ‘Archimedean’ or ‘semiregular’ ones I’m talking about today—so the arithmetic works a bit differently.

For the special magic arising from

see:

• John Baez, 42.

In another direction, my colleague Julie Bergner has talked about how they Egyptian fractions show up in the study of ‘groupoid cardinality’:

• Julie Bergner, Groupoids and Egyptian fractions.

So, while nobody uses Egyptian fractions much anymore, they have a kind of eerie afterlife. For more on what the Egyptians actually did, try these:

• Ron Knott, Egyptian fractions.

• Egyptian fractions, Wikipedia.

Babylon and the Square Root of 2

joint with Richard Elwes

Sometimes you can learn a lot from an old piece of clay. This is a Babylonian clay tablet from around 1700 BC. It’s known as “YBC7289”, since it’s one of many in the Yale Babylonian Collection.

It’s a diagram of a square with one side marked as having length 1/2. They took this length, multiplied it by the square root of 2, and got the length of the diagonal. And our question is: what did they really know about the square root of 2?

Questions like this are tricky. It’s even hard to be sure the square’s side has length 1/2. Since the Babylonians used base 60, they thought of 1/2 as 30/60. But since they hadn’t invented anything like a “decimal point”, they wrote it as 30. More precisely, they wrote it as this:

Take a look.

So maybe the square’s side has length 1/2… but maybe it has length 30. How can we tell? We can’t. But this tablet was probably written by a beginner, since the writing is large. And for a beginner, or indeed any mathematician, it makes a lot of sense to take 1/2 and multiply it by to get .

Once you start worrying about these things, there’s no end to it. How do we know the Babylonians wrote 1/2 as 30? One reason is that they really liked reciprocals. According to Jöran Friberg’s book A Remarkable Collection of Babylonian Mathematical Texts, there are tablets where a teacher has set some unfortunate student the task of inverting some truly gigantic numbers such as 3²⁵ · 5. They even checked their answers the obvious way: by taking the reciprocal of the reciprocal! They put together tables of reciprocals and used these to tackle more general division problems. To calculate they would break up into factors, look up the reciprocal of each, and take the product of these together with . This is cool, because modern algebra also sees reciprocals as logically preceding division, even if most non-mathematicians disagree!

So, we know from tables of reciprocals that Babylonians wrote 1/2 as 30. But let’s get back to our original question: what did they know about ?

On this tablet, they used the value

This is an impressively good approximation to

But how did they get this approximation? Did they know it was just an approximation? And did they know is irrational?

There seems to be no evidence that they knew about irrational numbers. One of the great experts on Babylonian mathematics, Otto Neugebauer, wrote:

… even if it were only due to our incomplete knowledge of the sources that we assume that the Babylonians did not know that had no solution in integer numbers and , even then the fact remains that the consequences of this result were never realized.

But there is evidence that the Babylonians knew their figure was just an approximation. In his book The Crest of the Peacock, George Gheverghese Joseph points out that a number very much like this shows up at the fourth stage of a fairly obvious recursive algorithm for approximating square roots! The first three approximations are

and

The fourth is

but if you work it out to 3 places in base 60, as the Babylonians seem to have done, you’ll get the number on this tablet!

The number 577/408 also shows up as an approximation to in the Shulba Sutras, a collection of Indian texts compiled between 800 and 200 BC. So, Indian mathematicians may have known the same algorithm.

But what is this algorithm, exactly? Joseph describes it, but Sridhar Ramesh told us about an easier way to think about it. Suppose you’re trying to compute the square root of 2 and you have a guess, say . If your guess is exactly right then

so

But if your guess isn’t right, won’t be quite equal to . So it makes sense to take the average of and , and use that as a new guess. If your original guess wasn’t too bad, and you keep using this procedure, you’ll get a sequence of guesses that converges to . In fact it converges very rapidly: at each step, the number of correct digits in your guess will approximately double!

Let’s see how it goes. We start with an obvious dumb guess, namely 1. Now 1 sure isn’t equal to 2/1, but we can average them and get a better guess:

Next, let’s average 3/2 and 2/(3/2):

We’re doing the calculation in painstaking detail for two reasons. First, we want to prove that we’re just as good at arithmetic as the ancient Babylonians: we don’t need a calculator for this stuff! Second, a cute pattern will show up if you pay attention.

Let’s do the next step. Now we’ll average 17/12 and 2/(17/12):

Do you remember what 17 times 17 is? No? That’s bad. It’s 289. Do you remember what 12 times 24 is? Well, maybe you remember that 12 times 12 is 144. So, double that and get 288. Hmm. So, moving right along, we get

which is what the Babylonians seem to have used!

Do you see the cute pattern? No? Yes? Even if you do, it’s good to try another round of this game, to see if this pattern persists. Besides, it’ll be fun to beat the Babylonians at their own game and get a better approximation to .

So, let’s average 577/408 and 2/(577/408):

Do you remember what 577 times 577 is? Heh, neither do we. In fact, right now a calculator is starting to look really good. Okay: it says the answer is 332,929. And what about 816 times 408? That’s 332,928. Just one less! And that’s the pattern we were hinting at: it’s been working like that every time. Continuing, we get

So that’s our new approximation of , which is even better than the best known in 1700 BC! Let’s see how good it is:

So, it’s good to 11 decimals!

What about that pattern we saw? As you can see, we keep getting a square number that’s one more than twice some other square:

and so on… at least if the pattern continues. So, while we can’t find integers and with

because is irrational, it seems we can find infinitely many solutions to

and these give fractions that are really good approximations to . But can you prove this is really what’s going on?

We’ll leave this as a puzzle in case you’re ever stuck on a desert island, or stuck in the deserts of Iraq. And if you want even more fun, try simplifying these fractions:

and so on. Some will give you the fractions we’ve seen already, but others won’t. How far out do you need to go to get 577/408? Can you figure the pattern and see when 665,857/470,832 will show up?

If you get stuck, it may help to read about Pell numbers. We could say more, but we’re beginning to babble on.

References

You can read about YBC7289 and see more photos of it here:

• Duncan J. Melville, YBC7289.

• Bill Casselman, YBC7289.

Both photos in this article are by Bill Casselman.

If you want to check that the tablet really says what the experts claim it does, ponder these pictures:

The number “1 24 51 10” is base 60 for

and the number “42 25 35” is presumably base 60 for what you get when you multiply this by 1/2 (we were too lazy to check). But can you read the clay tablet well enough to actually see these numbers? It’s not easy.

For a quick intro to what Babylonian mathematicians might have known about the Pythagorean theorem, and how this is related to YBC7289, try:

• J. J. O’Connor and E. F. Robertson, Pythagoras’s
theorem in Babylonian mathematics.

We got our table of Babylonian numerals from here:

• J. J. O’Connor and E. F. Robertson, Babylonian numerals.

For more details, try:

• D. H. Fowler and E. R. Robson, Square root approximations in Old Babylonian mathematics: YBC 7289 in context, Historia Mathematica 25 (1998), 366–378.

We also recommend this book, an easily readable introduction to the history of non-European mathematics that discusses YBC7289:

• George Gheverghese Joseph, The Crest of the Peacock: Non-European Roots of Mathematics, Princeton U. Press, Princeton, 2000.

To dig deeper, try these:

• Otto Neugebauer, The Exact Sciences in Antiquity, Dover Books, New York, 1969.

• Jöran Fridberg, A Remarkable Collection of Babylonian Mathematical Texts, Springer, Berlin, 2007.

---

Here a sad story must indeed be told. While the field work has been perfected to a very high standard during the last half century, the second part, the publication, has been neglected to such a degree that many excavations of Mesopotamian sites resulted only in a scientifically executed destruction of what was left still undestroyed after a few thousand years. – Otto Neugebauer.