HMMT 二月 2002 · 团队赛 · 第 7 题

HMMT February 2002 — Team Round — Problem 7

[45] Let T = n / 9 for positive integers L . Determine all L for which T is a square L L n =1 number. Luck of the dice. Problems 8–12 concern a two-player game played on a board consisting of fourteen spaces in a row. The leftmost space is labeled START , and the rightmost space is labeled END . Each of the twelve other squares, which we number 1 through 12 from left to right, may be blank or may be labeled with an arrow pointing to the right. The term blank square will refer to one of these twelve squares that is not labeled with an arrow. The set of blank squares on the board will be called a board configuration ; the board below uses the configuration { 1 , 2 , 3 , 4 , 7 , 8 , 10 , 11 , 12 } . START ⇒ ⇒ ⇒ END 1 2 3 4 5 6 7 8 9 10 11 12 For i ∈ { 1 , 2 } , player i has a die that produces each integer from 1 to s with probability 1 /s . Here i i s and s are positive integers fixed before the game begins. The game rules are as follows: 1 2

解析

[45] Let T = n / 9 for positive integers L . Determine all L for which T is a square L L n =1 number. Solution. Since T is square if and only if 9 T is square, we may consider 9 T instead of T . L L L L 3 It is well known that n is congruent to 0, 1, or 8 modulo 9 according as n is congruent to 0, 1, 3 3 2 2 3 3 or 2 modulo 3. (Proof: (3 m + k ) = 27 m + 3(9 m ) k + 3(3 m ) k + k ≡ k (mod 9).) Therefore 2 ⌊ ⌋ 3 3 n − 9 n / 9 is 0, 1, or 8 according as n is congruent to 0, 1, or 2 modulo 3. We find therefore that ⌊ ⌋ 3 ∑ n 9 T = 9 L 9 1 ≤ n ≤ L ∑ 3 = n − # { 1 ≤ n ≤ L : n ≡ 1 (mod 3) } − 8# { 1 ≤ n ≤ L : n ≡ 2 (mod 3) } 1 ≤ n ≤ L ( ) ⌊ ⌋ ⌊ ⌋ 2 1 L + 2 L + 1 = L ( L + 1) − − 8 . 2 3 3 ( ) ( ) 2 2 Clearly 9 T < L ( L + 1) / 2 for L ≥ 1. We shall prove that 9 T > L ( L + 1) / 2 − 1 for L ≥ 4, L L whence 9 T is not square for L ≥ 4. Because L ( ) ( ) 2 2 L ( L + 1) / 2 − 1 = L ( L + 1) / 2 − L ( L + 1) + 1 , we need only show that ⌊ ⌋ ⌊ ⌋ L + 2 L + 1 2

8 ≤ L + L − 2 . 3 3 2 But the left-hand side of this is bounded above by 3 L +10 / 3, and the inequality 3 L +10 / 3 ≤ L + L − 2 2 2 means exactly L − 2 L − 16 / 3 ≥ 0 or ( L − 1) ≥ 19 / 3, which is true for L ≥ 4, as desired. Hence T is not square for L ≥ 4. By direct computation we find T = T = 0 and T = 3, so T is L 1 2 3 L square only for L ∈ { 1 , 2 } . Luck of the dice. Problems 8–12 concern a two-player game played on a board consisting of fourteen spaces in a row. The leftmost space is labeled START , and the rightmost space is labeled END . Each of the twelve other squares, which we number 1 through 12 from left to right, may be blank or may be labeled with an arrow pointing to the right. The term blank square will refer to one of these twelve squares that is not labeled with an arrow. The set of blank squares on the board will be called a board configuration ; the board below uses the configuration { 1 , 2 , 3 , 4 , 7 , 8 , 10 , 11 , 12 } . START ⇒ ⇒ ⇒ END 1 2 3 4 5 6 7 8 9 10 11 12 For i ∈ { 1 , 2 } , player i has a die that produces each integer from 1 to s with probability 1 /s . Here i i s and s are positive integers fixed before the game begins. The game rules are as follows: 1 2