HMMT 十一月 2023 · THM 赛 · 第 7 题
HMMT November 2023 — THM Round — Problem 7
题目详情
- Betty has a 3 × 4 grid of dots. She colors each dot either red or maroon. Compute the number of ways Betty can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color.
解析
- Betty has a 3 × 4 grid of dots. She colors each dot either red or maroon. Compute the number of ways Betty can color the grid such that there is no rectangle whose sides are parallel to the grid lines and whose vertices all have the same color. Proposed by: Amy Feng Answer: 408 Solution: First suppose no 3 by 1 row is all red or all blue. Then each row is either two red and one blue, or two blue and one red. There are 6 possible configurations of such a row, and as long as no row is repeated, there’s no monochromatic rectangle This gives 6 · 5 · 4 · 3 = 360 possibilities. Now suppose we have a 3 by 1 row that’s all red. Then the remaining rows must be two blue and one red, and all 3 such configurations must appear. This gives 4! = 24, and having an all blue row is also 4! = 24. The final answer is 360 + 24 + 24 = 408.