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 colorings of the grid, what is the maximum possible number of L-trominos that contain exactly one square of each 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 colorings of the grid, what is the maximum possible number of L-trominos that contain exactly one square of each 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 the pigeonhole principle, some color appears twice among the four squares, and there are two trominoes which 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.