It looks to me that this is Pigeonhole related question but can't come up with the proof. I tried this: Group numbers in pairs such that sum of pairs equals to 2n - 1. If 2n - 1 is selected then by Pigeonhole principle there will be a pair that is selected too. But what if 2n -1 is not selected?
Asked
Active
Viewed 216 times
0
-
... then how many numbers do you have in your set from $2$ to $2n-3$? – Mark Bennet Mar 28 '21 at 20:54
-
Always at least $\lceil \frac{n+1}{2}\rceil$ of at least one parity. – Roddy MacPhee Jun 10 '21 at 23:16
1 Answers
0
I think that you can extend the argument you made a little bit. You showed that the condition is satisfied if $2n - 1$ is selected. What if the biggest number selected is $2n - 2$? Now we have can divide the rest of the numbers into pairs that add $2n - 2$ (note that $n - 1$ is alone, but there are still $n - 2$ groups and we have to select more than one number from some group). This argument can continue if $2n - 3$ is the greatest, $2n - 4$ is the greatest, and so on. Hope this helps!
dannnny
- 124
-
There are $n$ odd numbers, selecting them all will force you to select an even number that is their difference. Selecting all even numbers forces it ( only $n-1$ of those) . And a few more cases ... – Roddy MacPhee Jun 10 '21 at 23:13