PUMaC 2013 · 代数（A 组） · 第 2 题

Algebra A Solutions A1 Suppose a, b, c > 0 are integers such that abc − bc − ac − ab + a + b + c = 2013 . (A.1) Find the number of possibilities for the ordered triple ( a, b, c ) . Solution. Subtracting 1 from both sides and factoring, we obtain 2012 = ( a − 1)( b − 1)( c − 1) . (A.2) ′ ′ ′ Writing a = a − 1 and similarly with b , c , it suffices to count the ordered integer triples ′ ′ ′ ′ ′ ′ ′ ′ ′ ( a , b , c ) such that a , b , c ≥ 0 and a b c = 2012 . ′ ′ ′ Immediately, we require a , b , c > 0 . Let τ ( n ) denote the number of positive divisors of n . 2 1 The prime factorization of 2012 is 2 · 503 , so the number of possible triples is ∑ 2 2 τ ( d ) = τ (1) + τ (2) + τ (2 ) + τ (503) + τ (2 · 503) + τ (2 · 503) d | 2012 d> 0 which simplifies to 1 + 2 + 3 + 2 + 4 + 6 = 18 . A2 2 Find the number of pairs ( n, C ) of positive integers such that C ≤ 100 and n + n + C is a perfect square. Remark. This problem was inspired by the “New Year’s Problem” of the 2008-2009 Wisconsin Math Talent Search. 2 2 Solution. We can write n + n + C = ( n + m ) for some integer m ≥ 1 . Expanding and 2 rearranging, C = m + (2 m − 1) n , so we have reduced the problem to counting pairs ( m, n ) 2 of positive integers such that m + (2 m − 1) n ≤ 100 . This is ⌊ ⌋ 10 2 ∑ 100 − m = 99 + 32 + 18 + 12 + 8 + 5 + 3 + 2 + 1 + 0 (A.3) 2 m − 1 m =1 which simplifes to 180 . 1

A3 √ √ Let x = 10 and y = 3 . For all n ≥ 2 , let 1 1 √ x = x 77 + 15 y (A.4) n n − 1 n − 1 √ y = 5 x + y 77 (A.5) n n − 1 n − 1 6 4 4 2 2 2 2 4 4 6 Find x + 2 x − 9 x y − 12 x y + 27 x y + 18 y − 27 y . 5 5 5 5 5 5 5 5 5 5 2 2 Solution. Let f = x − 3 y . We factor n n n 6 4 4 2 2 2 2 4 4 6 2 2 3 2 2 2 x + 2 x − 9 x y − 12 x y + 27 x y + 18 y − 27 y = ( x − 3 y ) + 2( x − 3 y ) n n n n n n n n n n n n n n 3 2 = f + 2 f . (A.6) n n Moreover, f = 1 , and by induction, we can prove f = 2 f for all n ≥ 2 . In particular, 1 n n − 1 4 12 8 f = 2 , so the answer to the problem is 2 + 3 · 2 = 4096 + 512 = 4608 . 5 A4 3 2 Suppose a, b are nonzero integers such that two roots of x + ax + bx + 9 a coincide, and all three roots are integers. Find | ab | . Solution. Write 3 2 2 x + ax + bx + 9 a = ( x − r ) ( x − s ) (A.7) for some integers r, s . Expanding and equating coefficients, we require  2  r s = − 9 a  2 r + 2 rs = b (A.8)   2 r + s = − a 2 Combining the first and third constraints gives r s − 18 r − 9 s = 0 . Solving this quadratic 2 in r , we find that 36( s + 9) must be a perfect square, because r, s are integers. Therefore, 2 2 s + 9 = d for some d > 0 , whence ( d + s )( d − s ) = 9 . We cannot have s = 0 because this would imply a = 0 by the first constraint in the display, so the only solutions for s are ± 4 . 2 Then ( r, s ) = ± (6 , 4) , so | ab | = | (2 r + s )( r + 2 rs ) | = 1344 in both cases. 2

