Tag: Golden Ratio

Euclid’s Game

One of the most fundamental algorithms in mathematics is the Euclidean Algorithm to compute (among other things) the greatest common divisor of two numbers. 

Euclid’s Game is a two person strategy game, invented by Cole and Davie in 1969, employing this algorithm, and, maybe not surprisingly, connected to the Golden Ratio. It is played with a pair of positive integers, like (11,27). A move consists of taking away from one number a non-zero multiple of the other number, so that the result is still non-negative.

 

So from (11,27), we can move to either (11,16) or to (11,5).
The players take turns until one number becomes zero, so that the other player is out of moves and has lost.

Here is a complete sample game:

(11,27)➔(11,5)➔(1,5)➔(1,3)➔(1,0)

Below is a way to visualize the possible moves by placing a blue pair (a,b) in a coordinate grid. If a<b, the possible yellow moves are obtained by decreasing the x-coordinate by a, until we get below the x-axis.

Euclid2 moves

We would like to find out when the first player has a winning strategy.

Here is a simple case: If one number is a multiple of the other, the first player can reduce the larger number to 0 and win in a single move. In particular, all pairs (a,a) are a win for the first player. By symmetry, we can from now on restrict our attention to the case that a<b.

How many different moves are possible for the pair (a,b)? We can list the moves (using the floor notation [x] for the largest integer less than or equal to x) as

(a,b-a), (a,b-2a), … , (a,b-[b/a] a),

so there are [b/a] possible moves. You can check this in the diagram above, too.

In many games, it is a good strategy to force the other player’s moves, and this turns out to be the case here as well. The first player should try to reach a pair (a’,b’) with 1< b’/ a’ <2, so that the second player has only one move left.

We will now prove:

Theorem: The first player has a winning strategy if and only if b/a is an integer, or b/a>𝜑, where 𝜑=(√5+1/2) ≈ 1.6180<2 is the Golden Ratio.
In the first case, the player wins by making the larger number 0, in the second case by moving to a position (a’,b’) where 1<b’/a'<2.

Below is a diagram showing all winning pairs (a,b) for the first player with a,b<30 in green. 

Euclid2 30

We first pin down the role of the Golden Ratio.

Lemma: If 1<b/a<𝜑, there is only one move from (a,b), namely to (a’,b’)=(b-a,a), and we have b’/a’>𝜑.

Proof:
We have

Frac a b = frac
so that

Frac b a > fra
In other words, if we can move the other player into the region 1<b/a<𝜑, they are forced to move us back into the claimed winning region b’/a’ >𝜑.

The next lemma tells us when that is possible:

Lemma: Let k be a positive integer.
If k<𝜑+k-1<b/a<k+1, we can move to (a’,b’) = (b-k a, a), and this pair satisfies 1<b’/a'<𝜑. In other words, we subtract the largest amount we are allowed to.

Proof:
We have
Phi 1< frac a b
Taking reciprocals proves the claim.

We will now take care of the remaining possible ratios. Here, we take away one times less than would be allowed:

Lemma: Let k be a positive integer.
If k+1<b/a<𝜑+k, we can move to (a’,b’) = (a, b-k a). From there, only one move is possible, namely to (a”,b”) = (b-(k+1)a, a), and this pair satisfies b”/a”>𝜑.

Proof:
That the chosen move to (a, b-k a) is valid is clear, because the assumptions imply that a<b-ka. Moreover,

Frac b a = fra 1
so there is only one move possible, namely to (a”,b”) = (b-(k+1)a, a). Now we have

Frac a b = f
which proves that a”<b” and that b”/a”>𝜑.

The proof of the theorem now follows by combining the three lemmas.

Euclid3 20b

Life gets more complicated in three dimensions. One can play this game also with triples, allowing to subtract multiples of one number from either of the other two. Above is the set of winning triples in the first octant, marked with small green dots, while the losing positions are big and red. One can see they form a tetrahedral cone, but the cone is not solid, meaning that it probably won’t be as easy to find a simple winning strategy. As an impartial game, Euclid is equivalent to the game of of Nim in any dimension, it’s just not so clear, what the size of the Nim pile is.

What is a Number? (Geometry and Numbers I)

The moment when humans made the abstraction from a set of objects to its cardinality and thus discovered counting is lost in history. There are other moments of similar impact that we know more about. Today, we are so familiar with numbers that we often forget that they are used to measure quantities and even ignore units, confusing distances and durations.

1234

For the early pre-Aristotle Greek mathematicians, lengths were not numbers at all. Numbers occurred as proportions, as ratios of lengths (or durations). One segment could be say twice as long as another segment. More generally, the Greeks called two lengths commensurable if their ratio is, in modern terms, a rational number. They would detect this by fitting one number, like 30, as often as possible (once) into another number (43), take the remainder (13), fit that in the second number (30) as often as possible (twice), take the remainder (4) etc. etc. What emerges is the continued fraction above, terminating eventually, because the denominators get smaller and smaller.

Phi

If the lengths are not commensurable, the continued fraction becomes infinite, like the one above. For the Greeks, this expression was essentially an algorithm. An infinite fraction is a mind boggling thing. How does one even compute it?

Pentagram

Geometrically, this can infinite continued fraction arises by comparing the side length 𝝋 of a regular pentagon to a segment of length 1 of its diagonals. Simple similarity of triangles tells us that 𝝋=1+1/𝝋. Rewriting this once leads to 𝝋=1+1/(1+1/𝝋), and if we keep going a little while longer, we arrive at the infinite continued fraction above. This reproduces how the Greeks proved that the Golden ratio 𝝋 is irrational (if it was rational, the continued fraction would be finite).

Root2b

Similarly, the above dissection of a unit square into a rectangle shows that (√2-1)(√2+1)=1. This is arithmetically easy, but the concept of a root of a number didn’t make sense to the Greeks in the early days. This equation is the essential ingredient to prove the continued fraction expansion of √2 (and thus its irrationality).

Sqrt2

Of course, the standard proof by contradiction that is taught today (and which probably goes back to Aristotle) makes the cumbersome process of finding continued fractions cumbersome. We will see next week that they still serve higher purposes.