The set S consists of 20 distinct positive integers, each below 70.
Create a set S' of 190 pairwise absolute values of differences between two distinct members of S.
Prove that in S' there must exist at least one value that appears more than 3 times.
Well, unless I am missing something, this is a simple example of the pigeonhole principal. The absolute differences must be between 1 and 69. With only 69 different values, we can only look at 138 couples without having a value appear three times. With 139, there must be at least one value that appears three times.
Further, a given value can appear at most 19 times because of the way that the set is constructed. That means that after 138 + 19 = 157 couples, there must be at least two values that appear at least three times. After 157 + 19 = 176 couples, there must be at least three values that appear three times.
So, without much thought, there must be at least 3 values that appear three times.
But it may be that with more careful analysis we can prove that there must be more such values. If one value (n) appears 19 times, then all 20 integers are in a linear progression, so 2n appears 18 times and 3n appears 17 times and 4n appears 16 times etc. So if we are trying to minimize the number of triples, then we cannot have one appearing 19 times.
Similarly, if one number n appears 18 times, then there are two separate linear progressions with a constant difference and a total length of 20. Then 2n appears at least 16 times and 3n appears at least 14 times and 4n appears at least 12 times, etc. So if we are trying to minimize the number of triples, then we cannot = have one appearing 18 times. That means that a 4th triple must occur after 138 + 17 + 17 + 17 = 189 couples. Since we have 190 couples, there must be at least 4 numbers that appear at least three 3 times.
If I pursued this sort of analysis, I might be able to prove that 5 or even 6 numbers must appear at least 3 times. But I have run out of time. I may or may not pursue this in a later post.
/*************************************************/
CORRECTION: I have shown that there must be at least 4 numbers that appear at least 3 times. But the problem requests a proof that a number appears MORE THAN 3 times. See my next post for the requested proof.
Edited on May 6, 2018, 6:07 pm
There must be at least 4 such numbers (spoiler)
