Mixing
Question based on pigeon hole reasoning
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
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.
combinatorics discrete-mathematics combinations
asked Sep 9 at 6:22
Miz
1,583522
add a comment |Â
up vote
5
down vote
favorite
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.
combinatorics discrete-mathematics combinations
asked Sep 9 at 6:22
Miz
1,583522
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13
add a comment |Â
up vote
5
down vote
favorite
up vote
5
down vote
favorite
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.
combinatorics discrete-mathematics combinations
asked Sep 9 at 6:22
Miz
1,583522
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.
combinatorics discrete-mathematics combinations
combinatorics discrete-mathematics combinations
asked Sep 9 at 6:22
Miz
1,583522
asked Sep 9 at 6:22
Miz
1,583522
asked Sep 9 at 6:22
Miz
1,583522
asked Sep 9 at 6:22
Miz
1,583522
asked Sep 9 at 6:22
Miz
1,583522
1,583522
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13
add a comment |Â
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
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.
answered Sep 9 at 6:32
Santana Afton
2,0681426
1
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
Sep 9 at 6:35
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
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.
answered Sep 9 at 6:32
Santana Afton
2,0681426
1
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
Sep 9 at 6:35
add a comment |Â
up vote
5
down vote
accepted
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.
answered Sep 9 at 6:32
Santana Afton
2,0681426
1
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
Sep 9 at 6:35
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
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.
answered Sep 9 at 6:32
Santana Afton
2,0681426
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.
answered Sep 9 at 6:32
Santana Afton
2,0681426
answered Sep 9 at 6:32
Santana Afton
2,0681426
answered Sep 9 at 6:32
Santana Afton
2,0681426
answered Sep 9 at 6:32
Santana Afton
2,0681426
2,0681426
1
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
Sep 9 at 6:35
add a comment |Â
1
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
Sep 9 at 6:35
1
1
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
Sep 9 at 6:35
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
Sep 9 at 6:35
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2910458%2fquestion-based-on-pigeon-hole-reasoning%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It is possible (e.g. give $k-1$ candies each to $k-1$ people and $k+1$ to one person) but not necessary (e.g. give $k$ candies each to $k-1$ people and $2$ to one person)
– Henry
Sep 9 at 11:07
Maybe it was meant to be $k-1$?
– MalayTheDynamo
Sep 9 at 16:13