UNIVERSITY OF SOUTH AFRICA (UNISA)
College of Science, Engineering and Technology
⋄
ASSIGNMENT 03
Pigeonhole Principle, Relations and Closures
Year Module — 2026
⋄
Module Code: MAT2612
Module Name: Discrete Mathematics
Assignment No.: Assignment 03
Total Marks: 100
Unique Number: 202586
Module Type: Year Module
Submitted in partial fulfilment of the requirements for MAT2612
at the University of South Africa.
,UNISA | MAT2612 Assignment 03
Question 1
1.1
Twenty cards numbered 1 to 20 are placed face down on a table. Cards are se lected one at
a time and turned over, and the player loses if two of the selected cards add up to 21. Us the
pigeonhole principle to show that if 11 cards are cho sen, then the player can never win the
game. State clearly what the pigeons and the pigeonholes are.
The pigeonhole principle is used to show that if 11 cards are chosen, then the player can never
win the game.
The cards can be grouped into pairs whose numbers add up to 21:
(1, 20), (2, 19), (3, 18), (4, 17), (5, 16),
(6, 15), (7, 14), (8, 13), (9, 12), (10, 11).
There are 10 such pairs.
The pigeons are the 11 selected cards.
The pigeonholes are the 10 pairs:
{1, 20}, {2, 19}, {3, 18}, . . . , {10, 11}.
By the pigeonhole principle, if 11 cards are selected and there are only 10 pairs, then at least
two selected cards must belong to the same pair. Therefore, two selected cards must form
one of the pairs
(1, 20), (2, 19), (3, 18), . . . , (10, 11),
and for every such pair,
1 + 20 = 21, 2 + 19 = 21, 3 + 18 = 21, ..., 10 + 11 = 21.
Therefore, at least two of the 11 selected cards add up to 21. Hence, the player loses the
game.
Page 1 of 12
, UNISA | MAT2612 Assignment 03
If 11 cards are chosen, the player can never win.
1.2
A store has an introductory sale on 12 types of candy bars. A customer may choose one
bar of any five different types and will be charged no more than R1,75. Use the extended
pigeonhole principle to show that although different choices may cost different amounts,
there must be at least two different ways to choose so that the cost will be the same for
both choices. State clearly what the pigeons and the pigeonholes are.
The extended pigeonhole principle is used to show that although different choices may cost
different amounts, there must be at least two different ways to choose so that the cost will be
the same for both choices.
The customer chooses 5 different types from 12 types, so the number of possible choices is
12 12! 12! 12(11)(10)(9)(8)(7!) 12(11)(10)(9)(8)
= = = = = 792.
5 5!(12 − 5)! 5! 7! (5)(4)(3)(2)(1)(7!) 5(4)(3)(2)(1)
Therefore, 792 different choices are possible.
The total cost is no more than R1,75. Since prices are measured in cents, the possible total
costs are
R0,01, R0,02, . . . , R1,75,
giving 175 possible costs.
The pigeons are the 792 different ways of choosing 5 different types of candy bars.
The pigeonholes are the 175 possible costs.
By the extended pigeonhole principle,
792
,
175
and since
175(4) = 700, 175(5) = 875,
it follows that
792
= 5.
175
Page 2 of 12
College of Science, Engineering and Technology
⋄
ASSIGNMENT 03
Pigeonhole Principle, Relations and Closures
Year Module — 2026
⋄
Module Code: MAT2612
Module Name: Discrete Mathematics
Assignment No.: Assignment 03
Total Marks: 100
Unique Number: 202586
Module Type: Year Module
Submitted in partial fulfilment of the requirements for MAT2612
at the University of South Africa.
,UNISA | MAT2612 Assignment 03
Question 1
1.1
Twenty cards numbered 1 to 20 are placed face down on a table. Cards are se lected one at
a time and turned over, and the player loses if two of the selected cards add up to 21. Us the
pigeonhole principle to show that if 11 cards are cho sen, then the player can never win the
game. State clearly what the pigeons and the pigeonholes are.
The pigeonhole principle is used to show that if 11 cards are chosen, then the player can never
win the game.
The cards can be grouped into pairs whose numbers add up to 21:
(1, 20), (2, 19), (3, 18), (4, 17), (5, 16),
(6, 15), (7, 14), (8, 13), (9, 12), (10, 11).
There are 10 such pairs.
The pigeons are the 11 selected cards.
The pigeonholes are the 10 pairs:
{1, 20}, {2, 19}, {3, 18}, . . . , {10, 11}.
By the pigeonhole principle, if 11 cards are selected and there are only 10 pairs, then at least
two selected cards must belong to the same pair. Therefore, two selected cards must form
one of the pairs
(1, 20), (2, 19), (3, 18), . . . , (10, 11),
and for every such pair,
1 + 20 = 21, 2 + 19 = 21, 3 + 18 = 21, ..., 10 + 11 = 21.
Therefore, at least two of the 11 selected cards add up to 21. Hence, the player loses the
game.
Page 1 of 12
, UNISA | MAT2612 Assignment 03
If 11 cards are chosen, the player can never win.
1.2
A store has an introductory sale on 12 types of candy bars. A customer may choose one
bar of any five different types and will be charged no more than R1,75. Use the extended
pigeonhole principle to show that although different choices may cost different amounts,
there must be at least two different ways to choose so that the cost will be the same for
both choices. State clearly what the pigeons and the pigeonholes are.
The extended pigeonhole principle is used to show that although different choices may cost
different amounts, there must be at least two different ways to choose so that the cost will be
the same for both choices.
The customer chooses 5 different types from 12 types, so the number of possible choices is
12 12! 12! 12(11)(10)(9)(8)(7!) 12(11)(10)(9)(8)
= = = = = 792.
5 5!(12 − 5)! 5! 7! (5)(4)(3)(2)(1)(7!) 5(4)(3)(2)(1)
Therefore, 792 different choices are possible.
The total cost is no more than R1,75. Since prices are measured in cents, the possible total
costs are
R0,01, R0,02, . . . , R1,75,
giving 175 possible costs.
The pigeons are the 792 different ways of choosing 5 different types of candy bars.
The pigeonholes are the 175 possible costs.
By the extended pigeonhole principle,
792
,
175
and since
175(4) = 700, 175(5) = 875,
it follows that
792
= 5.
175
Page 2 of 12
