HMMT 二月 2002 · 冲刺赛 · 第 60 题
HMMT February 2002 — Guts Round — Problem 60
题目详情
- [10] 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 squares be filled in with integers so that any two adjacent numbers differ by 1, where two squares are adjacent if they share a common edge (but not if they share only a corner)? 9
- Bob Barker went back to school for a PhD in math, and decided to raise the intellectual level of The Price is Right by having contestants guess how many objects exist of a certain type, without going over. The number of points you will get is the percentage of 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 arrange- ment of the integers 1 through 15 with five numbers in the top row, four in the next, three in the next, two in the next, and one in the last, such that each row and each column is increasing (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 15 is one table. How many tables are there?
- 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 largest possi- ble length of an arithmetic progression formed of positive primes less than 1,000,000? Be prepared to justify your answer.
- Our third and final item comes to us from Germany, I mean Geometry. It is known that a regular n -gon can be constructed with straightedge and compass if n is a prime that is 1 plus a power of 2. It is also possible to construct a 2 n -gon whenever an n -gon is constructible, or a p p · · · p -gon where the p ’s are distinct primes of the above form. What 1 2 m i is really interesting is that these conditions, together with the fact that we can construct a square, 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? Help control the pet population. Have your pets spayed or neutered. Bye-bye. 10
解析
- 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 squares be filled in with integers so that any two adjacent numbers differ by 1, where two squares are 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 has index 5, and the lower-right square has index 7, so every square must have index 5 or 7. The boundary separating the two types of squares is a path consisting of upward and rightward steps; it can be extended along the grid’s border so as to obtain a path between the lower-left and upper-right corners. Conversely, any such path uniquely determines each square’s index and hence the entire array of numbers — except that the two paths lying entirely along the border of the grid fail to separate the upper-left from the lower-right square and thus do not create valid arrays (since these two squares should have different indices). Each path consists ( ) 10 of 5 upward and 5 rightward steps, so there are = 252 paths, but two are impossible, so 5 the answer is 250.
- Bob Barker went back to school for a PhD in math, and decided to raise the intellectual level of The Price is Right by having contestants guess how many objects exist of a certain type, without going over. The number of points you will get is the percentage of 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 arrange- ment of the integers 1 through 15 with five numbers in the top row, four in the next, three in the next, two in the next, and one in the last, such that each row and each column is increasing (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 15 is one table. How many tables are there? 4 3 2 Solution: 15! / (3 · 5 · 7 · 9) = 292864 . These are Standard Young Tableaux.
- 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 largest possible length of an arithmetic progression formed of positive primes less than 1,000,000? Be prepared to justify your answer. 15 Solution: 12 . We can get 12 with 110437 and difference 13860.
- Our third and final item comes to us from Germany, I mean Geometry. It is known that a regular n -gon can be constructed with straightedge and compass if n is a prime that is 1 plus a power of 2. It is also possible to construct a 2 n -gon whenever an n -gon is constructible, or a p p · · · p -gon where the p ’s are distinct primes of the above form. What 1 2 m i is really interesting is that these conditions, together with the fact that we can construct a square, 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 the 2 32 resulting numbers. There are 32 cases to check, or just observe that 2 = 4 , 294 , 967 , 296 is 32 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 power of 2 only decreases the product, and there’s not enough room to squeeze in an extra 32 factor of 2 without replacing all of them, and that gives us 2 , so indeed that it is the answer. Help control the pet population. Have your pets spayed or neutered. Bye-bye. 16