The Art and Craft of Problem Solving

214 CHAPTER 6 COMBINATORICS

is equal to the alternating sum

1 -(a + b + ... ) -(ab + ac + ... ) + .... •

Problems and Exercises

6.3.8 In Example 6.3.2 on page 207, we assumed that

the children are distinguishable. But if we are just

counting ice cream orders, then the children are not.

For example, one order could be "Three cones of fla­

vor #16, seven of flavor #28." How many such orders

are there in this case?

6.3.9 What is wrong with the following "solution" to

Example 6.3.17

The first person can of course be cho­

sen freely, so there are eight choices. The

next person must not be that person's

partner, so there are six available. The

third person cannot be the second per­

son's partner, so there are five choices.

Thus the product is

8·6·5·4·3·2·1·1,

since the last two slots have no freedom

of choice.

6.3. 10 How many integers between 1 and 1000, inclu­

sive, are divisible by neither 2, 3, or 5?

6.3. 11 (USAMO 72) A random number generator

randomly generates the integers 1,2, ... ,9 with equal

probability. Find the probability that after n numbers

are generated, the product is a multiple of 10.

6.3.12 How many nonnegative integer solutions are

there to a + b + c + d = 17, provided that d � 12?

6.3.13 Let ai, a 2 , ... ,an be an ordered sequence of n

distinct objects. A derangement of this sequence is a

permutation that leaves no object in its original place.

For example, if the original sequence is 1 ,2,3 ,4, then

6.4 Recurrence

2,4,3,1 is not a derangement, but 2,1,4,3 is. Let Dn

denote the number of derangements of an n-element

sequence. Show that

D n =n!(I-�+�-... +(-I)n�).

I! 2! n!

6.3.14 Use a combinatorial argument (no formulas!)

to prove that

n! = ± (;)Dn-r,

r=O

where Dk is defined in the problem above.

6.3. 15 Consider 10 people sitting around a circular

table. In how many different ways can they change

seats so that each person has a different neighbor to

the right?

6.3. 16 Imagine that you are going to give n kids ice­

cream cones, one cone per kid, and there are k dif­

ferent flavors available. Assuming that no flavors get

mixed, show that the number of ways we can give out

the cones using all kfiavors is

kn -G)(k- lt + G) (k - 2t -G)(k-3t+

... +(-I)kG)on.

6.3. 17 (IMO 89) Let a permutations n of

{I, 2,. .. ,2n} have property P if

In(i)-n(i+l)1 =n

for at least one i E [2n - 1]. Show that, for each n, there

are more permutations with property P than without it.

Many problems involving the natural numbers require finding a formula or algorithm

that is true for all natural numbers n. If we are lucky, a little experimenting suggests

the general formula, and we then try to prove our conjecture. But sometimes the

problem can be so complicated that at first it is difficult to "globally" comprehend it.

The general formula may not be at all apparent. In this case, it is still possible to gain