Some counting problems
J ́erˆome Fortier
McGill University
January 12, 2021
Sum and product principles
Problem 1
How many possible canadian postal codes are there?
Problem 2
Show that for any finite set A, we have: P(A) = 2|A|.
Problem 3
We must choose a president for something. Among the candidates, there are 3 men and 4 women. How many choices do we have?
Problem 4
A password on some website has to contain at least 6 and at most 8 characters. There are 52 admissible characters (a-z,A-Z,0-9). How many admissible passwords are there?
The Inclusion-Exclusion Principle
The Inclusion-Exclusion Principle
Problem 5
How many bit strings of length 8 start with 1 or end with 00?
Problem 6
How many integers from 1 to 1000 are divisible by 4 or by 7?
The Complement Principle
Problem 7
How many 6-characters license plates do not contain the word ‘SEX’?
The pigeonhole principle
The pigeonhole principle
Problem 8
You have an urn with 10 balls inside of it. Balls are numbered with numbers from 1 to 10. We draw 3 balls (3 distinct numbers) and add them up. How many times do we need to do this to guarantee that the same number appears twice?
Problem 9
Take a rectangular hexagon with side 1. Put 7 points inside the hexagon (at random). Show that at least two of them have a distance ≤ 1.