(1) Let

k be any positive integer. Prove that there exists a positive

integer multiple n of k such that the only digits in n are 0s and

1s. (Use the pigeonhole principle.)

(2) A ternary string is a sequence of 0s, 1s and 2s. How many

ternary strings of length 12 are there? How many of those

strings contain exactly five 0s, three 1s and four 2s? How many

ternary strings of length 12 contain an odd number of 1s?

(3) Prove the binomial identity

X

n

i=0

n

i

2

=

2

n

n

.

(4) A committee of seven people is to be chosen from twelve married

couples. How many ways can a committee of three men and four

women be chosen? How many ways can a committee containing

no married couple be chosen? How many ways can a committee

containing exactly two married couples be chosen?

(5) Find the number of non-negative integer solutions of

x

1 + x2 + x3 + x4 + x5 = 7.

How many of those solutions have xi 0 for all i?