HMMT 二月 2023 · COMB 赛 · 第 6 题
HMMT February 2023 — COMB Round — Problem 6
题目详情
- Each cell of a 3 × 3 grid is labeled with a digit in the set { 1 , 2 , 3 , 4 , 5 } . Then, the maximum entry in each row and each column is recorded. Compute the number of labelings for which every digit from 1 to 5 is recorded at least once.
解析
- Each cell of a 3 × 3 grid is labeled with a digit in the set { 1 , 2 , 3 , 4 , 5 } . Then, the maximum entry in each row and each column is recorded. Compute the number of labelings for which every digit from 1 to 5 is recorded at least once. Proposed by: Evan Erickson, Luke Robitaille Answer: 2664 Solution: We perform casework by placing the entries from largest to smallest. • The grid must have exactly one 5 since an entry equal to 5 will be the maximum in its row and in its column. We can place this in 9 ways. • An entry equal to 4 must be in the same row or column as the 5; otherwise, it will be recorded twice, so we only have two records left but 1, 2, and 3 are all unrecorded. Using similar logic, there is at most one 4 in the grid. So there are 4 ways to place the 4. • We further split into cases for the 3 entries. Without loss of generality, say the 4 and the 5 are in the same row. – If there is a 3 in the same row as the 4 and the 5, then it remains to label a 2 × 3 grid with 1s 3 and 2s such that there is exactly one row with all 1s, of which there are 2(2 − 1) = 14 ways to do so. – Suppose there is no 3 in the same row as the 4 and the 5. Then there are two remaining empty rows to place a 3. There are two possible places we could have a record of 2, the remaining unoccupied row or the remaining unoccupied column. There are 2 ways to pick one of these; without loss of generality, we pick the row. Then the column must be filled with all 1s, and the remaining slots in the row with record 2 can be filled in one of 3 ways (12, 21, or 22). The final empty cell can be filled with a 1, 2, or 3, for a total of 3 ways. Our total here is 2 · 2 · 3 · 5 = 60 ways. Hence, our final answer is 9 · 4 · (14 + 60) = 36 · 74 = 2664.