[SOLVED] CS Math 340 Tutorial 1 Solutions Jordan Barrett

Math 340 Tutorial 1 Solutions Jordan Barrett
1. Consider the set of n digit numbers. How many of these numbers
(a) have an even number as the last digit? (b) have at least one repeating digit?
(c) have exactly k digits that are 9s?
Solution:
(a) There are 5 ways to choose the last digit, and 10 ways to choose the remaining n 1 digits. Hence, the answer is 5 10n1.
(b) It is easier to count the opposite, i.e. n digit numbers with no repeating digits. This is just P(10,n), which is 10! if n 10, or 0 if n > 10. Since we counted
(10n)!
the opposite, we must subtract it from the total, meaning the answer is
10n P(10,n).
(c) There are n digits to be filled, and we must fill k of them with the digit 9. The number of ways to do this is nk. With the 9s chosen, we fill the remaining n k digits, and there are 9 choices for each digit, so the number of ways to do this is 9nk. Hence, the answer is
nk 9nk.

(1 continued:)

2. Consider functions f from the set {1, 2, . . . , n} to the set {0, 1}.
(a) How many functions are there?
(b) How many functions have f(1) = 1?
(c) Howmanyfunctionshavef(k)6=f(k+1)forall1k