Question

Suppose I randomly choose 4 distinct integers between 1 and 60. Is it true, or is it not true, that at least 2 of them must differ by no more than 19.

Answer 1

Answer:

It’s true

Step-by-step explanation:

Proof by induction

Let the four chosen numbers be x_1, … x_4 and, without loss of generality, let x_1 < x_2, … < x_4.

For x_1 = 1, the smallest possible choice, let x_2 = x_1 + 20 = 21 be the smallest possible choice that has a difference larger than 19. Likewise, x_3 = x_2 + 20 = x_1 + 40 = 41. Then x_4 has to be at least x_3 + 20 = x_1 + 60 = 61 which is out of range.

For the induction, suppose that x_4(n) = x_1(n) + 60 > 60 and therefore x_4(n) can’t be chosen for a given x_1(n). Then incrementing x_1(n+1) = x_1(n) + 1 would require x_4(n+1) to be at least x_1(n) + 1 + 60 = x_4(n) + 1 > 61, so this is out of range as well.

For another induction, suppose that x_4(n) = x_2(n) + 40 > 60 and therefore x_4(n) can’t be chosen for a given x_2(n). Then incrementing x_2(n+1) = x_2(n) + 1 would require x_4(n+1) to be at least x_2(n+1) + 40 = x_4(n) + 1 > 61, so this is out of range as well.

Likewise, for the induction, suppose that x_4(n) = x_3(n) + 20 > 60 and therefore x_4(n) can’t be chosen for a given x_3(n). Then incrementing x_3(n+1) = x_3(n) + 1 would require x_4(n+1) to be at least x_3(n+1) + 20 = x_4(n) + 1 > 61, so this is out of range as well.

Therefore all choices of x_1, x_2, x_3 with differences greater than 19 leaves no choice of x_4 within range with x_4 > x_3 + 19.