2
$\begingroup$

$10$ numbers are chosen from $\{1,2, \ldots, 37 \}$. Show that we can choose $4$ of them such that the sum of two of these four is equal to the sum of the other two.

My attempt : Almost nothing I think. Firstly, it suffices to find $4$ numbers such that the difference two of them is equal to the difference of the other two so one can compare differences assuming no two are equal resulting to some bounds e.g. the least of the ten numbers is less than $12$ and the bigger of these is $\geq 26$. Any help?

$\endgroup$
  • 2
    $\begingroup$ Here's a naive first application of the pigeon hole principle: There are $\binom{10}{2}=45$ pairs of numbers but only $36$ possible differences of numbers, so there have to be two pairs that yield the same difference. However, the two pairs might not be disjoint. $\endgroup$ – Christoph Jun 16 at 18:33
3
$\begingroup$

Edit: The original answer contains an unacceptable mistake, so I post a new answer.

Continue the method mentioned in Christoph's comment. If we get two disjoint pair we have done. Otherwise, the only case is $(x_1-d_1,x_1)$ and $(x_1,x_1+d_1)$, then do the following loop(start from $i=2$):

Loop $i$: Exclude the pairs we got, so there are $45-2(i-1)$ pair of numbers, and $36-(i-1)$ possible differences. Again, by pigeon hole principle(if $i<10$), if we get two disjoint pairs we have done. Otherwise, the only case is $(x_i-d_i,x_i)$ and $(x_i,x_i+d_i)$. If $x_i=x_j$ for some $i\neq j $ , then the pairs $(x_i-d_i,x_j-d_j)$ and $(x_i+d_i,x_j+d_j)$ are what we need, done. Otherwise continue the loop.

Now I show that we will be done on or before $i=9$. Suppose $i$ attend $9$ and cannot get two disjoint pairs by pigeon hole principle, then by definition of $x_i$'s, all of them are different. So the set {$\min(x_i-d_i|i\leq8),x_1,x_2,...,x_8,\max(x_i-d_i|i\leq8)$}=original set. So $x_9$ must equal to one of $x_1,x_2,...,x_8$, otherwise the set {$\min(x_i-d_i|i\leq9),x_1,x_2,...,x_8,x_9,\max(x_i-d_i|i\leq9)$} is subset of original set but number of elements is larger than the original set, contradiction arises.

$\endgroup$
1
$\begingroup$

Let $A = \{ a_1, \ldots, a_{10} \}$ be a subset with ten elements, where $i < j \rightarrow a_i < a_j$, of $B = \{1, \ldots, 37\}$.

Obviously $a_{10} - a_1 \leq 36$. Define $d_i := a_{i + 1} - a_{i}$. We have $1 \leq d_i \leq 27$, and $\sum_{i = 1}^9 d_i = a_{10} - a_{1} \leq 36$. If $d_i = d_j$, then $a_i + a_{j + 1} = a_j + a_{i + 1}$. So in order for a four-subset satisfying the desired property not to exist, all $d_i$ must take different values. There is no set of nine distinct positive integers whose sum is smaller than 36.

As far as I can tell, the property would still hold for numbers much larger than 37, too - this proof doesn't consider differences between numbers which aren't adjacent.

$\endgroup$
  • 2
    $\begingroup$ +1: Very nice! One way to make it a bit smoother might be as follows: Supposing that the $d_i$ are pairwise distinct, then $$\{d_i:1\le i\le 9\}=\{c_i:1\le i\le 9\}$$ where $i<j$ implies that $c_i<c_j.$ Then $i\le c_i$ for each $i,$ so $$45=\sum_{i=1}^9i\le\sum_{i=1}^9c_i=\sum_{i=1}^9d_i<36$$ yields a contradiction. $\endgroup$ – Cameron Buie Jun 16 at 18:40
  • 1
    $\begingroup$ As OP mentioned in his comment, you have to watch that $i+1\neq j$. So consecutive $d_i$ may be equal. $\endgroup$ – Empy2 Jun 16 at 19:09
  • $\begingroup$ Consider 1 2 3 5 7 11 14 17 30 37 $\endgroup$ – DragunityMAX Jun 16 at 19:11
  • $\begingroup$ Watch out, it's possible that $j=i+1$ ... so wrong $\endgroup$ – math_here Jun 16 at 19:35
  • $\begingroup$ Ah, completely correct. It could still be fixed, but I see a correct answer is already published. $\endgroup$ – Alexander Geldhof Jun 16 at 21:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.