← All Learn lessons · Start adaptive practice · Practise on paper

You will learn: Choose useful boxes and prove that some group must contain enough objects.

Before you start: Counting objects and understanding a guarantee versus a possibility.

More objects than boxes

Place five counters into four boxes. At least one box must contain two or more counters. If every box held at most one, there would be room for at most four counters, contradicting the five you placed. This is the pigeonhole principle.

The crowded box may change, but five counters cannot all be alone in four boxes.

More generally, if n boxes each hold at most k objects, there are at most nk objects. So nk + 1 objects force some box to contain at least k + 1. To solve a problem, identify the objects, define the boxes, and check that every object belongs to exactly one box.

Worked example 1: a repeated birthday month

Among 13 people, at least two were born in the same month. The people are the objects and the 12 calendar months are the boxes. If no month held two birthdays, there could be at most 12 people. This guarantees a shared month, not a shared date or a particular month.

Worked example 2: create the right pairs

Choose six distinct integers from 1 through 10. Show that two chosen integers sum to 11. Make five boxes: {1,10}, {2,9}, {3,8}, {4,7}, {5,6}. Every allowed integer lies in exactly one box. Six choices among five boxes force a box with two chosen integers. Those two are the pair whose sum is 11.

There is no guarantee with only five choices: choosing 1, 2, 3, 4, 5 gives no pair summing to 11. This construction shows why the threshold six matters.

Remainders can be boxes

When integers are divided by 4, only four remainders are possible: 0, 1, 2, 3. Among any five integers, two have the same remainder. Their difference is then divisible by 4. Notice that it is the difference, not necessarily either original integer, that is a multiple of 4.

Possible is weaker than guaranteed

Two people may share a birthday month, but with only two people this is not forced. A guarantee must survive every possible arrangement. To show that a claimed smaller threshold fails, give one arrangement avoiding the desired event. To show the correct threshold works, use a counting argument covering all arrangements.

Practise at your next step

A six-question session chooses from nine questions. Two correct answers in a row without hints move you up a level; an incorrect answer brings a simpler next question where one is available. Hints keep you at the same level. This is a practice suggestion, not an exam score or proof of mastery.

Interactive practice loads here. You can also use the complete question set below.

Write a proof of your own

Prove that among any seven integers, two have a difference divisible by 6.

Write your reasoning on paper before comparing. The practice checker does not grade a written proof.

Compare your proof with a full solution

Divide each integer by 6 and put it in the box labelled by its remainder, one of 0, 1, 2, 3, 4, 5. Seven integers in six boxes force two in the same box. Write them as 6a + r and 6b + r. Their difference is 6(a − b), which is divisible by 6. This also covers negative integers and repeated values.

Check: did you state the assumptions, explain the key step, and reach the requested conclusion?

All nine practice questions, hints and solutions

This complete set works without the interactive practice. Hide each solution until you have made an attempt.

1. Five counters are placed in four boxes. What is guaranteed?

Foundation

  1. Every box is nonempty
  2. One box has at least two counters
  3. One box has exactly three counters
  4. The first box has two counters
Hint

What would be the largest total if every box held at most one?

Answer and explanation

One box has at least two counters. At most one counter in each of four boxes would give at most four counters. With five, some box must hold at least two. The argument does not identify which box.

2. How many people guarantee that two share a birthday month?

Foundation

  1. 2
  2. 7
  3. 12
  4. 13
Hint

There are 12 possible months.

Answer and explanation

13. With 13 people and 12 months, some month contains at least two birthdays. Twelve people need not share a month, since one could be born in each month.

3. In a birthday-month argument, what are the boxes?

Foundation

  1. The people
  2. The 12 months
  3. The 365 dates
  4. The ages
Hint

Group people by the property that should match.

Answer and explanation

The 12 months. The goal is a repeated month, so the boxes are the 12 months. Each person belongs to the month in which their birthday falls.

4. Ten counters are placed in three boxes. What is guaranteed?

Core

  1. Some box has at least 4
  2. Every box has at least 3
  3. Some box has at least 5
  4. All boxes are nonempty
Hint

If every box held at most 3, how many counters could there be?

Answer and explanation

Some box has at least 4. Three boxes with at most 3 counters each hold at most 9 counters. Ten counters therefore force at least 4 in some box. Four is sharp: the distribution 4, 3, 3 avoids five.

5. How many distinct integers chosen from 1 through 10 guarantee that two sum to 11?

Core

  1. 4
  2. 5
  3. 6
  4. 10 only
Hint

Group the integers into the five pairs that sum to 11.

Answer and explanation

6. Use {1,10}, {2,9}, {3,8}, {4,7}, {5,6}. Six choices force a complete pair. Five choices such as 1,2,3,4,5 need not contain such a pair, so the minimum guarantee is 6.

6. Among any five integers, which statement is guaranteed?

Core

  1. Two are equal
  2. One is divisible by 4
  3. Two have a difference divisible by 4
  4. Their sum is divisible by 4
Hint

Use the four possible remainders modulo 4 as boxes.

Answer and explanation

Two have a difference divisible by 4. Five integers occupy only four remainder classes, so two have the same remainder. Writing them as 4a + r and 4b + r, their difference is 4(a − b), a multiple of 4.

7. What is the minimum number of counters that guarantees at least 5 in some box when there are 4 boxes?

Stretch

  1. 16
  2. 17
  3. 20
  4. 21
Hint

First fill each box with as many as possible without reaching 5.

Answer and explanation

17. Four boxes can each hold 4 counters, giving 16 without any box reaching 5. One more counter makes this impossible. Thus 17 is necessary and sufficient for the guarantee.

8. A drawer contains only red, blue and green socks, with plenty of each. Without looking, how many socks guarantee at least 3 of one colour?

Stretch

  1. 3
  2. 6
  3. 7
  4. 9
Hint

How many could you take while having at most 2 of each colour?

Answer and explanation

7. At most 2 of each of 3 colours gives 6 socks without a triple. The seventh forces at least 3 of one colour. Six do not guarantee it, as 2 red, 2 blue and 2 green show.

9. Choose six distinct integers from 1 through 10. Which grouping proves that two are consecutive?

Stretch

  1. {1,10}, {2,9}, {3,8}, {4,7}, {5,6}
  2. {1,2}, {3,4}, {5,6}, {7,8}, {9,10}
  3. One box containing all ten integers
  4. Ten one-number boxes
Hint

Every two-number box should itself guarantee the desired difference.

Answer and explanation

{1,2}, {3,4}, {5,6}, {7,8}, {9,10}. The five boxes {1,2}, {3,4}, {5,6}, {7,8}, {9,10} each contain consecutive integers. Six distinct choices force both members of some box to be chosen. They differ by 1, as required.

Where to go next

Move on to the mixed proof-practice plan · Explore the wider Olympiad topic map

Teaching examples prepared for this guide, not attributed to a contest paper. Familiar elementary problems may appear in other learning materials. Report an unclear step or an error.