Integers and proof
Fifty five numbers are selected from the the 1st 100 positive integers.
(a) Show there must be two which differ by 9, two which differ by 10, and two which differ by 13.
(b) Show there doesn’t have to be two which differ by 11.
(c) Show there must be two which differ by 12.
This is a good problem.
Originally Posted by smithhall
What have you done to start a solution?
And where are you having trouble?
The easiest way to solve this is by doing the following:
Try and construct a solution by starting from 1, going to 100, and adding a number to the 'solution' if it doesn't interfere with the difference condition. for example on the 9:
1 2 3 4 5 6 7 8 9 19 20 21 22 23 24 25 26 27 etc.
This gives you a 100/18 of these sequences of 9 numbers and 9 gaps, which is 5 rest 10. Fill up the rest 10 with 9, so you have 6*9 = 54 numbers in the solution, which is optimal (you can do that proof for yourself) which is less than 55.