Question based on pigeon hole reasoning
Clash Royale CLAN TAG#URR8PPP
Question based on pigeon hole reasoning
Suppose $k^2-k+2$ candies are distributed among a group of $k$ people ($k geq 3$), such that every person gets at least one candy. Is it true that one person in the group got at least $k+1$ candies?
So this was a question on the combinatorics test in an earlier exam. My belief is that if you take the average then $frack^2-k+2k=k-1+frac2k$.
So by a basic pigeon hole argument you can conclude that one of the persons got at least k candies. But is it true that someone got $k+1$?
I asked a few seniors and they claim it is possible. I can't figure out how.
1 Answer
1
Unless I misunderstand, this is not possible.
Consider the easiest possible case: $k=3$.
I have three people, and eight total candies. Is it true that regardless of how I distribute them, someone must have four candies so long as everyone gets at least one?
Surely not. Give the first person three, the second person three, and the third person two.
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
For any $kge3$, this approach is generalized by first giving each person $k-1$ candies. This leaves $(k^2-k+2)-(k^2-k) = 2$ candies left to give. Give two distinct people one additional candy. Thus two people have $k$ candies and the rest have $k-1$.
– Santana Afton
1 hour ago