Problem 20 · AMC 8 Stretch
Core
Counting & Probability
pigeonholecasework
Color every square of a \(3 \times 9\) grid red or blue. Show that no matter how you color it, two of the columns end up colored exactly the same.
Show answer
Answer: two columns are colored identically
Show hints
Hint 1 of 4
A column is a stack of 3 squares, each red or blue. Treat each whole column as one object, and its 3-square color pattern as the label.
Still stuck? Show hint 2 →
Hint 2 of 4
How many different ways can you color a stack of 3 squares with 2 colors? Think \(2 \times 2 \times 2\).
Still stuck? Show hint 3 →
Hint 3 of 4
There are \(2^3 = 8\) possible column patterns — your 8 boxes. The grid has 9 columns.
Show solution
Approach: Pigeonhole on column patterns — 9 columns, \(2^3 = 8\) patterns
- Each column is a stack of 3 squares, each red or blue. The number of ways to color a stack of 3 with 2 colors is \(2 \times 2 \times 2 = 2^3 = 8\). Make these 8 patterns the boxes.
- The grid has 9 columns. Sort each column into the box for its pattern.
- Since \(9 > 8\), two columns share a pattern.
- That means two columns are colored exactly the same.
Mark:
· log in to save