Quick questions on The pigeonhole principle: guaranteed coincidences in counting problems

3short Q&A pairs drawn directly from our worked dot-point answer. For full context and worked exam questions, read the parent dot-point page.

What is watch objects fill the boxes, stage by stage?

Show answer

The principle is easiest to believe when you try (and fail) to keep every box to one object. Take

4

boxes and place objects one at a time. The first four can spread out, but the fifth has nowhere new to go.

What is off-by-one in the bound?

Show answer

n + 1

or more" pigeons forces a box with

\ge 2

; exactly

n

pigeons does not. State the strict inequality.

What is generalised-form miscount?

Show answer

kn + 1

pigeons force

\ge k + 1

in some box;

kn

pigeons do not. Use the ceiling

\lceil m/n \rceil

to be safe, and double-check whether

m = kn

exactly (in which case the guarantee is only

k

Have a question we have not covered?

This dot-point answer is short enough that we have not extracted many short questions yet. Read the full dot-point answer or ask Mo, our study assistant, in the chat for follow ups.