Prove that among any 54 integers 1 =< x1 < x2 < x3 < < x54 =< 100, there is a pair with difference 12.

Use the pigeonhole principle.

Consider choosing



This selection guarantees that no two elements have a difference of 12. For example, in the first subset with , the largest difference is 12 - 1 = 11. Then in the next subset with , the smallest difference between the least element of this subset with the previous subset is 25 - 12 = 13.

The last subset is problematic, however, because the last two elements of that subset are 48 + 53 = 101 and 48 + 54 = 102. We require that all the integers are no greater than 100, and that they are distinct, which means there must be two numbers that belong to the set , and this will force at least one integer that makes up a pair with difference 12.