4
$\begingroup$

So we have the below pigeonhole problem from an example quiz and I understand how to solve the problem, but I can't really model how it is working in my head. Can anyone explain it?

There are 50 baskets of apples. Each basket contains at least one, but no more than 24 apples. Show that there are at least 3 baskets containing the same number of apples.

Solution: The baskets are the pigeons, and we place each of them in one of 24 pigeonholes according to how many apples are in it. Thus the ratio n/k of pigeons to pigeonholes is 50/24 = 2 and 1/12

By Generalized PHP there are at least this many baskets with the same number of apples, so there must be at least 3

$\endgroup$
2
  • 1
    $\begingroup$ Can't a basket contain zero apples...? Then there would be $25$ holes, not $24$. $\endgroup$
    – CiaPan
    May 23, 2016 at 13:07
  • $\begingroup$ @CiaPan: I agree. I fixed it for the OP. $\endgroup$
    – TonyK
    May 23, 2016 at 13:29

1 Answer 1

Reset to default
3
$\begingroup$

You have $50$ baskets, and each basket contains between $1$ and $24$ apples. I assume no basket contains $0$ apples since you said "$50$ baskets containing apples". Then you can take out 48 baskets and place $1$ apple in two of them, $2$ apples in two of them etc. until you have 48 baskets and for every number between $1$ and $24$ there are exactly two baskets containing that many apples. Now you have $2$ empty baskets left. Regardless of how many apples you place in them, there are two baskets already containing equally many apples. So you will at least $3$ baskets containing equally many apples.

Edit: I hope this helps you in thinking about the PHP in a more intuitive way, rather than simply looking at formulas. When considering these "basic" PHP problems I like to carry out the argument as I did above, at least in my mind before I write down my answer using the PHP results, because it's a very logical and simple reasoning, so less room for mistakes.

2nd Edit: Maybe you can try to reason why there are at most two cases of "$3$ baskets containing equally many apples". That is, if there are $3$ baskets containing $a_1$ apples, and there are $3$ other baskets containing $a_2$ apples, then you cannot have a third set of $3$ baskets containing equally many apples. Begin with the two remaining baskets in my explanation above, and see what happens when you fill the last two.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer! I am still having trouble getting it but I think it is simply because I need to reflect on it a bit and re-read your answer a few times. It is not the most intuitive thinking for me right now but hopefully it will clear itself upon further reflection with your strategy. $\endgroup$
    – timbram
    May 23, 2016 at 17:26
  • $\begingroup$ Ah, I get it now. It turns out I wasn't understanding the question properly and getting hung up on the fact that the baskets seemed to be the containers, when in actuality the fact that no basket can have more than 24 apples is what is the "container". $\endgroup$
    – timbram
    May 23, 2016 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .