HMMT 二月 2023 · COMB 赛 · 第 4 题

HMMT February 2023 — COMB Round — Problem 4

The cells of a 5 × 5 grid are each colored red, white, or blue. Sam starts at the bottom-left cell of the grid and walks to the top-right cell by taking steps one cell either up or to the right. Thus, he passes through 9 cells on his path, including the start and end cells. Compute the number of colorings for which Sam is guaranteed to pass through a total of exactly 3 red cells, exactly 3 white cells, and exactly 3 blue cells no matter which route he takes.

解析

The cells of a 5 × 5 grid are each colored red, white, or blue. Sam starts at the bottom-left cell of the grid and walks to the top-right cell by taking steps one cell either up or to the right. Thus, he passes through 9 cells on his path, including the start and end cells. Compute the number of colorings for which Sam is guaranteed to pass through a total of exactly 3 red cells, exactly 3 white cells, and exactly 3 blue cells no matter which route he takes. Proposed by: Sean Li Answer: 1680 Solution: Let c denote the cell in the i -th row from the bottom and the j -th column from the left, i,j so Sam starts at c and is traveling to c . The key observation (from, say, trying small cases) is that 1 , 1 5 , 5 Claim. For 1 ≤ i, j < 5, the cells c and c must be the same color. i +1 ,j i,j +1 Proof. Choose a path P from c to c , and a path Q from c to c . Then consider the two 1 , 1 i,j i +1 ,j +1 5 , 5 paths P → c → Q and P → c → Q . These both must have 3 cells of each color, but they only i +1 ,j i,j +1 differ at cells c and c . So these cells must be the same color. i +1 ,j i,j +1 Hence, every diagonal D = { c : a + b = k } must consist of cells of the same color. Moreover, any k a,b path that goes from c to c contains exactly one cell in D for k = 2 , 3 , . . . , 10. So we simply need 1 , 1 5 , 5 k to color the diagonals D , . . . , D such that there are 3 diagonals of each color. The number of ways 2 10 ( ) 9 to do this is = 1680. 3 , 3 , 3