|
Let a and b be positive integers, with a < b < 2a. Then, given more than half of the integers in the set {1, 2, ..., a + b}, some two of the given integers differ by a or by b.
|
The proof is by William A McWorter Jr..
Form the array below.
| 1 | 2 | 3 | ... | b | b+1 | b+2 | b+3 | ... | a+b |
| a+1 | a+2 | a+3 | ... | a+b | 1 | 2 | 3 | ... | a |
There are a + b columns and each integer appears exactly twice in the array. Now, given more than half the integers in {1, 2, ..., a + b}, the given integers appear in the above array, counting multiplicity, more than a + b times. Hence there must be two occurrences of the given integers in the same column. Thus those occurrences differ by a or b.
The reason for the condition b < 2a is that you need only a little over a third of the integers if b = 2a. And the original proof
still works if b > 2a.
Copyright © 1996-2009 Alexander Bogomolny
|
