2020 HSC Mathematics Extension 1
Question 12(c):
Pigeonhole principle
To complete a course, a student must choose and pass exactly three topics. There are eight topics from which to choose.
Last year students completed the course.
Explain, using the pigeonhole principle, why at least eight students passed exactly the same three topics.
How to recognise this question
Question type: pigeonhole principle
- The command and notation point to pigeonhole principle.
- The requested response is a explanation.
How to handle it: identify the objects and boxes, then show why avoiding a repeated box is impossible.
Watch out: Do not select a formula until its domain, interval, sign and units match the question.
Step-by-step answer
- Number of possible three-topic combinations: .
- These combinations are the pigeonholes; the students are the pigeons.
- If every combination had at most students, the maximum total would be .
- But , so at least one combination has at least students.
- NESA: 2 marks for a correct explanation; 1 mark for evaluating or forming .
Common mistake: choosing a familiar formula before checking that its conditions, signs, interval and units match this question.
The paper records 2 total marks for this group. Where the official marking guide provides useful partial-credit criteria, those criteria are stated in the steps above.
Try your hand at it again by answering these questions
Question 1
Students choose exactly topics from . There are students. Show that at least share the same pair.
Question 2
Each of students chooses electives from . Show at least students share the same combination.
Question 3
There are possible triples from topics. How many students guarantee that at least share a triple?