[SOLVED] CS Some counting problems

Some counting problems
J erome 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.