2012 AMC 10B Problem 11

P11-15~3 minPrint

Arrangements with Restrictions Basic Counting Set up the equation/formula and compute; no special trick needed Start from the end state / desired conclusion and reverse

A dessert chef prepares the dessert for every day of a week starting with Sunday. The dessert each day is either cake, pie, ice cream, or pudding. The same dessert may not be served two days in a row. There must be cake on Friday because of a birthday. How many different dessert menus for the week are possible?

Show solution without answering

Key insight

Fill in Friday (cake) first, then work outward from it. Every other day then has 3 choices, since only the neighbor already filled in is ruled out.

Solution

1. Friday is the day with a fixed dessert, so start there. Friday is cake: $1$ choice.
2. Saturday comes right after Friday, so it must be different from cake: $3$ choices.
3. Now go backward from Friday. Thursday must differ from Friday's cake: $3$ choices.
4. Wednesday must differ from Thursday. Whatever Thursday was, that rules out exactly one dessert: $3$ choices.
5. In the same way, Tuesday differs from Wednesday, Monday differs from Tuesday, and Sunday differs from Monday: $3$ choices each.
6. Every day except Friday has $3$ choices, and there are $6$ such days:
$3 \times 3 \times 3 \times 3 \times 3 \times 3 = 3^6 = 729.$

The answer is $\boxed{\textbf{(A)}\ 729}$ .

Why this works

With a "no two days in a row the same" rule, each day has one fewer choice than the total, as long as the neighbor it is compared with has already been chosen. Starting at the fixed day and working outward keeps every step at exactly $3$ choices. Starting at Sunday instead would leave Thursday tangled up with Friday: if Thursday happened to be cake, Friday would have no choices at all.

Alternative approach

Forget the birthday for a moment. Sunday has $4$ choices and each later day has $3$ , so there are $4 \times 3^6 = 2916$ menus. The four desserts play equal roles, so Friday is cake in exactly one quarter of these menus: $2916 \div 4 = 729$ .

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Begin with the most constrained day. Friday is cake: $1$ choice.

Now move outward from Friday. Saturday must differ from Friday: $3$ choices. Thursday must differ from Friday: $3$ choices. Wednesday must differ from Thursday (whatever it is): $3$ choices. The same holds for Tuesday, Monday and Sunday, each differing from the day after it: $3$ choices apiece.

Every day except Friday contributes a factor of $3$ , so the number of menus is
$3^6 = 729.$

The answer is $\boxed{\textbf{(A)}\ 729}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
Prealgebra, Chapter 15: Problem-Solving Strategies (§15.4)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)