The Art and Craft of Problem Solving

6.2 PARTITIONS AND BIJECTIONS 205

We can compute the exact number. Each sorority is uniquely determined by its

collection of 10 digits where repetition is allowed. For example, one (highly exclusive)

sorority can be named "ten 6s," while another is called "three 4s, a 7, two 8s, and

four 9s." So now the question becomes, in how many different ways can we choose

10 digits, with repetition allowed? Crux move #2: this is equivalent to putting 10

balls into 10 urns that are labeled 0, 1,2, ... ,9. By the balls in urns formula, this is

e:) = 92,378.

Finally, we conclude that there will be a sorority with at least

fI ,428,571 ,428 /92, 378 l = 15,465

members. This is greater than 10,000, so the answer is "yes." •

Problems and Exercises

6.2.8 (Jim Propp) Sal the Magician asks you to pick

any five cards from a standard deck.^4 You do so, and

then show them to Sal's assistant Pat, who places one

of the five cards back in the deck and then puts the re­

maining four cards into a pile. Sal is blindfolded, and

does not witness any of this. Then Sal takes off the

blindfold, takes the pile of four cards, reads the four

cards that Pat has arranged, and is able to find the fifth

card in the deck (even if you shuffle the deck after Pat

puts the card in the deck). Assume that neither Sal nor

Pat has supernatural powers, and that the deck of cards

is not marked. How is the trick done? Harder version:

you (instead of Pat) pick which of the five cards goes

back into the deck.

6.2.9 Eight people are in a room. One or more of

them get an ice-cream cone. One or more of them get

a chocolate-chip cookie. In how many different ways

can this happen, given that at least one person gets both

an ice-cream cone and a chocolate-chip cookie?

6.2. 10 How many subsets of the set {1, 2, 3,4, ... , 30}

have the property that the sum of the elements of the

subset is greater than 232?

6.2.11 How many strictly increasing sequences of

positive integers begin with I and end with lOoo?

6.2. 12 Find another way to prove the Hockey Stick

Identity (Example 6.2.5 on page 201), using the sum­

mation identity (6.1.14).

6.2. 13 For any set, prove that the number of its subsets

with an even number of elements is equal to the num­

ber of subsets with an odd number of elements. For ex­

ample, the set {a, b, c} in the problem above has four

subsets with an even number of elements (the empty

set has 0 elements, which is even), and four with an

odd number of elements.

6.2. 14 In how many ways can two squares be selected

from an 8-by-8 chessboard so that they are not in the

same row or the same column?

6.2. 15 In how many ways can four squares, not all in

the same row or column, be selected from an 8-by-8

chessboard to form a rectangle?

6.2. 16 In how many ways can we place r red balls and

w white balls in n boxes so that each box contains at

least one ball of each color?

6.2. 17 A parking lot for compact cars has 12 adjacent

spaces, and eight are occupied. A large sport-utility

vehicle arrives, needing two adjacent open spaces.

What is the probability that it will be able to park?

Generalize!

6.2.18 Find a nice formula for the sum

Can you explain why your formula is true?

6.2.19 How many ways can the positive integer n can

be written as an ordered sum of at least one positive

4A standard deck contains^52 cards. 13 denominations ( 2 , 3 , ... ,IO,J,Q,K,A) in each of four suits

(0, <::I, "',.),