PUMaC 2009 · 团队赛 · 第 5 题

PUMaC 2009: The Team Round Solutions 1 Across 2 3 4 • 1 Across There is only one square number n that can be written in the form 1+ p + p + p + p . It can also be expressed as k ! + 1 for some k ∈ N . What is the square number n ? (3 characters; 2 points) Solution. 121. This is extremely easy to figure out, especially if you notice the fact that the answer is a 3-digit number. There are only two 3-digit numbers of the form k ! + 1 for some natural number k , and these are 5! + 1 = 121, and 6! + 1 = 721. Notice that only the first one is a perfect square, so that has to be the answer. To check, you can also note that for p = 3, 2 3 4 you get 1 + 3 + 3 + 3 + 3 = 1 + 3 + 9 + 27 + 81 = 121. 1 1 1 2 2 2 • 4 Across For integers 1 ≤ k ≤ 96 let a = + + . . . + . Find a + a + a + . . . + a . k 1 1 2 96 k k +1 96 (3 characters; 4 points) 2 2 2 1 2 2 Solution. 192. When we expand out a + a + . . . + a , the term appears only in a , . . . , a , 2 1 2 96 1 n n 2 2 2 and the term with m < n appears only in a , . . . , a . Therefore, 1 m m · n 1

96 ∑ ∑ 1 2 2 2 2 a + a + . . . + a = × n + × m 1 2 96 2 n m · n n =1 1 ≤ m<n ≤ 96 96 96 n − 1 ∑ ∑ ∑ 1 2 = + n n n =1 n =1 m =1 96 96 ∑ ∑ 1 2( n − 1) = + n n n =1 n =1 96 ∑ 2 n − 1 = . n n =1 Therefore 96 96 ∑ ∑ 1 2 n − 1 2 2 2 a + a + a + . . . + a = + = 192 . 1 1 2 96 n n n =1 n =1 • 6 Across For a finite set M we define the power set of M to be the set of all subsets of M , and we denote the power set of M by P ( M ). For a set M with 4 elements, determine the number of functions f : P ( M ) → P ( M ) that satisfy the relation f ( A ) ∪ f ( B ) = f ( A ∪ B ) for any sets A, B ∈ P ( M ). (5 characters; 5 points) Solution. 83521. Denote the four elements by a , b , c , d , then according to the relation, the values of f ( { a } ), f ( { b } ), f ( { c } ), f ( { d } ) uniquely determine the values of f at all non-empty sets in P ( M ). Since f ( A ) ∪ f ( ∅ ) = f ( A ) ∀ A ∈ P ( M ) , each of f ( { a } ), f ( { b } ), f ( { c } ), f ( { d } ) must contain f ( ∅ ). Counting according to the number of elements inside f ( ∅ ), we get the total number of functions satisfying the condition: ( ) ( ) ( ) ( ) ( ) 4 4 4 4 4 4 4 3 4 2 4 1 4 0 4 (2 ) × + (2 ) × + (2 ) × + (2 ) × + (2 ) × = 83521 . 0 1 2 3 4 • 7 Across A line drawn from vertex A of equilateral 4 ABC meets BC at D and the circumcircle at P . If BP = 55 and P C = 220, find AD . (3 characters; 4 points) Solution. 231. By Ptolemy’s Theorem, AB · P C + AC · P B = BC · P A. Since 4 ABC is equilateral, P A = P B + P C = 275. ◦ Also, ∠ BP D = ∠ AP C = 60 , ∠ P BD = ∠ P AC = ⇒ 4 P BD ∼ 4 P AC , and so we get P B P D 55 × 220 = = ⇒ P D = = 44. P A P C 275 Therefore, AD = P A − P D = 231. 2

• 8 Across We define a binary operation on the integers : x § y , such that:

