ASSIGNMENT 02
Total Marks: 100
Memorandum
ONLY FOR YEAR MODULE
All questions will be marked.
DO NOT USE A CALCULATOR TO OBTAIN YOUR ANSWERS-WHERE APPLICABLE, LEAVE
YOUR ANSWERS IN TERMS OF FACTORIALS, n Cr AND n Pr .
Question 1: 14 Marks
(1.1) Twenty cards numbered 1 to 20 are placed face down on a table. Cards are selected (7)
one at a time and turned over. If 2 of the cards add up to 21, the player loses. Use the
pigeonhole principle to show that if 11 cards are chosen, then the player can never
win the game. State clearly what the pigeons and the pigeonholes are.
Solution
Pair the cards according to their numbers as follows:
(1, 20), (2, 19), (3, 18), (4, 17), (5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11).
We note that the numbers on each pair of cards add up to 21.
Consider the pairs of cards adding up to 21, as the pigeonholes. There are 10 pairs. Consider the
11 cards that are chosen as the pigeons. Assign each of these cards according to its number to the
pair in which the number occurs. Since there are more pigeons (11) than pigeonholes (10), then at
least one of the pigeonholes will have 2 pigeons, i.e. two of the chosen cards will add up to 21, and
the player loses the game.
(1.2) A store has an introductory sale on 12 types of candy bars. A customer may choose (7)
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.
12
, /
Solution
A customer may pay anything from 1 cent to 175 cents for a candy bar. Let the cost of the candy
bars be the pigeonholes. Hence there are 175 pigeonholes. There are
12
= 792
5
different choices of candy bars a customer can make. Let these 792 choices be the pigeons. By the
extended pigeonhole principle, there are at least
792 − 1
+1=4+1=5
175
choices that cost the same.
Question 2: 40 Marks
Let A = {1, 2, 3, 6, 12} and define the relation R on A by aRb if and only if
a
is an integer.
b
6 3
That is, 6R2 since 2
= 3 ∈ Z but, 3R2 since 2
∈
/ Z.
(2.1) Decide with reasons if (A, R) is;
(a) Reflexive; (3)
Solution
a
Yes, because (a, a) ∈ R for all a ∈ A, since a
= 1 ∈ Z.
(b) Irreflexive; (3)
Solution
No, because (A, R) is reflexive, i.e. (a, a) ∈ R for all a ∈ A.
(c) Symmetric; (3)
Solution
No. For example, (6, 2) ∈ R while (2, 6) ∈
/ R.
(d) Asymmetric; (3)
Solution
For example, (2, 2) ∈ R.
(e) Antisymmetric; (3)
Solution
Yes. If (a, b) ∈ R, then there exists a positive integer n such that a = nb. Also, if
(b, a) ∈ R, then there exists a positive integer m such that b = ma.
Hence b = ma = mnb.
13
Total Marks: 100
Memorandum
ONLY FOR YEAR MODULE
All questions will be marked.
DO NOT USE A CALCULATOR TO OBTAIN YOUR ANSWERS-WHERE APPLICABLE, LEAVE
YOUR ANSWERS IN TERMS OF FACTORIALS, n Cr AND n Pr .
Question 1: 14 Marks
(1.1) Twenty cards numbered 1 to 20 are placed face down on a table. Cards are selected (7)
one at a time and turned over. If 2 of the cards add up to 21, the player loses. Use the
pigeonhole principle to show that if 11 cards are chosen, then the player can never
win the game. State clearly what the pigeons and the pigeonholes are.
Solution
Pair the cards according to their numbers as follows:
(1, 20), (2, 19), (3, 18), (4, 17), (5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11).
We note that the numbers on each pair of cards add up to 21.
Consider the pairs of cards adding up to 21, as the pigeonholes. There are 10 pairs. Consider the
11 cards that are chosen as the pigeons. Assign each of these cards according to its number to the
pair in which the number occurs. Since there are more pigeons (11) than pigeonholes (10), then at
least one of the pigeonholes will have 2 pigeons, i.e. two of the chosen cards will add up to 21, and
the player loses the game.
(1.2) A store has an introductory sale on 12 types of candy bars. A customer may choose (7)
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.
12
, /
Solution
A customer may pay anything from 1 cent to 175 cents for a candy bar. Let the cost of the candy
bars be the pigeonholes. Hence there are 175 pigeonholes. There are
12
= 792
5
different choices of candy bars a customer can make. Let these 792 choices be the pigeons. By the
extended pigeonhole principle, there are at least
792 − 1
+1=4+1=5
175
choices that cost the same.
Question 2: 40 Marks
Let A = {1, 2, 3, 6, 12} and define the relation R on A by aRb if and only if
a
is an integer.
b
6 3
That is, 6R2 since 2
= 3 ∈ Z but, 3R2 since 2
∈
/ Z.
(2.1) Decide with reasons if (A, R) is;
(a) Reflexive; (3)
Solution
a
Yes, because (a, a) ∈ R for all a ∈ A, since a
= 1 ∈ Z.
(b) Irreflexive; (3)
Solution
No, because (A, R) is reflexive, i.e. (a, a) ∈ R for all a ∈ A.
(c) Symmetric; (3)
Solution
No. For example, (6, 2) ∈ R while (2, 6) ∈
/ R.
(d) Asymmetric; (3)
Solution
For example, (2, 2) ∈ R.
(e) Antisymmetric; (3)
Solution
Yes. If (a, b) ∈ R, then there exists a positive integer n such that a = nb. Also, if
(b, a) ∈ R, then there exists a positive integer m such that b = ma.
Hence b = ma = mnb.
13
