HMMT 十一月 2024 · 冲刺赛 · 第 33 题
HMMT November 2024 — Guts Round — Problem 33
题目详情
- [17] A grid is called groovy if each cell of the grid is labeled with the smallest positive integer that does not appear below it in the same column or to the left of it in the same row. Compute the sum of the entries of a groovy 14 × 14 grid whose bottom left entry is 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2024, November 09, 2024 — GUTS ROUND Organization Team Team ID# 136 279 841
解析
- [17] A grid is called groovy if each cell of the grid is labeled with the smallest positive integer that does not appear below it in the same column or to the left of it in the same row. Compute the sum of the entries of a groovy 14 × 14 grid whose bottom left entry is 1. Proposed by: Jacob Paltrowitz Answer: 1638 Solution: The following diagram is the entire 16 × 16 groovy grid computed out. However, one will not need to write out every single entry to obtain the answer. 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 15 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2 14 13 16 15 10 9 12 11 6 5 8 7 2 1 4 3 13 14 15 16 9 10 11 12 5 6 7 8 1 2 3 4 12 11 10 9 16 15 14 13 4 3 2 1 8 7 6 5 11 12 9 10 15 16 13 14 3 4 1 2 7 8 5 6 10 9 12 11 14 13 16 15 2 1 4 3 6 5 8 7 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 7 8 5 6 3 4 1 2 15 16 13 14 11 12 9 10 6 5 8 7 2 1 4 3 14 13 16 15 10 9 12 11 5 6 7 8 1 2 3 4 13 14 15 16 9 10 11 12 4 3 2 1 8 7 6 5 12 11 10 9 16 15 14 13 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 We prove the following key claim. n n Claim 1. In the 2 × 2 groovy grid, each row and column is a permutation of the numbers from 1 n to 2 . Proof. We use induction on n . The base case n = 0 is clear. Now, assume that we know this for a n n n +1 n +1 n +1 n +1 2 × 2 groovy grid, and we will prove it for a 2 × 2 grid. To that end, we divide the 2 × 2 n n grid into four subgrids of size 2 × 2 . C D A B n n The subgrid labeled A is the groovy grid of size 2 × 2 , so by induction, each row and column is a n n permutation of { 1 , . . . , 2 } . Thus, the bottom left corner of the subgrid labeled B is 2 + 1, and so the n subgrid labeled B is the groovy grid where each entry is added by 2 . Hence, by induction hypothesis, n n n n each row and column of the subgrid labeled B is a permutation of { 2 + 1 , 2 + 2 , . . . , 2 + 2 } . The same argument applies for the subgrid labeled C . n Finally, the subgrid labeled D has enough numbers from 1 , 2 , . . . , 2 and does not need any number n greater than 2 . The bottom left corner is 1. Hence, it must be a groovy grid. Thus, the induction hy- n pothesis applies, and each row and column of the subgrid labeled D is a permutation of { 1 , 2 , . . . , 2 } . By considering all subgrids together, we find that each row and column of the entire grid is a permu- n +1 tation of { 1 , 2 , . . . , 2 } . In particular, we have that every row and column of the 16 × 16 grid is a permutation of { 1 , 2 , . . . , 16 } . To compute the sum of entries of the 14 × 14 grid, we can take out 2 rows and 2 columns and add back the top right 2 × 2 which we know entries 1, 2, 2, 1 by following the proof of the claim. This gives the final answer of 16 · 17 16 · 17 16 · 17 16 · − 2 · − 2 · + (1 + 2 + 2 + 1) = 1638 . 2 2 2 Remark. In fact, one can show that the entry at row x and column y is (( x − 1) ⊕ ( y − 1)) + 1, where ⊕ denotes bitwise XOR. 136 279 841