Problem 24 · 1994 AJHSME
Stretch
Counting & Probability
caseworkorder-ideal
A 2 by 2 square is divided into four 1 by 1 squares. Each small square is painted green or red. In how many ways can this be done so that no green square shares its top or right side with a red square? (There may be from zero to four green squares.)
Show answer
Answer: B — 6.
Show hints
Hint 1 of 2
Translate the wordy rule into a chain reaction: 'no green touches a red on its top or right' means the instant a square is green, its top neighbor and right neighbor are FORCED green too.
Still stuck? Show hint 2 →
Hint 2 of 2
So greenness flows up and to the right. The bottom-left square is the hardest to make green (it forces the most), and the top-right is the easiest. Think about which squares MUST come along for the ride.
Show solution
Approach: green region must be closed upward and rightward
- Rephrase the constraint: green ⇒ the square above and the square to the right are green. Greenness 'climbs' toward the top-right corner.
- So the top-right square is free (nothing above or right of it), and the bottom-left is most demanding (greening it forces all four green). List the legal green sets by how far the green spreads: {none}, {TR}, {TR, TL}, {TR, BR}, {TR, TL, BR}, {all four}.
- That's 6 colorings. (16 total colorings exist, but the rule throws out the 10 that put a green below or left of a red.)
- The transferable trick: when a rule says 'if A then B must follow,' you're really counting which START sets are self-consistent — build them in order of size (smallest spread to largest) so you can't double-count or skip one. This 'closed staircase' shape is the same idea as Pascal-style monotone regions.
Mark:
· log in to save