2018 AMC 10A Problem 4

P1-10~2 minPrint

Arrangements with Restrictions Basic Counting Organized listing / direct enumeration Set up the equation/formula and compute; no special trick needed

How many ways can a student schedule $3$ mathematics courses -- algebra, geometry, and number theory -- in a $6$ -period day if no two mathematics courses can be taken in consecutive periods? (What courses the student takes during the other $3$ periods is of no concern here.)

Show solution without answering

Key insight

First choose which three periods hold math, with gaps between them; only four choices work. Then put the three different courses into those periods in 6 orders.

Solution

Split the job into two questions: which periods get math, and which course goes in each.

1. Which periods? We need three of the periods $1$ to $6$ with no two next to each other. List them in order, smallest first.
- Start with $1$ : the next can be $3$ , then $5$ or $6$ . Or the next can be $4$ , then $6$ . That gives $\{1,3,5\}$ , $\{1,3,6\}$ , $\{1,4,6\}$ .
- Start with $2$ : the only choice is $\{2,4,6\}$ .
- Start with $3$ or later: the next two would need periods $5$ and $7$ , but there is no period $7$ . Nothing works.

So there are $4$ sets of periods.
2. Which course goes where? In a chosen set, the first math period can hold any of the $3$ courses, the second any of the $2$ left, and the third the last one. That is $3 \cdot 2 \cdot 1 = 6$ orders.
3. Put it together. Each of the $4$ sets can be filled in $6$ ways: $4 \cdot 6 = 24$ .

The answer is $\boxed{\textbf{(E)}\ 24}$ .

Why this works

The "not next to each other" rule only cares about the positions, not about which course is where. So handle the positions first, where the rule lives, and then arrange the courses freely. This two-step split ("where" and then "what") works for many seating and scheduling problems.

Alternative approach

Count the bad position sets and subtract. There are $\binom{6}{3} = 20$ ways to pick three periods with no rule. List the sets that include at least one pair of neighbors: there are $16$ of them (for example $\{1,2,4\}$ , $\{3,4,5\}$ ), so $20 - 16 = 4$ good sets remain, and $4 \cdot 6 = 24$ as before. Listing the $4$ good sets directly is quicker.

Concise solution

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

First decide which periods hold math, then decide which course goes in each.

Three periods out of $1, 2, \dots, 6$ with no two consecutive: list them. Each chosen period after the first must skip at least one period, so the possibilities are
$\{1,3,5\},\ \{1,3,6\},\ \{1,4,6\},\ \{2,4,6\}.$
That is $4$ sets of periods.

For each set, the three distinct courses can be assigned to the three periods in $3! = 6$ ways.

Total: $4 \cdot 6 = 24$ . The answer is $\boxed{\textbf{(E)}\ 24}$ .

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.2)
Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)