HMMT 二月 2024 · COMB 赛 · 第 6 题

HMMT February 2024 — COMB Round — Problem 6

In each cell of a 4 × 4 grid, one of the two diagonals is drawn uniformly at random. Compute the probability that the resulting 32 triangular regions can be colored red and blue so that any two regions sharing an edge have different colors.

解析

In each cell of a 4 × 4 grid, one of the two diagonals is drawn uniformly at random. Compute the probability that the resulting 32 triangular regions can be colored red and blue so that any two regions sharing an edge have different colors. Proposed by: Derek Liu 1 Answer: 512 Solution: Give each cell coordinates from (1 , 1) to (4 , 4) . Claim. The grid has a desired coloring if and only if every vertex not on the boundary meets an even number of edges and diagonals. Proof. If this were not the case, the odd number of regions around the vertex would have to alternate between the two colors, which is clearly impossible. In the event that every vertex has an even number of incident edges, it is not hard to show that the grid is always colorable. We claim the diagonals drawn in the cells of form (1 , a ) and ( a, 1) for 1 ≤ a ≤ 4 uniquely determine the rest (for a valid coloring to exist). Indeed, given the diagonals for any three cells around a vertex, we can uniquely determine the fourth one using the parity in the claim above. If (1 , 1) , (1 , 2) , (2 , 1) are fixed, so is (2 , 2) ; likewise so are (2 , 3) and (2 , 4) , etc. until the whole grid is fixed. The solid lines force the dotted lines as described above. Thus, once the seven cells along the top row and leftmost column are determined, the remaining nine 1 1 have a = chance of being selected in a way that admits a coloring. 9 2 512