2014 AMC 10A Problem 4
Walking down Jane Street, Ralph passed four houses in a row, each painted a different color. He passed the orange house before the red house, and he passed the blue house before the yellow house. The blue house was not next to the yellow house. How many orderings of the colored houses are possible?
Show solution without answering
Key insight
Place blue and yellow first, since they have the most rules. Only three spot pairs keep blue first with a gap; orange and red then fit in exactly one way.
Solution
Number the four spots in the order Ralph walks past them. Blue and yellow have the most rules (blue first, and not next to each other), so place them first.
- List every pair of spots for (blue, yellow) with blue earlier:
| blue, yellow | next to each other? | allowed? |
|---|---|---|
| yes | no | |
| no | yes | |
| no | yes | |
| yes | no | |
| no | yes | |
| yes | no |
That leaves choices.
2. For each choice, two spots are still empty. Orange and red go there, and orange must come first, so there is only one way to fill them.
3. The three orders are
The answer is .
Why this works
Start with the items that have the most rules. Once they are placed, the rest often has no freedom left. A rule like "orange before red" means that of the two ways to put orange and red into two spots, only one counts.
Alternative approach
Count everything, then remove the bad cases.
- Four houses can be ordered in ways.
- In exactly half of them orange comes before red: . In half of those, blue comes before yellow: .
- Now remove the orders where blue is right before yellow. Glue "BY" into one block; with orange before red, the orders are , , . That is orders.
- So orders are left.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Number the positions to in the order Ralph passes them. The blue and yellow houses carry the tightest restrictions, so place them first: blue comes before yellow and they are not adjacent. The position pairs (blue, yellow) that are not consecutive are
For each of these, the two open positions must hold orange and red with orange first, which can be done in exactly one way. So each pair gives one ordering:
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.5)
- Prealgebra, Chapter 15: Problem-Solving Strategies (§15.2)
- Introduction to Counting & Probability, Chapter 3: Correcting for Overcounting (§3.2, §3.4)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.