Let $S$ be a subset of $\{1,2,3,4,5,6,7,8,9,10\}$. If $S$ has the property that the sums of three elements of $S$ are all different, find the maximum number of elements of $S$.
Problem
Source: 2012 Indonesia Round 2 TST 4 Problem 3
Tags: combinatorics proposed, combinatorics
18.03.2012 22:17
I'm getting 5, which can be done with $\{1,6,8,9,10\}$ among others. Not entirely convinced this messy proof that 6 fails is correct... Suppose we have six numbers $a_1 < a_2 < a_3 < a_4 < a_5 < a_6$. Call a bad quad a set of four pairwise distinct indices $i,j,k,\ell$ with $a_j - a_i = a_\ell - a_k$. We can't have any bad quads because then $a_i + a_\ell + x = a_j + a_k + x$, where $x$ is an arbitrary fifth element. If we define $d_i = a_{i+1} - a_i$ the only way two terms of $d_1, d_2, d_3, d_4, d_5$ can be equal is if they are consecutive. Using the fact that $d_1, d_3, d_5$ are pairwise distinct and $\sum_{i=1}^5 d_i = a_6 - a_1 \leq 9$, we can show that $d_1, d_2, d_3, d_4, d_5$ is $1,1,2,2,3$ in some order, with the pair of 1s and pair of 2s consecutive. If $d_j = d_{j+1} = 1$ and $d_k = d_{k+1} = 2$, then $a_{j+2} - a_j = 2$, $a_k - a_{k-1} = 2$, and $a_{k+1} - a_k = 2$. Either $j, j+2, k-1, k$ or $j, j+2, k, k+1$ are a bad quad, so six elements is impossible.
19.03.2012 02:06
I divided cases, like that there are 20 sums if there are 6 elements and decide which sum is possible or impossible. Ultimately I reached to a contradiction by disallowing 3 sums, while there are only 22 possible sums (6-27).