That is all.
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?
Somos sequences are sequences that are defined by certain nonlinear recurrence relations. The Somos-k sequence obeys the recurrence relation
with initial values for
The first interesting case is :
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 is always a positive rational number. It is not at all obvious that 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 are pairwise coprime for some n, and let p be a a prime divisor of (the numerator of) . Then p divides , so p also divides . From this we conclude that
But p cannot divide two of the terms , because we assumed that they are coprime. Therefore, p divides none of them; so 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
and suppose that the first eight terms are integers. We will show that i is also an integer.
The recurrence yields the following equations.
Reducing the equations modulo e yields the following equations. (The divisions are allowed because b, c, d, and e are coprime.)
Step 3: A lucky factorization.
Observe that we can write the final equation as
But , so .
This implies that i is an integer.
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?
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.
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 has n solutions in the complex plane. They are
If we connect these points with line segments then we produce a regular polygon. This picture shows the six complex solutions to .
We can form other polygons by connecting the vertices in different ways.
Let be a fixed integer. For each integer between 0 and , let be the following polygon.
is a regular polygon, and is the same polygon with the opposite orientation. The other polygons are star polygons, except when divides . If and are not coprime, then the polygon has repeated vertices. The following picture shows , and when .
The “polygon” is rather boring. It consists of the same vertex 1, repeated n times. But we will need as well!
A sequence of complex numbers is transformed into a new sequence by the formula
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 represent amplitudes, and the indices are frequencies.
The DFT is an invertible transformation, and the inverse is defined by
Applying this to the polygon , we obtain
In other words, every n-gon can be expressed uniquely as a linear combination of the .
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 yields a smaller copy of . Of course, is unchanged by this process and remains a single point. But note that and shrink relatively slowly, and the other shrink more rapidly. See the figure below.
After many iterations, the polygon will look like
because the other components will be negligible.
But we recall that and are regular n-gons (with opposite orientations), and multiplication by a fixed complex number is a linear transformation. Therefore,
is an affine regular polygon.
There is one special case that needs to be noted. If and 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 and will no longer be zero, and the limiting shape will be an affine regular polygon.
A real function is said to be periodic if there exists a real number so that for all . The number is said to be a period of the function. The most familiar examples of periodic functions are the trigonometric functions sine, cosine, and tangent.
Note that if is a period of a function, then are also periods. If a periodic function is continuous and nonconstant, then it has a least period, and all other periods are positive integer multiples of the least period.
There are discontinuous periodic functions that have no least period. The most famous example is the Dirichlet function, defined by if is rational, if is irrational. Every positive rational number is a period of the Dirichlet function, so there is no least period.
Sums of periodic functions are often periodic
The sum of two periodic functions is often periodic, but not always. Suppose that is periodic with least period , and is periodic with least period . If and have a common multiple , then is periodic with period . However, is not necessarily the least period of . To give an extreme example, has no least period.
Some readers may have heard of biorhythm theory, which was popular in the 1970s. The theory claims that humans are influenced by three fundamental cycles: a physical cycle of 23 days, an emotional cycle of 28 days, and an intellectual cycle of 33 days. These cycles are usually modeled as sine waves that start on one’s day of birth. We might suppose that a person’s happiness on day x is the sum of these three cycles.
The figure shows a portion of the graph of this function. It appears to be quite irregular but in fact it repeats every 21,252 days, since 21,252 is the least common multiple of 23, 28, and 33. (View this graph on Desmos.)
Sums of periodic functions are not always periodic
If the periods of two periodic functions do not have a common multiple, then their sum is not periodic. Perhaps the simplest example is , whose terms have least periods 2π and 2 respectively.
Polynomials are finite sums of periodic functions
Sums of periodic functions can be peculiar indeed. In fact, we can prove the following astonishing theorem: If is a polynomial function of a real variable, and the degree of is , then is the sum of periodic functions.
It is clear that a non-constant polynomial cannot be expressed as a finite sum of continuous periodic functions, since a continuous periodic function is bounded, and a finite sum of bounded functions is bounded. In fact, it can be shown that an unbounded continuous function cannot be expressed as a finite sum of Lebesgue measurable periodic functions. Consequently, we will need to use the Axiom of Choice.
R as a vector space over Q
The statement that every vector space has a basis is equivalent to the Axiom of Choice. Since is a vector space over , there is a subset of , called a Hamel basis, so that every real number can be written uniquely as a finite linear combination of elements of A with rational coefficients.
For each , we write where is rational and is finite for every .
Periodicity of (x,a)
It is readily seen that for all and all . Moreover for distinct . It follows that for all and distinct . In other words, the function is periodic with period for any .
The identity function is the sum of two periodic functions
Choose two distinct elements . Then .
Let and .
Then has period d, has period c, and is the identity function.
x^2 is the sum of three periodic functions
Note that . Choose three distinct elements . The term has period , unless or . Since no term involves all three of , it follows that each term has a period of either , , or .
Let be the sum of all terms which have period ; let be the sum of all terms which have period but not ; and let be the sum of all terms which do not have period or . Such terms must have period . More specifically,
Then is a representation of as the sum of three periodic functions.
A polynomial of degree n is the sum of n+1 periodic functions
Let P be a polynomial of degree n. Using the identity we can express P(x) as a linear combination of products with . Each term involves at most n distinct elements of A.
Let be distinct elements of A. No product in the expansion can involve ALL of . Therefore, we can group the terms into sums, , so that no term in involves .
Thus, we have , and each has period . QED.
A polynomial of degree n cannot be written as the sum of n periodic functions
Suppose that for some n, there is a polynomial P of degree n which is the sum of n periodic functions. Let p be one of the periods. Then is a polynomial of degree , and it is also the sum of periodic functions, since one of the terms cancels. By repeating this, we eventually obtain a polynomial of degree 1 that is the sum of 1 periodic function. But this is absurd.
e^x is not the sum of periodic functions
Suppose that is the sum of n periodic functions. Let p be one of the periods. Then is the sum of periodic functions, since the term with period p cancels out. But is a constant multiple of , so we conclude that is the sum of periodic functions. By repeating this, we find that is the sum of 1 periodic function. But this is absurd.
Stefano Mortola and Roberto Peirone, The Sum of Periodic Functions, Topology Atlas Document # vaaa-21
This problem was posted in an ice cream shop in Oxford, England. I found it surprisingly difficult.
Here is my solution. Suppose that and . After substituting,
which implies that . Therefore
But the left side is positive for , so there are no whole number solutions.
Image credit: Janet McKnight
Euclid’s proof of the infinitude of primes is justly famous. Here is one version of this proof:
Let P be a finite set of primes, and let N be the product of the numbers in P. Then N+1 is not divisible by any number in P, since it leaves a remainder of 1. But N+1 must be divisible by at least one prime, so P cannot contain all of the primes. Therefore the set of primes is infinite.
A variation of this argument shows that there are infinitely many primes of the form .
Let P be a finite set of primes of the form , and let N be the product of the primes in P. Consider the number . It is not divisible by 2 or 3, nor is it divisible by any number in P. But it is not possible that all prime factors of have the form , because the product would have the form as well.
Therefore, has at least one prime factor of the form that does not belong to P. Therefore, P cannot contain every prime of the form , so the set of primes of this form is infinite.
It takes a little bit more work to prove that there are infinitely many primes of the form . Here is a proof of that fact.
Let P be a finite set of primes of the form , and let N be a number that is divisible by every number in P. Assume that N is also divisible by 6. Let p be a prime divisor of .
Note that . so p divides , or in other words and so .
Recall that the order of N modulo p is the least positive k so that . The order must divide 6. so k = 1, 2, 3, or 6. But , so the order cannot be 1 or 3.
Can the order be 2? If and then . This would be bad, because then p would divide both and ; but , contradiction.
Thus N has order 6 mod p, and the group of units mod p has order , so 6 divides , which means that p has the form . Therefore, P does not contain all primes of the form , so the set of primes of this form is infinite.
In this note, I will state a proof of the following theorem: If are finite groups, and if is isomorphic to , then is isomorphic to .
Let be the number of homomorphisms from to , and let be the number of monomorphisms from to .
If is a finite group then
But since and are isomorphic. Therefore . Dividing both sides by yields .
I claim that for every finite group . The proof is by induction on the order of . If has order 1 then and , so the equality holds.
Suppose that for every group of order less than , and let be a group of order .
where ranges over all nontrivial normal subgroups of . But by the preceding argument, and by the induction hypothesis. Therefore .
Setting and in the above yields and . Thus there exist monomorphisms and . Since and are finite, this implies that and are isomorphic. QED.
I am very fond of this theorem because it was a key lemma in my doctoral dissertation. I learned of this argument from Fred Galvin, but I do not know if it was original to him.
The theorem would be false if the word ‘finite’ were omitted. For example, if A is a free abelian group of infinite rank, B is an infinite cyclic group, and C is the trivial group, then and are both isomorphic to A, but B and C are not isomorphic to each other.