Pigeonhole question involving choosing $6$ distinct integers

127 Views Asked by At

Prove that if $6$ distinct integers from one to ten are chosen, then there will be at least two of them which sum to eleven.

I have identified the five only possible pirs: $(10,1),(9,2),...,(6,5)$ but I am having trouble expressing how this is guaranteed if six digits are chosen. I'm not sure if this helps, but I know for the first digit chosen, there is only one way to get the desired outcome (sum to eleven). Since there are 6 digits chosen, $\lceil 6/5 \rceil=2$? So At least two will produce a sum of eleven? Sounds very flawed to me.

1

There are 1 best solutions below

1
On BEST ANSWER

The thing that sounds very flaw to you is, in fact, correct.

Put the number $1$ to $10$ in five boxes, as you have done: $(10, 1), (9, 2), \dots, (6, 5)$.

Now you want to choose $6$ numbers from the five boxes. By pigeonhole principle, there must be two numbers that are chosen from the same box.

These two numbers will sum up to $11$.