Pure self-indulgence

Well, almost pure.

I was leafing through Aigner and Ziegler’s Proofs from THE BOOK, which is a compendium of the most beautiful results in mathematics, and I came across a very simple puzzle which Paul Erdös used to use when he wanted to see if someone was really a mathematician. Here it is, without the algebra:

Think of the numbers from 1 to 100. Prove that if you make a collection of any 51 numbers between 1 and 100, at least one number in your collection will be divisible by some other number in your collection.

I am not a real mathematician. I am not patient enough. Knowing I’d regret it for the rest of my life, I read the solution. It is indeed very beautiful. To atone for my crime and assuage my anguish, here is the proof in a form that I think everyone will be able to follow. Try it. It’s fun.

Take 1, and double it, and double it, and double it, and so on. This gives you 1, 2, 4, 8,… Let’s call this the ‘family’ of 1.

Take 3, and double it, and… you get the idea. Then 3, 6, 12, 24,… is the ‘family’ of 3.

And so on.

Here are three obvious facts about families.

  1. Every odd number has a family of its own.
  2. Every even number is a member of an odd number’s family. (Just keep on dividing it by 2 until you can’t divide it by 2 any more).
  3. If two numbers are in the same family, one is divisible by the other. (Because you can get from the smaller one to the bigger one by doubling it repeatedly).

So then, those numbers between 1 and 100. How many families do they belong to? 50, because there are 50 odd numbers between 1 and 100 and each of them has a family of its own.

So then, those 51 numbers in your collection. How many of them are there? 51.

51 numbers in 50 families means that [at least] two of them must be members of the same family.

So one of those numbers must be divisible by the other.