smc-1082-40-Pigeonhole

Combinatorics, EXT1 A1 2024 HSC 3 MC

Students from 4 different schools come together to form a choir.

What is the minimum size of the choir to know that there must be at least 20 students in the choir from one of the schools?

$76$
$77$
$80$
$81$

Show Answers Only

$B$

Show Worked Solution

$\text{Pigeonholes}\ (k) = 4$

$\text{Let pigeons}\ (n) = x$

$\dfrac{n}{k} = \dfrac{x}{4} \gt 19\ \ \Rightarrow \ \gt 76$

$x_{min} = 77$

$\Rightarrow B$

Combinatorics, EXT1 A1 2022 HSC 12b

A sports association manages 13 junior teams. It decides to check the age of all players. Any team that has more than 3 players above the age limit will be penalised.

A total of 41 players are found to be above the age limit.

Will any team be penalised? Justify your answer. (2 marks)

Show Answers Only

`text{Yes. By PHP, at least one team will have at least}`

`text{4 players above the limit.}`

Show Worked Solution

`text{Pigeonholes}\ (k)=13`

`text{Pigeons}\ (n)=41`

`n/k=41/13=3\ text{remainder 2}`

`:.\ text{By PHP, at least one team must have 4 players above}`

`text{the age limit and therefore at least one team will be}`

`text{penalised.}`

Combinatorics, EXT1 A1 2021 HSC 10 MC

The members of a club voted for a new president. There were 15 candidates for the position of president and 3543 members voted. Each member voted for one candidate only.

One candidate received more votes than anyone else and so became the new president.

What is the smallest number of votes the new president could have received?

Show Answers Only

`C`

Show Worked Solution

`text(Pigeonholes)\ (k) = 15`

♦♦ Mean mark 31%.

`text(Pigeons)\ (n) = 3543`

`n/k = 3543/15 = 236.2`

`text(By PHP, the minimum votes one candidate could receive = 237)`

`text(Smallest vote total for the candidate with the highest number)`

`text(of votes occurs when:)`

`text(- 12 candidates receive 236 votes and 3 candidates receive 237 votes)`

`:.\ text(The smallest number to elect a president is 238.)`

`=>\ C`

Combinatorics, EXT1 A1 2020 HSC 12c

To complete a course, a student must choose and pass exactly three topics.

There are eight topics from which to choose.

Last year 400 students completed the course.

Explain, using the pigeonhole principle, why at least eight students passed exactly the same three topics. (2 marks)

--- 6 WORK AREA LINES (style=lined) ---

Show Answers Only

`text(See Worked Solution)`

Show Worked Solution

`\ ^8C_3 = 56\ text(ways of choosing 3 topics)`

Mean mark 52%.

`text(400 students pass)`

`text(Pigeonholes)\ (k)= 56`

`text(Pigeons)\ (n) = 400`

`n/k`	`= 400/56`
	`= 7.14…`

`:.\ text(By PHP, at least 8 students passed the)`

`text(same 3 subjects.)`

Combinatorics, EXT1 A1 EQ-Bank 14

A delivery company has 1095 packages to deliver on a given day.

It has 17 delivery vans that will deliver all packages. If one van delivers more packages than all other vans, the company pays the driver a $100 bonus.

What is the minimum number of packages a van could deliver and still win the $100 bonus. (2 marks)

Show Answers Only

`66`

Show Worked Solution

`text(Pigeonholes)\ (k) = 17`

COMMENT: Note that “By PHP” refers to by pigeonhole principle.

`text(Pigeons)\ (n) = 1095`

`(n)/(k) = (1095)/(17) = 64\ text(remainder 7)`

`text(S)text(ince 7 vans could deliver 65 packages and the rest 64 packages)`

`=> \ text(By PHP, the minimum packages to win the $100 bonus = 66)`

Combinatorics, EXT1 A1 EQ-Bank 13

A sock drawer contains blue, white and green socks.

If individual socks are randomly chosen from the drawer, what is the minimum number that must be selected to ensure there are at least three pairs? (2 marks)

--- 4 WORK AREA LINES (style=lined) ---

Show Answers Only

`8`

Show Worked Solution

`text(Consider the worst-case scenario:)`

COMMENT: Note that “By PHP” refers to by pigeonhole principle.

`text{(i.e. the most socks chosen without 3 pairs)}`

`text(It is possible to choose 7 socks and only have 2 pairs)`

`=> \ text(5B, 1W, 1G (2 pairs))`

`=> \ text(3B, 3W, 1G (2 pairs))`

`text(Choosing the 8th sock produces 3 pairs in any scenario.)`

`:. \ text(By PHP, a minimum of 8 selections ensures 3 pairs.)`

