HMMT 二月 2014 · COMB 赛 · 第 8 题

英文解析

8. The integers 1 , 2 , . . . , 64 are written in the squares of a 8 × 8 chess board, such that for each 1 ≤ i < 64,
   the numbers i and i + 1 are in squares that share an edge. What is the largest possible sum that canappear along one of the diagonals?
   Answer: 432 Our answer is 26 + 52 + 54 + 56 + 58 + 60 + 62 + 64.
   One possible configuration:
   WLOG, we seek to maximize the sum of the numbers on the main diagonal (top left to bottom right).
   If we color the squares in a checker-board pattern and use the fact that a and a + 1 lie on differentcolored squares, we notice that all numbers appearing on the main diagonal must be of the same parity.
   Consider the smallest value m on the main diagonal. All numbers from 1 to m − 1 must lie on one sideof the diagonal since the main diagonal disconnects the board into two regions, and by assumption, all
   26 25 24 23 18 17 8 7
   27 52 53 22 19 16 9 6
   28 51 54 21 20 15 10 5
   29 50 55 56 57 14 11 4
   30 49 44 43 58 13 12 3
   31 48 45 42 59 60 61 2
   32 47 46 41 40 39 62 1
   33 34 35 36 37 38 63 64
   numbers less than m cannot lie on the main diagonal. Therefore, m ≤ 29 (one more than the seventhtriangular number) But if m = 29, then the sum of the numbers on the main diagonal is at most
   29 + 51 + 53 + 55 + 57 + 59 + 61 + 63 = 428, as these numbers must be odd. Similarly, m = 27 is alsonot optimal.
   This leaves m = 28 as a possibility. But if this were the case, the only way it beats our answer is if wehave 28 + 52 + 54 + ... + 64, which would require 52 , 54 , ..., 64 to appear sequentially along the diagonal,
   forcing 28 to be in one of the corners.
   Now label the squares ( row, column ) with (1 , 1) being the top left and (8 , 8) being the bottom right.
   Assume WLOG that 28 occupies (1 , 1). Since 62 and 64 are in (7, 7) and (8, 8), respectively, we musthave 63 in (7, 8) or (8, 7), and WLOG, assume it’s in (8, 7). Since 61 is next to 60, it is not difficultto see that (7, 8) must be occupied by 1 (all numbers a between 2 and 60 must have a − 1 and a + 1
   as neighbors) . Since 1 is above the main diagonal, all numbers from 1 to 27 must also be above themain diagonal. Since there are 28 squares above the main diagonal, there is exactly one number abovethe main diagonal greater than 28.
   Notice that 61 must occupy (7 , 6) or (6 , 7). If it occupies (7 , 6), then we are stuck at (8 , 6), since itmust contain a number between 2 and 59, which is impossible. Therefore, 61 must occupy (6 , 7), andno more numbers greater than 28 can be above the main diagonal. This forces 59, 57, 55, and 53 tooccupy (6 , 5) , (5 , 4) , (4 , 3) , (3 , 2), respectively. But we see that 27 occupies (1 , 2) and 29 occupies (2 , 1),
   leaving nowhere for 51.
   This is a contradiction, so our answer is therefore optimal.
   Alternate solution : Another method of proving that m ≤ 26 is to note that each side of the diagonalhas 28 squares, 16 of which are one color and 12 of which are the other color. As the path has toalternate colors, one can make at most 13 + 12 = 25 steps before moving on the diagonal.