HMMT 二月 2002 · 冲刺赛 · 第 60 题

英文解析

60. A 5 × 5 square grid has the number − 3 written in the upper-left square and the number 3 written in the lower-right square. In how many ways can the remaining squaresbe filled in with integers so that any two adjacent numbers differ by 1, where two squaresare adjacent if they share a common edge (but not if they share only a corner)?
    Solution: 250 If the square in row i , column j contains the number k , let its “index”
    be i + j − k . The constraint on adjacent squares now says that if a square has index r ,
    the squares to its right and below it each have index r or r + 2. The upper-left square hasindex 5, and the lower-right square has index 7, so every square must have index 5 or 7. Theboundary separating the two types of squares is a path consisting of upward and rightwardsteps; it can be extended along the grid’s border so as to obtain a path between the lower-leftand upper-right corners. Conversely, any such path uniquely determines each square’s indexand hence the entire array of numbers — except that the two paths lying entirely along theborder of the grid fail to separate the upper-left from the lower-right square and thus do notcreate valid arrays (since these two squares should have different indices). Each path consists
    ( )
    of 5 upward and 5 rightward steps, so there are = 252 paths, but two are impossible, so 10
    the answer is 250.5
61. Bob Barker went back to school for a Ph d in math, and decided to raise theintellectual level of The Price is Right by having contestants guess how many objects existof a certain type, without going over. The number of points you will get is the percentageof the correct answer, divided by 10, with no points for going over (i.e. a maximum of 10
    points).
    Let’s see the first object for our contestants...a table of shape (5 , 4 , 3 , 2 , 1) is an arrangement of the integers 1 through 15 with five numbers in the top row, four in the next, threein the next, two in the next, and one in the last, such that each row and each column isincreasing (from left to right, and top to bottom, respectively). For instance:
    1 2 3 4 5
    6 7 8 9
    10 11 12
    13 14
    is one table. How many tables are there?15
    4 3 2
    Solution: 15! / (3 · 5 · 7 · 9) = 292864 . These are Standard Young Tableaux.
62. Our next object up for bid is an arithmetic progression of primes. For example,
    the primes 3, 5, and 7 form an arithmetic progression of length 3. What is the largestpossible length of an arithmetic progression formed of positive primes less than 1,000,000?
    Be prepared to justify your answer.
    Solution: 12 . We can get 12 with 110437 and difference 13860.15
63. Our third and final item comes to us from Germany, I mean Geometry. It is knownthat a regular n -gon can be constructed with straightedge and compass if n is a primethat is 1 plus a power of 2. It is also possible to construct a 2 n -gon whenever an n -gon isconstructible, or a p p · · · p -gon where the p ’s are distinct primes of the above form. What
    1 2 m iis really interesting is that these conditions, together with the fact that we can construct asquare, is that they give us all constructible regular n -gons. What is the largest n less than
    4,300,000,000 such that a regular n -gon is constructible?
    Solution: The known primes of this form (Fermat primes) are 3, 5, 17, 257, and 65537,
    and the result is due to Gauss (German). If there are other such primes (unknown), then
    10 9
    they are much bigger than 10 . So for each product of these primes, we can divide 4 . 3 · 10
    by that number and take log to find the largest power of 2 to multiply by, then compare theresulting numbers. There are 32 cases to check, or just observe that 2 = 4 , 294 , 967 , 296 is 322
    so close that there’s likely a shortcut. Note that 2 + 1 is divisible by 641, and hence not 32
    prime. 3 · 5 · 17 · 257 · 65537 = 2 − 1 is smaller; replacing any of the factors by the closest 32
    power of 2 only decreases the product, and there’s not enough room to squeeze in an extrafactor of 2 without replacing all of them, and that gives us 2 , so indeed that it is the 32
    answer.
    Help control the pet population. Have your pets spayed or neutered. Bye-bye.
    16