Combinatorics, EXT1 A1 EQ-Bank 12

Eleven numbers are randomly chosen from the set of integers, `S`, where

`S = {1, 2, 3, 4, ..., 20}`

Prove that the sum of two of the eleven numbers randomly selected must equal 21. (2 marks)

--- 4 WORK AREA LINES (style=lined) ---

Show Answers Only

`text(Proof (Show Worked Solution))`

Show Worked Solution

`text(Rearranging)\ S\ text(into 10 pairs that sum to 21:)`

COMMENT: Note that “By PHP” refers to by pigeonhole principle.

`{1, 20}, {2, 19}, {3, 18}, …. , {10, 11}`

`text(Select one number from each pair)`

`=>\ text(10 numbers where two do not sum to 21`

`text(The 11th number chosen must complete a pair that sums to 21)`

`:. \ text(By PHP, two of the eleven numbers must sum to 21.)`

Combinatorics, EXT1 A1 SM-Bank 11

A multiple choice quiz asks students 4 questions. Each question has three possible answers, a, b or c, and students must attempt each question.

How many students must do the quiz to ensure that at least two sets of answers are identical? (2 marks)

Show Answers Only

`82`

Show Worked Solution

`text(Total possible answer combinations)`

COMMENT: Note that “By PHP” refers to by pigeonhole principle.

`= 3 xx 3 xx 3 xx 3`

`= 81`

`:. \ text(By PHP, 82 students must do the quiz. `

Combinatorics, EXT1 A1 2010 HSC 7c

A box contains `n` identical red balls and `n` identical blue balls. A selection of `r` balls is made from the box, where `0 <= r <= n`.

Explain why the number of possible colour combinations is `r + 1`. (1 mark)

--- 4 WORK AREA LINES (style=lined) ---
Another box contains `n` white balls labelled consecutively from `1` to `n`. A selection of `n − r` balls is made from the box, where `0 <= r <= n`.

Explain why the number of different selections is `((n),(r))`. (1 mark)

--- 4 WORK AREA LINES (style=lined) ---
The `n` red balls, the `n` blue balls and the `n` white labelled balls are all placed into one box, and a selection of `n` balls is made.

Using the identity, `n2^(n-1)=sum_(k=1)^n k ((n),(k)),` or otherwise, show that the number of different selections is `(n + 2)2^(n- 1)`. (3 marks)

--- 6 WORK AREA LINES (style=lined) ---

Show Answers Only

`text(Proof)\ \ text{(See Worked Solutions)}`
`text(Proof)\ \ text{(See Worked Solutions)}`
`text(Proof)\ \ text{(See Worked Solutions)}`

Show Worked Solution

♦♦♦ Mean mark 4%.
COMMENT: Solving this part required high level logical reasoning which proved extremely challenging for the vast majority of candidates.

i.	`text(1 Ball, # Combinations)`	`= 2\ text{(R or B)}`
	`text(2 Balls, # Combinations)`	`= 3\ text{(BB, BR, RR)}`
	`text(3 Balls, # Combinations)`	`= 4`

`text{(BBB, RBB, RRB, RRR)}`

`text(i.e. # Red balls could be 0, 1, 2, 3, …)`

`:.\ text(If)\ r\ text(balls chosen, # Combinations) = r + 1`

ii.

`text(# Selections when choosing)\ (n\ – r)\ text(from)\ n`

`= ((n),(n\ – r))`

♦♦♦ Mean mark 18%.

`((n),(n\ – r))`	`= (n!)/((n\ – r)!(n\ – (n\ – r))!)`
	`= (n!)/((n\ – r)! r!`
	`= ((n),(r))`

♦♦♦ Mean mark part (iii) 2%. Beast alert – equal lowest mean mark of any part of any question since this data has been available post-2009.

iii. `text(If)\ n\ text(balls are chosen,)`

`text(Let)\ r\ text(balls be red and blue and)`

`(n\ – r)\ text(balls be white labelled.)`

`=> text{# Combinations (Red and blue)} = r + 1`

`=> text{# Combinations (White)} = ((n),(r))`

`text(Any selection of)\ \ r\ \ text(red and blue balls would)`

`text(result in)\ \ (n-r)\ \ text(white balls, with) \ r=0,1,2,…`

`:.\ text{# Selections (for any given}\ r\ text{)}`

`= (r + 1)((n),(r))`

`= r ((n),(r)) + ((n),(r))`

`:.\ text{Total Selections}`	`= sum_(r=1)^n r ((n),(r)) + sum_(r=0)^n ((n),(r))`
	`= n2^(n\ – 1) + 2^n`
	`= n2^(n\ – 1) + 2*2^(n\ – 1)`
	`= (n + 2)2^(n\ – 1)\ text(… as required)`