1. x § 0 = x , for all x .
2. ( x + 1) § y + x § ( y + 1) = 3( x § y ) − xy + 2 y for all integers x , y . Find 178 § 255. (5 characters; 5 points) Solution. 45313. We can prove this easily by induction. The claim is, for all y , we have x § y = xy + x − y for all x . First of all, note that the case y = 0 is given. Also, we can show the case y = 1, from the second condition, by noting that ( x + 1) § 0 + x § 1 = 3( x § 0) = ⇒ x + 1 + x § 1 = 3 x = ⇒ x § 1 = 2 x − 1 for all x . So we have proven the case y = 1. Suppose the claim is true for some y . We will show that it is true for y + 1 as well. To this end, note that ( x +1) § y + x § ( y +1) = 3( x § y ) − xy +2 y , i.e. ( x +1) y + x +1 − y + x § ( y +1) = 3 xy +3 x − 3 y − xy +2 y , whence we get x § ( y + 1) = xy + 2 x − y − 1 = x ( y + 1) + x − ( y + 1) for all x , and so the claim is proven. Hence, for all x and y , we get x § y = xy + x − y . In particular, we get 178 § 255 = 178 · 255 + 178 − 255 = 45313. • 9 Across Suppose n is the number of 5-digit numbers that can be formed with at least one digit repeated. Write down the square of the sum of the digits of n . (3 characters; 3 points) Solution. 729. Consider the number of 5-digit numbers that can be formed without repeating any digit. Then, we get 9 choices for the first digit, 9 for the second as well, and then 8, 7 and 6 for the third, fourth and fifth respectively. Thus, we get the number of 5-digit numbers that can be formed without repeating a digit as 9 · 9 · 8 · 7 · 6 = 27216. Furthermore, the number 5 4 of 5-digit numbers is simply 10 − 10 (because there cannot be leading zeroes) = 99990. So, we get the number of 5-digit numbers that can be formed with at least one digit repeated as 99990 − 27216 = 72774. The sum of the digits is 27, so squaring that yields 729. 1+ x n − 1 • 11 Across The sequence x of real numbers is defined by: x = 100, x = 200, x = if n 1 2 n x n − 2 n ≥ 3. The number x can be expressed as 0 .a a a . . . a , where the a are the digits after 2009 1 2 3 m i the decimal points. Write down the entire string of digits after the decimal point of x . In 2009 your answer, ignore the decimal point, i.e. if the answer is 0 . 098765432, then write 098765432. Do not ignore leading zeroes, if any. (5 characters; 5 points) Solution. 01505. We can get a recursive definition as follows: let x = a , x = b . Then, we 1 2 1+ b a + b +1 1+ a get successively, x = , x = , x = , and x = a , x = b . Hence, the sequence 3 4 5 6 7 a ab b 1+ a + b is cyclic of order 5, and hence, x = a , x = b . Hence, we get x = . Here, 2006 2007 2009 ab 301 a = 100, b = 200, and so x = = 0 . 01505. Hence, we get our desired solution 01505. 2009 20000 • 13 Across There are 10! permutations s s . . . s of 0 , 1 , . . . , 9. How many of them satisfy 0 1 9 s ≥ k − 2 k for k = 0 , 1 , . . . , 9? (5 characters; 5 points) Solution. 13122. Consider such a permutation. Then, we must have s ≥ 7, i.e. s can only 9 9 take three values 7, 8 or 9. Suppose we fix that value. Now consider s ≥ 6. It can take 8 four values, but out of those four, one has already been taken by s . Hence, s can also take 9 8 exactly three values. Suppose we fix this value as well. We can continue right up to s ≥ 1, 3 3

