Problem 10 · AMC 8 Stretch
Stretch
Counting & Probability
Logic & Word Problems
pigeonholecasework
Color every square of a \(3 \times 9\) grid either black or white, any way you like. Show that you can always find a rectangle (using 2 of the rows and 2 of the columns) whose 4 corner squares are all the same color.
Show answer
Answer: a same-color-corner rectangle always exists
Show hints
Hint 1 of 4
A rectangle's 4 corners live in 2 columns and 2 rows. Try looking at the grid one column at a time — what can you always say about a single column of 3 squares in 2 colors?
Still stuck? Show hint 2 →
Hint 2 of 4
How many 'features' are possible? Choose 2 of the 3 rows (there are 3 ways: rows 1&2, 1&3, 2&3) and a color (2 ways). That's \(3 \times 2 = 6\) features — your boxes.
Still stuck? Show hint 3 →
Hint 3 of 4
You have 9 columns, each giving a feature, but only 6 feature-boxes.
Show solution
Approach: Pigeonhole on (row-pair, color) features — 9 columns, 6 features
- Look at any single column: 3 squares in 2 colors, so by pigeonhole at least 2 of its squares share a color. For each column record a 'feature': which two rows match, and what color they share.
- How many features are possible? 3 ways to pick the matched row-pair (1&2, 1&3, or 2&3) times 2 color choices, so \(3 \times 2 = 6\) features. Make these 6 features the boxes.
- The grid has 9 columns, each giving one feature, but only 6 boxes. Since \(9 > 6\), two columns share a feature.
- That means the same two rows have the same color in both columns — those 4 squares are the corners of a rectangle, all one color.
Mark:
· log in to save