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.

Solution

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.

• 17 rooks on a Chessboard
• Chinese Remainder Theorem
• Pigeonhole in a Chessboard
• Pigeonhole in Concurrent Cuts
• Monochromatic Rectangle in a 2-coloring of the Plane
• Polynomial and Integer Division
• Power of three that ends with 001
• Pigeonhole Principle (subsets)
• Four Numbers, Six Differences, GCD of the Products