which can also take 3 values. After this, there remain 3 digits and 3 possible places s , s and 0 1 s for them. The condition now adds no extra constraint to the place value, and this is just 2 a simple permutation case of putting 3 objects into 3 ordered boxes. The number of possible ways of doing this is 3!. Thus, we have to multiply all these possibilities, because given the restrictions and the fixed values, the possibilities are independent. So, the total number of 7 admissible permutations is 3 · 3! = 13122. 2 2 • 15 Across Let C be the unit circle x + y = 1. A point P is chosen randomly on the circumference of C , and another point Q is chosen randomly from the interior of C . Both these points are chosen independently and uniformly over their domains. Let R be the rectangle with sides parallel to the x and y -axes with diagonal P Q . Suppose the probability that no 1000 point of R lies outside of C is . Find k . (4 characters; 3 points) kπ Solution. 250 π . Point P = (cos θ, sin θ ) has uniform distribution in θ ∈ [0 , 2 π ]. For any given ′ P , suppose P = ( − cos θ, − sin θ ), then the largest rectangle satisfying the condition, denoted ′ by ℘ , has P P as one diagonal. Any choice of Q satisfy the condition if and only if Q lies in the interior of ℘ (since sides are parallel). Hence for a given θ , the probability that a randomly | 4 sin θ · cos θ | chosen Q result in a rectangle lies entrely inside the C is equal to . Since θ and P π are independently chosen, we take the mean over all θ ∈ [0 , 2 π ], the desired probability is: ∫ ∫ 2 π 1 1 | 4 sin θ · cos θ | 4 4 dθ = 4 sin θ d (sin θ ) = . 2 2 2 π π 2 π π 0 0 Therefore, k = 250 π . 2 Down • 2 Down There are 9 people standing in a line at a supermarket. What is the number of ways they can stand so that Arthur is ahead of Erick? [Note that standing ahead of someone means occupying any of the positions in front of him or her.] (6 characters; 3 points) Solution. 181440. The total number of ways in which this line can be formed is simply 9!, a simple permutation problem. Now, the key is in realizing that in each of these permutations, Erick either stands behind Arthur, or in front of Arthur. In fact, for every permutation that has Erick behind Arthur, there is a unique “reflection” permutation which has Arthur and Erick interchanged and the others fixed. So there is a bijection between the set of permutations where Arthur stands in front of Erick and the set of permutations where Erick stands in front of Arthur. Hence, the required answer is simply 9! / 2 = 181440. • 3 Down A school has 2009 students. The principal asks each student to submit a randomly chosen real number between 0 and 1. She then ranks these numbers in a list of decreasing order, and decides to use the 456th largest number as the fraction of students that are going to get an overall pass this year. What is the expected fraction of students that get a passing grade? Express your answer as a reduced fraction and concatenate the numerator and denominator. 1734 (For instance, if you think that the answer is , you would submit 1734274.) (6 characters; 274 5 points) Solution. 259335. There are many ways to solve this, but the simplest way is to just use symmetry. Consider the possibility that we pick exactly 2009 equispaced numbers between 0 4

i and 1, i.e. the numbers , where i runs from 1 to 2009. Suppose each student picks one of 2010 these. The key lies in realizing that any way of calculating the probabilities is going to end up being symmetric to this possibility, because each student completely randomly selects a real number, and they are uniformly distributed over the given interval. Using this symmetry argument, we can go into a nonrigorous but equally valid proof that the 456th largest number 2010 − 456 1554 259 is going to be = = . Then, we get our required answer as 259335. 2010 2010 335 • 4 Down For any n ∈ N , let S ( n ) be the sum of the digits of n . Let M = max { S ( a )+ S ( b )+ S ( c ) | a + b + c = 2009, a, b, c ∈ N } . How many triples ( a, b, c ) of natural numbers are there such that S ( a ) + S ( b ) + S ( c ) = M ? (6 characters; 10 points) Solution. 111375. Denote a = a a a a , b = b b b b , c = c c c c (where the leading digits 4 3 2 1 4 3 2 1 4 3 2 1 may be zero). Let s = a + b + c , ∀ i ∈ { 1 , 2 , 3 , 4 } . Then we want to maximize s + s + s + s i i i i 1 2 3 4 under the constraint s + 10 s + 100 s + 1000 s = 2009. By the method of freezing variables, 1 2 3 4 we see that s + s + s + s is maximized when s , s , s , s are maximized in precisely that 1 2 3 4 1 2 3 4 order. Since 0 ≤ s ≤ 27, in maximal situation, s = 19, s = 19, s = 18, s = 0. i 1 2 3 4 The equation a + b + c = 19 has 45 integral solutions satisfying 0 ≤ a , a , a ≤ 9 (when 1 1 1 1 2 3 a = 0 , . . . , 9, there are 0 , . . . , 9 solutions respectively). 1 Similarly, the equation a + b + c = 19 has 45 solutions. 2 2 2 The equation a + b + c = 18 has 55 solutions (counting by a = 0 , . . . , 9, there are 1 , . . . , 10 3 3 3 1 solutions respectively). The equation a + b + c = 0 has 1 solution. 4 4 4 Hence, by the multiplication principle, there are 45 × 45 × 55 = 111375 solutions to the given equation. • 5 Down In right 4 ABC , P and Q are on legs BC and AC , respectively, such that CP = CQ = 20. Through the point of intersection, R , of AP and BQ , a line is drawn also passing through C and meeting the hypotenuse AB at S . The extension of P Q meets line AB at T . Suppose AB = 100, and AC = 80. Then, if the length of T S is k , find k . (3 characters; 5 points) Solution. 240. By Ceva’s Theorem, we have AQ CP BS BS 2 · · = 1 = ⇒ = QC P B SA SA 3 Then, by Menelaus’ Theorem, we get AQ CP BT BT 2 · · = 1 = ⇒ = QC P B T A T A 3 Therefore, BS = 40, BT = 200, T S = 240. • 7 Down The polynomial p ( x ) is the polynomial of smallest degree which satisifies the following conditions: – The coefficients of p are integers. – All the roots of p are integers. 5

