A Number Theory Problem About Natural Numbers

一道自然数的数学题 苏剑林 · 2009-07-26 · Mathematics natural number pigeonhole principle

This feels a bit like the pigeonhole principle, but seems slightly more complex:

There are 12 pairwise distinct natural numbers, all less than 37. Prove that among the pairwise differences of these natural numbers, at least 3 must be equal.

My solution:

Suppose, for contradiction, that no difference occurs more than twice. Arrange the numbers in increasing order, and consider the smallest possible case:
Their differences would be 1, 2, 3, 4, 5, 6 respectively; among these, 6 appears once and the others appear twice (this is the minimal case).
Then the difference between the first and the last number is 36 ($(1+2+3+4+5)\cdot 2+6$), so it follows that the first natural number can only be 0, and there is only this one possibility for the differences.
Then, among 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, if we pick any n of these numbers and sum them, then subtract n−1 of those n numbers, the result will always land among these 11 numbers, which contradicts our original assumption.
Let's give an example:
The first number is 0
The second number is 5
The third number is 5+6
The fourth number is 5+6+4
Then, (5+6+4)−(5+6)=4 — doesn't that give us a third occurrence of the difference 4?
This shows that, in any case, it is impossible for every difference to occur only twice.

By the way, let's figure out how to find someone who shares your exact birthday (same year, month, and day):

Look at how many people are in your grade at school. If there are more than 500, and you're not some especially unusual case, then there is bound to be someone who was born on exactly the same year, month, and day as you!

Do you know why this is? It's not some mystical "fated encounter" — there's actually solid mathematics behind it! Why not try to work out the reasoning yourself?

If you don't believe it, go ask around class by class (^_^)? You're bound to find something interesting.