The University of Sydney
School of Mathematics and Statistics
Solutions to Counting II – Week 6 Tutorials
1. If possible, compute |A ∪ B ∪ C| from the given information. If it is not possible,
explain why.
(a) |A| = 12, |B| = 13, |C| = 7, |A ∩ B| = 5, |A ∩C| = 4, |B ∩C| = 3
and |A ∩ B ∩C| = 2.
Solution: A complete Venn diagram is as shown:
A B
5 3 7
221
2
In this case, we see that it is possible to compute |A ∪ B ∪C| and it is given
by
|A ∪ B ∪C|
=|A| + |B| + |C| − |A ∩ B| − |A ∩C| − |B ∩C| + |A ∩ B ∩C|
=12 + 13 + 7 − 5 − 4 − 3 + 2 = 22.
(b) |A| = 12, |B| = 13, |C| = 7, |A ∩ B| = 10, |A ∩C| = 7, |B ∩C| = 13
and |A ∩ B ∩C| = 2.
Solution: Since |C| = 7, |B ∩C| is at most equal to 7. But |B ∩C| is given to
be 13. This contradiction shows that sets A, B,C as described in the question
do not exist. Thus it does not make sense to try to compute |A ∪ B ∪C|.
(c) |A| = 12, |B| = 13, |C| = 7, |A ∩ B| = 10, |A ∩C| = 4, |B ∩C| = 6
and |A ∩ B ∩C| = 2.
Solution: If you start to draw a Venn diagram you will eventually run into
an impossibibility. One approach gives the result shown.
A B
0 8 ?
224
?
The two question marks show impossibilities emerging. From the diagram
we can see that |B| ≥ 14, but |B| is given to be 13, which is a contradiction.
Copyright © 2024 The University of Sydney 1
(Similarly we can see that |C| ≥ 8, but |C| is given to be 7.) Thus sets A, B,C
as described in the question do not exist: it does not make sense to try to
compute |A ∪ B ∪C|.
2. In a group of 50 participants at a recent international meeting, 30 speak English,
18 speak German, 26 speak French, 9 speak both English and German, 16 speak
both English and French, 8 speak both French and German, and 47 speak at least
one of English, French or German.
(a) How many people in the group cannot speak English, French or German?
Solution: Since there are 50 participants and 47 can speak at least one of
English, French or German, we see that the number of people who cannot
speak English, French or German is 50 − 47 = 3.
(b) How many people in the group can speak all three languages?
Solution: Let E be the set of the participants who speak English, G the set
of those who speak German and F the set of those who speak French. Then
from the information, we see that |E| = 30, |G| = 18, |F| = 26, |E ∩ G| = 9,
|E ∩ F| = 16, |F ∩ G| = 8 and |E ∪ G ∪ F| = 47. We want to find |E ∩ G ∩ F|.
Now
|E ∪ G ∪ F| = |E| + |G| + |F| − |E ∩ G| − |E ∩ F| − |G ∩ F| + |E ∩ G ∩ F|,
so that
47 = 30 + 18 + 26 − 9 − 16 − 8 + |E ∩ G ∩ F|.
Thus |E ∩ G ∩ F| = 6. Hence the number of people who can speak all three
languages is 6.
3. How many numbers between 1 and 100 (inclusive) are divisible by at least one of
the numbers 3, 5 or 7?
Solution: Let A be the set of all numbers between 1 and 100 that are divisible by
3, B be the set of all numbers between 1 and 100 that are divisible by 5, and C be
the set of all numbers between 1 and 100 that are divisible by 7. Then
⌊ ⌋ ⌊ ⌋ ⌊ ⌋
100 100 100
|A| = = 33, |B| = = 20 and |C| = = 14
3 5 7
(where ⌊x⌋ is the greatest integer not exceeding x).
Now |A ∩ B| is the set of all numbers between 1 and 100 that are divisible by 3 and
5, i.e. by 15, and so ⌊ ⌋
100
|A ∩ B| = = 6.
15
Similarly, |A ∩C| is the set of all numbers between 1 and 100 that are divisible by
3 and 7, i.e. by 21, and so
⌊ ⌋
100
|A ∩C| = = 4.
21
2
Also, |B ∩ C| is the set of all numbers between 1 and 100 that are divisible by 5
and 7, i.e. by 35, and so ⌊ ⌋
100
|B ∩C| = = 2.
35
Moreover, |A ∩ B ∩C| is the set of all numbers between 1 and 100 that are divisible
by 3, 5 and 7, i.e. by 105, and so
⌊ ⌋
100
|A ∩ B ∩C| = = 0.
105
Hence the total number of numbers between 1 and 100 that are divisible by at
least one of the numbers 3, 5 or 7 is |A ∪ B ∪C| which is equal to
|A| + |B| + |C| − |A ∩ B| − |A ∩C| − |B ∩C| + |A ∩ B ∩C| = 55.
4. Given A = {1, 2, 3, 4, 5}. How many permutations (i.e. bijections) f : A → A have
the property that f (i) = i for at least one value of i?
Solution: For i = 1, 2, 3, 4, 5, let Ai be the set of permutations f : A → A such that
f (i) = i. Then |Ai | = 4!, (i = 1, 2, 3, 4, 5) |Ai ∩ A j | = 3! for i < j, |Ai ∩ A j ∩ Ak | = 2 for
i < j < k, |Ai ∩ A j ∩ Ak ∩ Al | = 1 for i < j < k < l, and |A1 ∩ · · · ∩ A5 | = 1. Hence the
number of permutations f : A → A having the property that f (i) = i for at least
one value of i is |A1 ∪ A2 ∪ A3 ∪ A4 | which is equal to
5
∑ |Ai| − ∑ |Ai ∩ A j | + ∑ |Ai ∩ A j ∩ Ak | − ∑ |Ai ∩ A j ∩ Ak ∩ Al | + |A1 ∩ · · · ∩ A5 |
i=1 i< j i< j<k i< j<k<l
= 5 × 4! − 10 × 3! + 10 × 2 − 5 + 1 = 76.
5. Use the Binomial Theorem to show that
n ( )
k n
∑ 2 k = 3n .
k=0
Solution: The Binomial Theorem says for any a, b ∈ R that
n ( )
n k n−k
(a + b) = ∑
n
ab .
k=0 k
() ()
Setting a = 2 and b = 1 gives us exactly 3n = ∑nk=0 nk 2k 1n−k = ∑nk=0 2k nk .
( )
6. Let p be a prime. Show that p | kp for all 1 ≤ k ≤ p − 1.
( )
Solution: By definition, kp is the positive integer given by
( )
p p!
= .
k k!(p − k)!
( )
We rewrite this as p! = kp k!(p − k)!. Now since p | p! of course, we get that
( )
p
p| k!(p − k)!.
k
3
Since p is prime and divides
( p) a product of positive integers, necessarily one of the
following must hold: p | k , p | k!, or p | (p − k)!. Consider the prime factorizations
via the Fundamental Theorem of Arithmetic. For any integer n such that n < p, p
cannot appear in its prime factorization (else p | n, which is impossible since n < p).
Now, as all of the terms multiplied together in both k! and (p − k)! are strictly less
than p, we conclude
( ) that p cannot divide k! and p cannot divide (p − k)!. Thus
necessarily p | kp , as desired.
7. In a soccer match between Teams A and B, the final score is n−all. At no time
during the match was Team B in the lead. In how many different ways can the
A-B scores be built up, starting at 0-0 and ending at n-n? Try the cases n = 1, 2, 3
and write down the scoring patterns. Can you guess what the answer might be
when n = 4? Find a connection between the scoring patterns and balanced strings
from the lectures.
Solution: The possible scoring patterns for n = 1, 2, 3 are as follows: (Left hand
numbers represent A’s score, right hand numbers represent B’s score.)
n = 1: 0-0,1-0,1-1.
n = 2: 0-0,1-0,1-1,2-1,2-2 and 0-0,1-0,2-0,2-1,2-2.
n = 3: 0-0,1-0,1-1,2-1,3-1,3-2,3-3; 0-0,1-0,1-1,2-1,2-2,3-2,3-3 ;
0-0,1-0,2-0,2-1,2-2,3-2,3-3; 0-0,1-0,2-0,2-1,3-1,3-2,3-3
and 0-0,1-0,2-0,3-0,3-1,3-2,3-3.
Hence there is 1 scoring pattern when n = 1, 2 when n = 2, and 5 when n = 3.
When n = 4 there are 14 scoring patterns, as the number of scoring patterns, for
any n, is the Catalan number cn .
A good way of illustrating the scoring patterns is by plotting a path between points
with integer coefficients in the xy plane. For example, for n = 1, 2, 3, the scoring
patterns are represented as follows:
n=1 n=2
n=3
The connection between this problem and balanced strings is as follows. Associate
a left bracket “(” with every unit move to the right, and a right bracket “)” with
every unit move upwards.