– p (0) = − 1 – p (3) = 128. Write down p (6) in base 3. (7 characters; 6 points) Solution. 2100112. The coefficients and roots of p are integers. In particular, the constant term of p is − 1, from the third condition. So, in fact, p is a monic polynomial (otherwise there would be fractional roots from the root tests), and hence, all the roots must divide − 1, and so, p ( x ) has roots only 1 and − 1, and in particular, p ( x ) has the form 2 a +1 b p ( x ) = ( x − 1) ( x + 1) where we have used the fact that the root 1 must occur with multiplicity odd in order for p ( x ) to have a constant term − 1 and not 1. We are trying to minimize 2 a + 1 + b . Now, note that 2 a +1 b 2 a +2 b +1 7 from the last condition, we have 2 · 4 = 2 = 128 = 2 , and so 2 a + 2 b + 1 = 7 = ⇒ a + b = 3. But to minimize 2 a + b + 1, it suffices to minimize a , and so a = 0 and b = 3. So 3 3 we get p ( x ) = ( x − 1)( x + 1) . Hence, p (6) = 5 · 7 = 1715, and in base 3 this is easily seen to be 2100112. • 10 Down The sidelengths of a triangle are 130, 144, and 194. What is the area of its circum- circle? (5 characters; 3 points) 2 2 2 2 Solution. 9409 π . Notice that if m = 9, n = 4, then m − n = 65, 2 mn = 72 and m + n = 97. Thus, from the form of Pythagorean triples, we know (65 , 72 , 97) is a primitive Pythagorean triple. Hence, if we scale each length by a factor of 2, then we get (130 , 144 , 194). This must also, obviously, be a Pythagorean triple. So, the hypotenuse is the side with length 194. Now, for a right-angled triangle, the circumcenter is the midpoint of the hypotenuse, and so the circumradius is just half the hypotenuse. In this case, then, R = 97, and so 2 ∆ = π · 97 = 9409 π . • 12 Down This number, known as the “Hardy-Ramanujan Number”, is the smallest positive integer that can be expressed as the sum of two cubes in two distinct ways. In other words, it 3 3 3 3 is the least n ∈ N that satisfies n = a + b = c + d for positive integers a , b , c and d , which are all distinct. We give you the following information: two of the numbers a , b , c and d are 1 and 10. (4 characters; 4 points) Solution. 1729. Suppose 1 and 10 are on the same side as the equality. Then, we must have 3 3 c + d = 1001 for some natural numbers c and d , and especially, they are both less than 10. 3 3 Then we can easily look at the possible last digits of c and the possible last digits of d such that they add up to a number with last digit 1. It is a simple exercise now to show that the sum of the cubes cannot be 1001. So it follows that 1 and 10 are on different sides of the equality, 3 3 i.e. x − y = 999 for some natural numbers x and y other than (10 , 1). Then, we may factorize 2 3 as ( x − y )[( x − y ) + 3 xy ] = 999 = 3 · 37. Then, if 37 | x − y , then clearly the factorized product is much larger than the actual value. The same holds for the possibilities x − y = 27. The only 2 remaining scenarios are x − y ∈ { 1 , 3 , 9 } . these have corresponding values of ( x − y ) + 3 xy . 2 We have, then, for the first case, x − y = 1, 1 + 3 xy = 999, which is inadmissible because 3 does not divide 998. For the second case, x − y = 3, and 9 + 3 xy = 333 = ⇒ xy = 108. So, ( y + 3) y = 108 = 12 · 9, which has the solution ( x, y ) = (12 , 9). The last case is x − y = 9, and 6

81 + 3 xy = 110 is inadmissible. So, the only solution is (12 , 9), and it is trivial to check that 3 3 3 3 12 + 1 = 10 + 9 = 1729. • 14 Down What is one fourth of the maximum number of points you can get for solving this crossword? If strategy fails you on this one, just count. (2 characters; 1 point) Solution. 25. We leave the proof as an exercise for the reader. 7