mathblag

Musings on mathematics and teaching.

Month: October, 2013

Three piles of coins

A recent post by Jim Wilder reminded me of the following problem which I heard many years ago.

There are three piles of coins. You are allowed to move coins from one pile to another, but only if the number of coins in the destination pile is doubled. For example, if the first pile has 6 coins and the second pile has 4 coins, then you may move 4 coins from the first pile to the second pile — no more or less. Prove that by repeating moves of this sort, it is possible to empty one of the piles.

I will post my solution in a few days, but I would like to know the origin of this problem. Does anyone know?

Advertisements

A Somos Sequence

Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation

a_n a_{n-k} = \sum\limits_{i=1}^{\lfloor k/2 \rfloor} a_{n-i} a_{n-k+1}

with initial values a_n = 1 for 0 \le n \le k-1\ .

The first interesting case is k = 4:

a_n a_{n-4} = a_{n-1} a_{n-3} + (a_{n-2})^2

The first 15 terms of the Somos-4 sequence (A006720) are

1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898.

It is easy to prove by induction that a_n is always a positive rational number. It is not at all obvious that a_n is always an integer, but this is true as well. I will present a proof due to Janice Malouf and George Bergman.

Step 1: Four consecutive terms are coprime.

We first show that any four consecutive terms are pairwise coprime. The proof is by induction. It is obvious that the first four terms are pairwise coprime. Assume that a_{n-4}, a_{n-3}, a_{n-2}, a_{n-1} are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) a_n. Then p divides a_n a_{n-4}, so p also divides a_{n-1} a_{n-3} + (a_{n-2})^2. From this we conclude that

p\ |\ a_{n-2} \iff (p\ |\ a_{n-1})\ or \ (p\ |\ a_{n-3})\ .

But p cannot divide two of the terms (a_{n-3}, a_{n-2}, a_{n-1}), because we assumed that they are coprime. Therefore, p divides none of them; so (a_{n-3}, a_{n-2}, a_{n-1}, a_n) are coprime. This completes the induction step.

Step 2: Modular madness!

Direct calculation shows that (at least) the first eight terms are integers. Consider nine consecutive terms

a, b, c, d, e, f, g, h, i

and suppose that the first eight terms are integers. We will show that i is also an integer.

The recurrence yields the following equations.

ae = bd + c^2

bf = ce + d^2

cg = df + e^2

dh = eg + f^2

ei = fh + g^2

Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)

bd + c^2 \equiv 0

f \equiv \dfrac{d^2}{b}

g \equiv \dfrac{df}{c} \equiv \dfrac{d^3}{bc}

h \equiv \dfrac{f^2}{d} \equiv \dfrac{d^4}{b^2d} \equiv \dfrac{d^3}{b^2}

ei \equiv \dfrac{d^5}{b^3} + \dfrac{d^6}{b^2c^2}

Step 3: A lucky factorization.

Observe that we can write the final equation as

ei \equiv \dfrac{d^5}{b^3 c^2} (c^2 + bd).

But c^2 + bd \equiv 0, so ei \equiv 0 \pmod{e}.

This implies that i is an integer.

Inscribed polygons and the Fourier transform

Draw a polygon in the plane. We can construct a new polygon by connecting the midpoints of the original polygon. I will call this the midpoint process. What happens if we repeat this process many times?

Inscribed polygons
It is clear that the polygons are shrinking to a point. We can also observe that the polygons appear to be approaching a limiting shape. I will explain why this is the case, and I will show that (except in very special cases) the limiting shape is an affine regular polygon, i.e. a regular polygon to which a linear transformation has been applied. Since linear transformations carry circles to ellipses, it follows that the limiting shape can be inscribed in an ellipse.

Credit: I learned about this problem from Michael Pershan. Please take a few minutes to read his excellent blog post on the topic, and then come back here. Also, Jason Davies has created a mesmerizing Javascript applet for exploring the midpoint process. The ideas in this post are drawn from the book Mathematical Time Exposures by Isaac J. Schoenberg.

Complex numbers

We will use complex numbers to analyze this problem. Every point in the plane is represented by a unique complex number. Similarly, a polygon with n vertices can be represented by a sequence of n complex numbers.

The equation z^n = 1 has n solutions in the complex plane. They are

1, w, w^2, \ldots w^{n-1}

where w = e^{2\pi i/n} = \cos(2\pi/n) + i \sin(2\pi/n).

If we connect these points with line segments then we produce a regular polygon. This picture shows the six complex solutions to z^6 = 1.

complex hexagon

Star polygons

We can form other polygons by connecting the vertices in different ways.

Let n \ge 3 be a fixed integer. For each integer k between 0 and n-1, let P_k be the following polygon.

P_k = (1, w^k, w^{2k}, \ldots, w^{(n-1)k})

P_1 is a regular polygon, and P_{n-1} is the same polygon with the opposite orientation. The other polygons are star polygons, except when k divides n. If k and n are not coprime, then the polygon has repeated vertices. The following picture shows P_1, P_2, P_3, and P_4 when n = 5.

star polygons

The “polygon” P_0 is rather boring. It consists of the same vertex 1, repeated n times. But we will need P_0 as well!

The discrete Fourier transform

A sequence of complex numbers x_0, x_1, \ldots x_{n-1} is transformed into a new sequence X_0, X_1, \ldots X_{n-1} by the formula

X_k = \sum\limits_{j=0}^{n-1} x_j e^{-2\pi ijk/n}.

This transformation is called the discrete Fourier transform (DFT). It is an essential tool in signal processing and image processing, and it has many other important applications. In signal processing, the Fourier coefficients X_k represent amplitudes, and the indices k are frequencies.

The DFT is an invertible transformation, and the inverse is defined by

x_j = \dfrac1n \sum\limits_{k=0}^{n-1} X_k e^{2\pi ijk/n}.

Applying this to the polygon P = (x_0, x_1, \ldots, x_{n-1}), we obtain

P = \dfrac1n \sum\limits_{k=0}^{n-1} X_k P_k.

In other words, every n-gon can be expressed uniquely as a linear combination of the P_k.

Putting it all together

You might well be wondering what this has to do with the original problem. The key idea is that the midpoint process is very easy to understand when it is applied to a regular polygon or a star polygon. Applying the midpoint process to P_k yields a smaller copy of P_k. Of course, P_0 is unchanged by this process and remains a single point. But note that P_1 and P_{n-1} shrink relatively slowly, and the other P_k shrink more rapidly. See the figure below.

inscribed pentagons

After many iterations, the polygon will look like

aP_0 + bP_1 + cP_{n-1}

because the other components will be negligible.

But we recall that P_1 and P_{n-1} are regular n-gons (with opposite orientations), and multiplication by a fixed complex number is a linear transformation. Therefore,

aP_0 + bP_1 + cP_{n-1}

is an affine regular polygon.

The loophole

There is one special case that needs to be noted. If X_1 and X_{n-1} are both zero, then the limiting shape will not be as described above. For example, if we start with a 5-pointed star, then each iteration will yield a smaller 5-pointed star. But this is an unstable equilibrium. If we perturb the star by moving a vertex by an arbitrarily small amount, then X_1 and X_{n-1} will no longer be zero, and the limiting shape will be an affine regular polygon.