HMMT 二月 2022 · 团队赛 · 第 2 题

HMMT February 2022 — Team Round — Problem 2

[25] Find, with proof, the maximum positive integer k for which it is possible to color 6 k cells of 6 × 6 grid such that, for any choice of three distinct rows R , R , R and three distinct columns C , C , C , 1 2 3 1 2 3 there exists an uncolored cell c and integers 1 ≤ i, j ≤ 3 so that c lies in R and C . i j

解析

[25] Find, with proof, the maximum positive integer k for which it is possible to color 6 k cells of 6 × 6 grid such that, for any choice of three distinct rows R , R , R and three distinct columns C , C , C , 1 2 3 1 2 3 there exists an uncolored cell c and integers 1 ≤ i, j ≤ 3 so that c lies in R and C . i j Proposed by: Saba Lepsveridze Answer: 4 Solution: The answer is k = 4. This can be obtained with the following construction: It now suffices to show that k = 5 and k = 6 are not attainable. The case k = 6 is clear. Assume for sake of contradiction that the k = 5 is attainable. Let r , r , r be the rows of three distinct un- 1 2 3 colored cells, and let c , c , c be the columns of the other three uncolored cells. Then we can choose 1 2 3 R , R , R from { 1 , 2 , 3 , 4 , 5 , 6 } \ { r , r , r } and C , C , C from { 1 , 2 , 3 , 4 , 5 , 6 } \ { c , c , c } to obtain 1 2 3 1 2 3 1 2 3 1 2 3 a contradiction.