The Vault: My favourite puzzle

Having spent nine days in Hamburg at a maths conference, I return to present what is to date my favourite ever maths problem. From the Tournament of the Towns:

Let n be a positive integer. Consider the largest odd factor of each of the numbers n+1, n+2, …, 2n. Prove that their sum is n2.

When I first saw this problem, I looked at it in disbelief. On the face of it, the result linking odd factors and square numbers is completely outrageous. I knew I had to try it immediately…

So we have n odd factors. After playing around with small cases, we get a sense of what’s really going on.

n = 2 :

3 is the largest odd factor of 3

1 is the largest odd factor of 4

3 + 1 = 4, which is 22.

n = 5:

3 is the largest odd factor of 6

7 is the largest odd factor of 7

1 is the largest odd factor of 8

9 is the largest odd factor of 9

5 is the largest odd factor of 10

3 + 7 + 1 + 9 + 5 = 25, which is 52.

We notice that for some reason, all the odd factors in our sum are different – there is never a repeat. Further, in fact it looks like the odd factors in our sum are just the first n odd numbers. How can we prove this claim?

Well, what can we say about two different numbers with the same largest odd factor? By looking at their prime factors, we realise that the only difference in their prime decompositions will be the power of 2 that appears; all the odd primes must be identical in both numbers. For example, 3 is the largest odd factor of 6, 12 and 48.

6 = 2 x 3

12 = 2 x 2 x 3

48 = 2 x 2 x 2 x 2 x 3.

So if two numbers have the same largest odd factor, then one is at least double the other. But in the list n+1, n+2, …, 2n, the largest number (2n) is less than double the smallest (n+1). So it is impossible for two numbers in the list to have the same largest odd factor. Hence every odd factor in our final sum is different.

Exactly which odd factors appear then? The largest that appears is always 2n-1. But the list of the first n odd numbers is precisely

1, 3, 5, …, 2n-1.

Our final sum contains n different odd factors, the largest of which is 2n-1. But this means that our sum must just contain every odd number in the list above precisely once.

It remains to calculate 1 + 3 + 5 + … + (2n-1). But this is an arithmetic series, an is easily calculated:

1 + 3 + 5 + … + (2n-1) = n2

and this astonishing result is proven.

What is remarkable about this problem is the number of  “good” characteristics it displays:

  • It is simple to understand
  • It has a fairly simple proof, but it difficult to find
  • The result is (very) surprising
  • It is aesthetically pleasing
  • It seems to strike at the heart of how mathematics works.

Even now, months after coming across it, the problem still holds the magic it did the first time I saw it. It is a work of art, beautifully constructed, and I am sincerely grateful to the author for sharing it with the world. If I ever find another like it, I will count myself very lucky indeed.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s