A5 Suppose w, x, y, z satisfy w + x + y + z = 25 (A.9) wx + wy + wz + xy + xz + yz = 2 y + 2 z + 193 (A.10) The largest possible value of w can be expressed in lowest terms as w /w for some integers 1 2 w , w > 0 . Find w + w . 1 2 1 2 Remark. This problem was inspired by USAMTS Year 21, Round 4, Problem 2. Solution. We solve the problem in greater generality. Suppose W, X, Y, Z ≥ 0 satisfy the modified system W + X + Y + Z = A (A.11) W X + W Y + W Z + XY + XZ + Y Z = B (A.12) 2 2 2 2 Expanding ( X − Y ) + ( X − Z ) + ( Y − Z ) ≥ 0 , we obtain ( X + Y + Z ) ≥ XY + XZ + Y Z . Therefore, B = W ( X + Y + Z ) + XY + XZ + Y Z 2 ( A − W ) ≤ W ( A − W ) + . (A.13) 3 After rearranging, we get the following quadratic inequality in W : 2 2 2 W − AW + ( − A + 3 B ) ≤ 0 , (A.14) √ 2 whence the largest possible value of W is ≤ ( A + 9 A − 24 B ) / 4 . But this value is actually attained at X = Y = Z , as we can see by solving the system where W + 3 X = A and 2 3 W X + 3 X = B . Setting ( W, X, Y, Z ) = ( w − 1 , x − 1 , y + 1 , z + 1) , we find that the original problem is equivalent to the problem in W, X, Y, Z with ( A, B ) = (25 , 193 + 25 − 2) = (25 , 216) . Thus, √ the largest possible value of w = W + 1 is (25 + 441 ) / 4 + 1 = 46 / 4 + 1 = 25 / 2 , giving an answer of 25 + 2 = 27 . A6 √ √ √ 3 Suppose the function ψ satisfies ψ (1) = 2 + 2 + 2 and ψ (3 x ) + 3 ψ ( x ) = ψ ( x ) for all ∏ 100 n real x . Determine the greatest integer less than ψ (3 ) . n =1 3

3 3 Solution. In order to compute ψ (3 ) , we can choose ψ to be any function that satisfies the stated conditions. In particular, if α is any real number and ψ ( x ) = 2 cos( αx ) , then 3 ψ (3 x ) = 2 cos(3 αx ) = 2(4 cos ( αx ) − 3 cos( αx )) 3 = (2 cos( αx )) − 3(2 cos( αx )) 3 = ψ ( x ) − 3 ψ ( x ) . (A.15) √ By applying the half-angle formula twice to 2 cos( π/ 4) = 2 , we find √ √ √ 2 cos( π/ 16) = 2 + 2 + 2 (A.16) so we can take α = π/ 16 = 2 π/ 32 . 8 4 2 2 n +8 n Since 3 = (3 ) ≡ ( − 15) ≡ 1 (mod 32) , we find that ψ (3 ) = ψ (3 ) for all n . Now, 4 ∏ √ n 2 cos(3 π/ 16) = 4 sin( π/ 8) cos( π/ 8) = 2 sin( π/ 4) = 2 (A.17) n =1 √ √ √ ∏ ∏ 8 100 n n 12 and similarly 2 cos (3 π/ 16) = 2 . Therefore, ψ (3 ) = 2 2 = 4096 2 . We n =5 n =1 2 check that 5792 is the largest integer whose square is ≤ 2 · 4096 . A7 Evaluate √ √ √ √ 2013 + 276 2027 + 278 2041 + 280 2055 + . . . (A.18) Remark. This problem was inspired by a theorem of Ramanujan. He famously posed the similar problem of evaluating √ √ √ √ 1 + 2 1 + 3 1 + 4 1 + . . . (A.19) in the Journal of the Indian Mathematical Society , with no response after six months. A good, albeit somewhat romanticized, place to read about Ramanujan is [ ? ]. Solution. We prove that a + N + n √ √ √ 2 2 2 = ( a + n ) + aN + N ( a + n ) + a ( N + n ) + ( N + n ) ( a + n ) + . . . (A.20) 4

