HMMT 二月 2020 · COMB 赛 · 第 3 题
HMMT February 2020 — COMB Round — Problem 3
题目详情
英文原题
- Each unit square of a 4 × 4 square grid is colored either red, green, or blue. Over all possible coloringsof the grid, what is the maximum possible number of L-trominos that contain exactly one square ofeach color? (L-trominos are made up of three unit squares sharing a corner, as shown below.)
解析
英文解析
- Each unit square of a 4 × 4 square grid is colored either red, green, or blue. Over all possible coloringsof the grid, what is the maximum possible number of L-trominos that contain exactly one square ofeach color? (L-trominos are made up of three unit squares sharing a corner, as shown below.)
Proposed by: Andrew Lin
Answer: 18
Solution: Notice that in each 2 × 2 square contained in the grid, we can form 4 L-trominoes. By thepigeonhole principle, some color appears twice among the four squares, and there are two trominoeswhich contain both. Therefore each 2 × 2 square contains at most 2 L-trominoes with distinct colors.
Equality is achieved by coloring a square ( x, y ) red if x + y is even, green if x is odd and y is even,
and blue if x is even and y is odd. Since there are nine 2 × 2 squares in our 4 × 4 grid, the answer is
9 × 2 = 18.