Edit: Comments showed me the answer is 7. How can I prove that using pigeonhole?
I know this is a pigeonhole principle question and that $6$ integers is enough to guarantee the condition, but I'm having trouble figuring out the appropriate pigeons/pigeonholes. Here are a few thoughts, though I don't know how useful they are:
- There are $8$ possible triplets from $\{1,2,…,9\}$ that sum to $15$: $\{1,5,9\},
\{1,6,8\}, \{2,4,9\}, \{2,5,8\}, \{2,6,7\}, \{3,4,8\}, \{3,5,7\}, \{4,5,6\}$. - From $6$ integers there are $20$ possible triplets, and from
$S$ the minimum triplet sum is $1+2+3=6$, and the maximum is
$7+8+9=24$, giving us a range of $19$ possible sums. - In order for a triplet to sum to $15$, the sum of its smallest integers
must be at least $6$, and the sum of its largest integers must be at
most $14$.
I think I'm missing some crucial observation.
Best Answer
The answer is $7$.
You need at least $7$ because no three of the $6$ numbers $1,2,3,7,8,9$ add up to $15$.
Looking at your $8$ possible triplets that sum to $15$, no number belongs to more than $4$ triplets, and only the number $5$ belongs to $4$ triplets, no other number belongs to more than $3$ triplets. Therefore if you choose any $7$ numbers from $S$, the two missing numbers are in at most $4+3=7$ triplets between them, so there is at least one triplet you haven't avoided.