for all a ∈ R and N, n ∈ Z with n | N . The result holds for N = 0 and any a, n , and if it ≥ 0 holds for an arbitrary triple ( a, N, n ) , then squaring both sides and simplifying, √ √ 2 2 N + a + 2 n = ( a + n ) + a ( N + n ) + ( N + n ) ( a + n ) + . . . (A.21) so it holds for ( a, N + n, n ) , whence induction finishes the proof. Our original problem is the case ( a, N, n ) = (7 , 276 , 2) . The answer is a + N + n = 285 . A8 The author thanks Will Sawin for his contribution to this solution . Let S be the set of permutations of { 1 , 2 , . . . , 6 } , and let T be the set of permutations of S that preserve compositions: i.e., if F ∈ T , then F ( f ◦ f ) = F ( f ) ◦ F ( f ) . (A.22) 2 1 2 1 for all f , f ∈ S . Find the number of elements F ∈ T such that if f ∈ S satisfies f (1) = 2 1 2 and f (2) = 1 , then ( F ( f ))(1) = 2 and ( F ( f ))(2) = 1 . Solution. We can, and will, write the elements of S in “cycle” notation: For example, f = (1 , 2 , 4)(3 , 5) means f (1) = 2 , f (2) = 4 , f (3) = 5 , f (4) = 1 , f (5) = 3 , f (6) = 6 . We write ι for the identity, or null, permutation. Right-to-left composition of permutations can 1 2 be expressed as left-to-right composition of cycles: For example, (1 , 2)(1 , 2) = (1 , 2) = ι and (1 , 2)(1 , 3) = (1 , 2 , 3) . In particular, every permutation can be decomposed into a composition of transpositions, not necessarily in a unique way. Moreover, all the transpositions are generated by the 6 transpositions (1 , 2) , (1 , 3) , . . . , (1 , 6) . We want to first describe T completely. For all f ∈ S , there is a uniquely associated element − 1 F ∈ T defined by F ( g ) = f ◦ g ◦ f . However, these do not account for all of T . To get f f the others, it is necessary to describe S in more detail: 6! We can classify the elements of S according to “cycle type.” For example, there are = 15 2 · 4! 6! transpositions, or type- 2 cycles; there are = 40 type- 3 cycles, such as (1 , 2 , 3) ; there 3 · 3! 6! are = 15 type- 2 , 2 , 2 cycles, such as (1 , 2)(3 , 4)(5 , 6) ; and so on. The main thing to 2 · 2 · 2 · 3! notice is that there are as many transpositions as type- 2 , 2 , 2 cycles, which suggests that a suitable bijection between them could extend to an element of T , since the transpositions generate T . 1 We introduce this change in the direction of composition because it makes the results from cycle composition more clear. 5

