5

20 pairwise distinct integers each less than 70 are taken and their pairwise differences are taken(magnitude of the difference). Show that there always exists 4 equal numbers.

I somehow found the range of the differences and tried to show that we get a minimum four equal numbers but it was not that easy. Another tough question in my school exam which I couldn't solve.

VividD
  • 15,966
Caratheodory_Enthusiast
  • 801

1 Answers1

3

Let us mark these numbers as $n_{1}, n_{2}, ... n_{19}, n_{20}$, but so that $n_{1} \lt n_{2} \lt ... \lt n_{19} \lt n_{20}$. This is then valid:

$$(n_{20} - n_{19}) + (n_{19} - n_{18}) + ... + (n_{3} - n_{2}) + (n_{2} - n_{1}) = (n_{20} - n_{1}) \lt69$$

Let's say there are no 4 same differences among $(n_{i+1} - n_{i})$. Then minimal value for their sum would be $3 \times 1 + 3 \times 2 + 3 \times 3 + 3 \times 4 + 3 \times 5 + 3 \times 6 + 7 = 70$, and this would mean $70 \lt 69$.

This means at least four of $(n_{i+1} - n_{i})$ must be the same.

VividD
  • 15,966
  • This is taken straight from PSS and in my opinion lacks some justification – Confuse Jan 21 '18 at 01:40
  • Justification of what?? @Confuse – VividD Jan 21 '18 at 01:45
  • I was having a bit of a tough time figuring out why the minimal would be $31+32+...+3*6+7$ but I do understand after a bit of a thought. This is probably the cleanest way to solve and this problem is way popular beyond PSS so I take my comment back :). – Confuse Jan 21 '18 at 01:48