Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

Activities 20.6 Activities
A4US

Activity 20.1.

A standard Alberta license plate has three letters followed by three or four digits.

(a)

How many different vehicles can the province license with this scheme?

(b)

Do you think the province was right to expand license plates by adding another digit, or do you think it should have added another letter instead? (Or, as a third possibility, is it irrelevant in practical terms?)
Hint.
The figure \(26^3 = 17576\) may help you decide.

Activity 20.2.

(a)

You roll a six-sided die ten times. How many different sequences of rolls are possible?

(b)

Describe how Task a relates to the problem of determining \(\card{\words{\Sigma}_{10}}\) for a suitable alphabet \(\Sigma\text{.}\)

Activity 20.3.

Let \(\Sigma = \EngAlphabet\text{.}\) How many words in \(\words{\Sigma}_5\) end in the letter \(z\text{?}\) How many do not?

Activity 20.4.

You and your five housemates pick names out of a hat each week to determine who is going to clean the toilet. Over a three-week period, how many different sequences of toilet bowl cleaners could be determined in this fashion
  1. if names are placed back in the hat after each draw?
  2. if names are not placed back in the hat after each draw?

Activity 20.5.

How many natural numbers between \(1\) and \(1,000,000\) (inclusive) contain the digit \(5\text{?}\)
Hint.
You might instead count how many numbers don’t contain the digit \(5\text{.}\)

Activity 20.6.

How many natural numbers between \(100\) and \(999\) (inclusive) have no repeated digits? Of these, how many are odd?
Hint.
There’s no rule that when you “construct” an arbitrary object of this type that you have to choose the first digit first.

Activity 20.7.

Use the Pigeonhole Principle to prove that in every set of three integers there exists a pair whose difference is even.
Hint.
What kinds of numbers add up to an even sum?

Activity 20.8.

You have a list of the names of twenty students. Ten of the students are domestic students and the other ten are out-of-province students. How many students must you select from the list to be certain to form a group that contains at least one domestic student and at least one out-of-province student?

Activity 20.9.

Let \(n\) be a fixed natural number. Determine the smallest number \(M\) for which the following statement is true: every subset of
\begin{equation*} \natnumlt{2n + 1} = \{0,1,2,3,\dotsc,2n\} \end{equation*}
of size \(M\) contains at least one odd number.

Activity 20.10.

You’re cleaning up your little nephew’s toy room. There are \(T\) toys on the floor and \(n\) empty toy storage boxes. You randomly throw toys into boxes, and when you’re done the box with the most toys contains \(N\) toys.

(a)

What is the smallest that \(N\) could be when \(T = 2 n + 1\text{?}\)

(b)

What is the smallest that \(N\) could be when \(T = k n + 1\text{?}\)

(c)

Now suppose that the number of toys \(T\) satisfies
\begin{equation*} T \lt \frac{n (n - 1)}{2} \text{.} \end{equation*}
Prove that when you are done cleaning up, there will be (at least) one pair of boxes that contain the same number of toys.
Hint.
Argue the contrapositive by assuming that every box ends up a different number of toys. What is the fewest number of toys you could have started with?
<Prev^TopNext>