Let S be the set of transpositions, and let S be the set of type- 2 , 2 , 2 cycles. By the 2 2 , 2 , 2 associativity of composition of permutations, a bijection S → S extends to an element 2 2 , 2 , 2 F ∈ T if and only if it preserves compositions on S , i.e., F ( f ◦ f ) = F ( f ) ◦ F ( f ) for all 0 2 0 1 2 0 1 0 2 f , f ∈ S . The composition of two transpositions is either ι , a type- 3 cycle, or a type- 2 , 2 1 2 2 cycle. The composition of two type- 2 , 2 , 2 cycles is either ι ; a type- 2 , 2 cycle, if they share exactly one transposition; or a type- 3 , 3 cycle, if they share no transpositions. Therefore, it suffices to find a bijection S → S that sends disjoint transpositions to 2 , 2 , 2 -cycles that 2 2 , 2 , 2 share exactly 1 transposition, and transpositions with 1 number in common to type- 2 , 2 , 2 cycles that share no transpositions, such that in the latter case, the induced map on the compositions is well-defined: i.e., F ((1 , 2)(1 , 3)) = F ((2 , 3)(1 , 2)) = F ((1 , 3)(2 , 3)) . 0 0 These conditions are met if, for example, we let F be defined by 0 (1 , 2) 7 → (1 , 2)(3 , 6)(4 , 5) (1 , 3) 7 → (1 , 6)(2 , 4)(3 , 5) (1 , 4) 7 → (1 , 3)(2 , 5)(4 , 6) (A.23) (1 , 5) 7 → (1 , 5)(2 , 6)(3 , 4) (1 , 6) 7 → (1 , 4)(2 , 3)(5 , 6) . . . . . . (Our choice of the image of (1 , 2) follows the choice in [ ? ].) It is useful to note that F ◦ F 0 0 is the identity permutation on elements of S . We can check that a given element of T takes the form F for some f ∈ F if and only if it f sends isolated transpositions to isolated transpositions. Therefore, F does not arise from 0 an f in this way. However, we claim that T = { F : f ∈ S} ∪ { F ◦ F : f ∈ S} . (A.24) f f 0 First, observe that if C is the set of all elements of S of a given cycle type, then any element of T , being invertible, must map C bijectively onto another set of the same form, i.e., consisting of all elements of another given cycle type. Such a set is called a conjugacy class of elements of S . But one verifies that the only conjugacy classes of size 15 in S are S and 2 S . Altogether, if we take an arbitrary G ∈ T , then either G keeps the transpositions in 2 , 2 , 2 place or exchanges them with the type- 2 , 2 , 2 cycles; in the former case, G = F for some f f , and in the latter case, G ◦ F keeps transpositions in place, so G ◦ F = F for some f , 0 0 f whence G = G ◦ F ◦ F = F ◦ F . This proves the claim. 0 0 f 0 ′ Finally, we can compute the answer to the problem. Let S be the set of g ∈ S such that g (1) = 2 and g (2) = 1 . ′ If F maps S onto itself, then by computation, any cycle notation for f must either contain f (1 , 2) , or else cannot contain any cycles involving either 1 or 2 . There is a bijection between the possibilities for f in the former case and those in the latter case; moreover, in the latter 6

case, counting by cycle type shows there are 1 + 6 + 8 + 3 + 6 = 24 possibilities, so that ′ in total, there are 48 possibilities. Conversely, any such f yields an F that maps S onto f itself. By the example above, we know we can choose F such that F ((1 , 2)) = (1 , 2)(3 , 6)(4 , 5) . 0 0 Thus, any element F ◦ F such that F sends any one of (1 , 2) , (3 , 6) , or (4 , 5) to (1 , 2) will 0 f f ′ map S onto itself. So there are also precisely 3(48) = 144 elements of the form F ◦ F 0 f ′ that map S onto itself. Altogether the answer to the problem is 48 + 144 = 192 . Remark. For further information about this solution, we advise the reader to consult [ ? ]. For more about the mathematical objects at work in the problem, we recommend the beautiful exposition in Ch. 1-3 of [ ? ]. In particular, S and T have the structure of groups ; S is S , the symmetric group on 6 letters, and T = Aut( S ) , its automorphism group. 6 6 References [He] I. N. Herstein. Abstract Algebra . 3rd Ed., Prentice Hall (1996). [JR] G. Janusz, J. Rotman. “Outer Automorphisms of S .” Amer. Math. Mon. , Vol. 89, 6 No. 6 (1982), 407-410. [Ka] R. Kanigel. The Man Who Knew Infinity: a Life of the Genius Ramanujan . New York: Charles Scribner’s Sons (1991). ISBN 0-684-19259-4. 7