2
$\begingroup$

I always have trouble trying to exactly identifying the exact pigeon and the pigeonholes for questions with slightly more integers. For example, questions like this.

Eleven integer are chosen from 1 to 20 inclusive. Use pigeonhole principle to prove the selection include integer a and b such that b = a + 1

To me, it's a little confusing because of the number of integers and the integer a and b.

Is it safe for me to assume the pigeon = 2 because of the integer a and b while the pigeonhole = 11 because of the chosen eleven integer?

The above seems to be less confusing compared to another question that uses generalized pigeonhole

A fruit basket that contains 10 apples, 8 oranges and 9 banana. If someone pick some fruits without looking, use the generalized pigeonhole principle to determine how many must you pick to be sure of getting at least 5 fruits of the same type

With so many potential values lingering in the question, is there any way to simply and identify the pigeon and pigeonhole to use the generalized pigeonhole to prove it?

$\endgroup$
1
$\begingroup$

For the first problem you want to divide the integers from $1$ through $20$ into $10$ pairs of consecutive integers: $\{1,2\}$, $\{3,4\}$, and so on up through $\{19,20\}$. These $10$ pairs are your pigeonholes, and the $11$ numbers that you choose are your pigeons. Since you have $11$ pigeons and only $10$ pigeonholes, some pigeonhole must contain two pigeons. In other words, two of your $11$ numbers belong to the same odd-even pair of consecutive integers.

The second problem is actually easier, because less ingenuity is needed in order to decide what the pigeons and pigeonholes are. In fact, I prefer not to think about pigeons and pigeonholes at all when dealing with this kind of problem. Ask yourself: what’s the most fruit I could take and not get at least $5$ of one type? Clearly I could take $4$ apples, $4$ oranges, and $4$ bananas, a total of $12$ pieces of fruit. The moment I take $13$ pieces, however, I must have more than $4$ of at least one of the types.

I’m afraid that there is no simple general way to identify pigeons and pigeonholes; sometimes it takes a great deal of ingenuity to come up with something that works. In the first problem here, though, it’s a good guess that the $11$ chosen numbers will be the pigeons, and that you have to show that $11$ is enough to ensure that two are consecutive. (It is at least true that if having more of something in the problem makes the desired outcome more likely, that something is fairly likely to be your pigeons.) That means that you should have at most $10$ pigeonholes, and they should be chosen so that if you have two pigeons in the same pigeonhole — i.e., two of the chosen numbers in the same set — then those numbers are consecutive. That suggests dividing $\{1,2,\ldots,20\}$ into $10$ pairs of consecutive numbers, those pairs being the pigeonholes, and in this case it works.

$\endgroup$
  • $\begingroup$ Thank you so much for being so clear and precise. You made it seems so simple. I guess i really need to find out more questions on such pigeonhole principle and practice more. Thanks to the community and people like you, my motivation to get better in maths and programming is so strong so one day i hope i can help others too. Thanks again. :) $\endgroup$ – Teo Chuen Wei Bryan Aug 26 '16 at 19:32
  • 1
    $\begingroup$ @TeoChuenWeiBryan: You’re very welcome. And yes, experience makes a great deal of difference: the more such problems you see, the likelier you are to come up with an idea that works. $\endgroup$ – Brian M. Scott Aug 26 '16 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.