PUMaC 2022 · 团队赛 · 第 20 题

Team Round Solutions We put the questions in reverse-difficulty order, and hid a message in the first letter of each problem. Happy April Fools!

1. Have b, c ∈ R satisfy b ∈ (0 , 1) and c > 0, then let A, B denote the points of intersection of 2 the line y = bx + c with y = | x | , and let O denote the origin of R . Let f ( b, c ) denote the area ∞ P 1 2 of triangle △ OAB . Let k = , and for n ≥ 1 let k = k . If the sum f ( k , k ) 0 n n n − 1 n − 1 2022 n =1 p can be written as for relatively prime positive integers p, q , find the remainder when p + q is q divided by 1000. Proposed by Sunay Joshi Answer: 484 c c Note that the points A, B have x -coordinates < 0 and > 0. Thus the area of the right − 1 − b 1 − b √ √ 2 1 c c c triangle △ OAB equals f ( b, c ) = · 2 · 2 = . As a result, the desired sum equals 2 2 1+ b 1 − b 1 − b ∞ n n P 2 2 2 k k k . We claim that this sum equals . To see this, expand the term as a n +1 2 n +1 2 2 1 − k 1 − k 1 − k n =1 ∞ P n +1 n j 2 +2 geometric series to find k . The exponents of this series contain all positive integers j =0 n n +1 n n +1 m ≡ 2 (mod 2 ). Since the set of positive integers m such that m ≡ 2 (mod 2 ) for ∞ P 2 2 ℓ k some n ≥ 1 is exactly the set of even positive integers, our sum reduces to k = , 2 1 − k ℓ =1 1 1 as claimed. Plugging in k = , we find a sum of . Thus p + q = 4088484 and our 2022 4088483 remainder is 484.
2. A triangle △ A A A in the plane has sidelengths A A = 7 , A A = 8 , A A = 9. For 0 1 2 0 1 1 2 2 0 i ≥ 0, given △ A A A , let A be the midpoint of A A and let G be the centroid of i i +1 i +2 i +3 i i +1 i ∞ △ A A A . Let point G be the limit of the sequence of points { G } . If the distance i i +1 i +2 i i =0 √ a b between G and G can be written as , where a, b, c are positive integers such that a and c 0 c 2 2 2 are relatively prime and b is not divisible by the square of any prime, find a + b + c . Proposed by Frank Lu Answer: 422 To do this, we work with vectors. Let r ⃗ be the vector between G and G . Then, notice i i i +1 1 1 that, by definition, we have that G = ( A + A + A ) , meaning that r ⃗ = ( A − A ) = i i i +1 i +2 i i +3 i 3 3 1 1 1 1 ( A − A ) . However, notice that we have that r ⃗ = ( A − A ) = ( ( A + A ) − A ) i +1 i i i +1 i i − 1 i − 2 i 6 6 6 2 1 1 1 = − ( A − A ) − ( A − A ) = r ⃗ − r ⃗ . From here, we explicitly consider one i i − 1 i − 1 i − 2 i − 1 i − 2 6 12 2 coordinate: notice then that we have the characteristic equation for, say, the x − coordinate, 1 2 i i r + r + = 0 , with the resulting solution for x = Ar + Br . But from here, notice that i 1 2 2 − 1+ i − 1 − i the solutions for r here are and . Hence, we see that the solutions for both x, y are 2 2 − 1+ i − 1 − i k k ⃗ of this form. In particular, we see that r ⃗ = a ⃗ ( ) + b ( ) . Therefore, we see that the k 2 2 ∞ P − 1+ i − 1 − i k k ⃗ vector between G and G is equal to a ⃗ ( ) + b ( ) . But using geometric series, we 0 2 2 k =0 1 1 2 2 3+ i 3 − i ⃗ ⃗ ⃗ see that this is just equal to a ⃗ + b = a ⃗ + b = a ⃗ + b . We just need − 1+ i − 1 − i 3 − i 3+ i 5 5 1 − 1 − 2 2 ⃗ to find what a ⃗ and b are. Returning to our original triangle, position our triangle such that A = (0 , 0) , A = (0 , 9) , and A has positive y − coordinate. Then, notice that we see that, if 0 2 1 2 2 2 2 A = ( x, y ) , we have that x + y = 49 , (9 − x ) + y = 64 means that − 18 x + 81 = 15 , or that 1 √ 11 8 5 − 1+ i − 1 − i ⃗ ⃗ x = , and y = . But notice then that we have that a ⃗ + b = r ⃗ and a ⃗ + b = r ⃗ . 0 1 3 3 2 2 3+ i 3 − i ⃗ Notice therefore that a ⃗ + b = 2 / 5 r ⃗ + 4 / r 5 ⃗ Simplifying this we see that this is equal 1 0 5 5 1

√ 2 1 1 1 38 8 5 to ( A − A + ( A − A ) = ( A + A − 2 A ) . But this is then equal to ( , ) . Our 1 0 2 1 2 1 0 15 15 15 15 3 3 √ √ √ √ 1 1 1 42 14 14 1 2 final answer is therefore 38 + 320 = 1444 + 320 = 1764 = = = , or 45 45 45 45 15 15 that we have 196 + 1 + 225 = 422 . 28 28 27 3. Provided that { α } are the 28 distinct roots of 29 x + 28 x + . . . + 2 x + 1 = 0, then the i i =1 28 P p 1 absolute value of can be written as for relatively prime positive integers p, q . 2 (1 − α ) q i i =1 Find p + q . Proposed by Ben Zenker Answer: 275 1 Let n = 30, and let p ( x ) denote the given polynomial. Then are the roots of the function 1 − α i x − 1 1 x − 1 n − 2 p ( ). Therefore are the roots of the polynomial q ( x ) = x p ( ), which can be x 1 − α x i written as n − 2 X k n − 2 − k q ( x ) = ( k + 1)( x − 1) x k =0 n − 2 n − 3 n − 4 Let the three leading terms of q ( x ) be denoted ax + bx + cx . By Vieta’s formulas, 2 the desired sum is given by ( − b/a ) − 2( c/a ). n n − 2 − m m We claim that the coefficient of x is given as ( − 1) ( m + 1) . To see this, note that m +2 k k +1 n − 2 − m k n − 2 − k m m the coefficient of x in ( k + 1)( x − 1) x is ( k + 1)( − 1) = ( − 1) ( m + 1) m m +1 n m by the Binomial Theorem. Summing over m ≤ k ≤ n − 2, we find ( − 1) ( m + 1) by the m +2 Hockey-Stick Identity, as claimed. − 2 n ( n − 1)( n − 2) / 6 n n n 2 It follows that a = , b = − 2 , and c = 3 . Thus b/a = = − ( n − 2) 2 3 4 n ( n − 1) / 2 3 3 n ( n − 1)( n − 2)( n − 3) / 24 1 4 2 and c/a = = ( n − 2)( n − 3). The desired sum is therefore ( n − 2) − n ( n − 1) / 2 4 9 1 1 1 ( n − 2)( n − 3), which reduces to ( n − 2)[(8 n − 16) − (9 n − 27)] = ( n − 2)(11 − n ). Plugging 2 18 18 1 266 in n = 30, the sum of squares becomes (28)( − 19) = − . Thus p = 266 , q = 9 and our 18 9 answer is 266 + 9 = 275. 4. Patty is standing on a line of planks playing a game. Define a block to be a sequence of adjacent planks, such that both ends are not adjacent to any planks. Every minute, a plank chosen uniformly at random from the block that Patty is standing on disappears, and if Patty is standing on the plank, the game is over. Otherwise, Patty moves to a plank chosen uniformly at random within the block she is in; note that she could end up at the same plank from which she started. If the line of planks begins with n planks, then for sufficiently large n , the expected number of minutes Patty lasts until the game ends (where the first plank disappears a minute after the game starts) can be written as P (1 /n ) f ( n ) + Q (1 /n ), where P, Q are polynomials P n 1 and f ( n ) = . Find P (2023) + Q (2023). i =1 i Proposed by Frank Lu Answer: 4045 Let E ( n ) be the expected value given that the block that Masie is standing on has length n. Then, notice that if the i th plank from the left disappears, then the expected number of minutes i − 1 n − i that Masie lasts afterwards is equal to E ( i )+ E ( n − i ); therefore, we see that we have that n n P P n n − 1 1 i − 1 n − i 2 2 E ( n ) = ( E ( i )+ E ( n − i )+1) . Therefore, we see that n E ( n ) = n + 2 jE ( j ) . i =1 j =0 n n n 2 2 In particular, we therefore see that ( n + 1) E ( n + 1) − n E ( n ) = 2 nE ( n ) + 2 n + 1 . Now, let nE ( n ) 2 n +1 3 1 F ( n ) = ; it therefore follows that F ( n + 1) − F ( n ) = = − . However, n +1 ( n +1)( n +2) n +2 n +1 n − 1 P 1 1 3 1 we also know that E (1) = 1 , so F (1) = . It therefore follows that F ( n ) = + − = 2 2 n +2 n +1 j =1 2

n P 1 3 1 2 3 3

• − = + 2 f ( n ) − 3 . But this means then that E ( n ) = (( n + 1) /n )( + 2 n +1 2 i n +1 n +1 j =3 2 f ( n ) − 3) = (2 + 2 /n ) f ( n ) + 3 /n − 3( n + 1) /n = (2 + 2 /n ) f ( n ) − 3 . But therefore we see that P ( x ) = 2 + 2 x, Q ( x ) = − 3 , and so therefore we have that our answer is 2 + 2 · 2023 − 3 = 4045. 2 iπ/ 13 10 iπ/ 13 16 iπ/ 13 24 iπ/ 13

5. You’re given the complex number ω = e + e + e + e , and told it’s a 3 2 root of a unique monic cubic x + ax + bx + c, where a, b, c are integers. Determine the value 2 2 2 of a + b + c . Proposed by Frank Lu Answer: 18 Observe first that the exponents of ω are precisely those of the form 2 πir/ 13 , where r is a 3 cubic residue (mod 13) . Indeed, notice that the values of r we have are r = 1 , 5 ≡ − 8 = ( − 2) 12 P 3 3 2 πij/ 13 (mod 13) , 8 = 2 , and − 1 = ( − 1) . Given as well the identity that e = − 1 , this j =1 suggests that the other two roots of this cubic are going to be the following complex numbers: 4 iπ/ 13 20 iπ/ 13 32 iπ/ 13 48 iπ/ 13 ω = e + e + e + e , 1 8 iπ/ 13 40 iπ/ 13 64 iπ/ 13 96 iπ/ 13 ω = e + e + e + e , 2 which were obtained from ω by multiplying the cubic residues by two and four. These 12 exponents, along with 0 , are 2 πi/ 13 times a complete residue class (mod 13) . (This can actually be proven with Galois theory, but this is not important for the solution itself). We now try finding the coefficients by computing ω + ω + ω, ω ω + ω ω + ω ω , ωω ω , which 1 2 1 2 1 2 1 2 are obtained by Vieta’s formulas. The first, as we mentioned before, is − 1 . For the other two, we analyze these terms by substituting the sums in and expanding out the products. For the second product, for instance, notice that we get 3 · 4 · 4 = 48 terms. We 2 πir/ 13 now consider the number of these terms that are equal to e for each residue r. Notice that this is equal to the number of cubic residues s, t so that s + 2 t ≡ r (mod 13) plus the number of cubic residues s, t so that s + 4 t ≡ r (mod 13) plus the number where 2 s + 4 t ≡ r 2 πir/ 13 (mod 13) . Each of these are obtained just from considering what it means for a term e to be obtained from one of the products. However, we claim that we can biject these solutions together. To see this, we can combine j j +1 these equations into the form s 2 + t 2 = r, where s, t are cubic residues and j ∈ { 0 , 1 , 2 } . It’s ′ ′ not hard to see then that ( s, t, j ) is a solution for r = 1 if and only if ( r s, r t, j ) is a solution ′ ′ if r is a nonzero cubic residue, and that this is a bijection between solutions. If r is twice a ′ ′ cubic residue, notice that ( s, t, j ) is a solution for r = 1 if and only if ( r s/ 2 , r t/ 2 , j + 1) is a ′ ′ solution if j = 0 , 1 , and (4 r s, 4 r t, 0) if j = 2 . A similar procedure works for four times a cubic 2 πir/ 13 residue. This means that the number of times that e appears for each nonzero residue r is the same. And as there are four solutions for r = 1 , namely 1 = ( − 1) + 2 ∗ (1) , 2 ∗ (5) + 4 ∗ (1) , 4 ∗ (8) + 8 ∗ 1 , 4 ∗ ( − 1) + 8 ∗ ( − 1) , it follows there are 4 copies of each residue, which means that this pairwise product equals − 4 . Finally, we consider ωω ω . Notice that again, the number of terms with residue r is the 1 2 number of solutions to r = s + 2 t + 4 u, where s, t, u are cubic residues. Here, we see again that all nonzero r have the same number of solutions. We just need to find the number of solutions to s + 2 t + 4 u ≡ 0 (mod 13) . Notice that by scaling up s we may assume that s = 1; from here notice that by going through the values for t the only solution we have are (1 , 8 , 12) . This 64 − 4 means there are 4 solutions for r = 0 and = 5 for all nonzero residues. 12 Therefore, we see that the value of this product is equal to 4 − 5 , as the sum of this exponential 3 2 for nonzero residues is equal to − 1 . Our polynomial is thus x + x − 4 x + 1 , and so our answer is 1 + 16 + 1 = 18 . 3

6. A sequence of integers x , x , ... is double-dipped if x = ax + bx for all n ≥ 1 and 1 2 n +2 n +1 n some fixed integers a, b . Ri begins to form a sequence by randomly picking three integers from the set { 1 , 2 , ..., 12 } , with replacement. It is known that if Ri adds a term by picking another 1 element at random from { 1 , 2 , ..., 12 } , there is at least a chance that his resulting four-term 3 sequence forms the beginning of a double-dipped sequence. Given this, how many distinct three-term sequences could Ri have picked to begin with? Proposed by Austen Mazenko Answer: 84 The main idea is that for a sequence a , a , a , a fourth term a is double-dipped only when 1 2 3 4 2 a is a particular residue modulo | a − a a | . Thus, for there to be at least 4 such values of 4 1 3 2 a , this absolute value must equal 1 , 2, or 3; this gives casework. 4 2 If x ± 1 = x x : (double at end to reverse them) (1 , 1 , 2), (1 , 2 , 3), (1 , 2 , 5), (1 , 3 , 8), (2 , 3 , 4), 1 3 2 (1 , 3 , 10), (2 , 3 , 5), (3 , 4 , 5), (2 , 5 , 12), (3 , 5 , 8), (4 , 5 , 6), (5 , 6 , 7), (6 , 7 , 8), (4 , 7 , 12), (5 , 7 , 10), (7 , 8 , 9), (8 , 9 , 10), (9 , 10 , 11), (10 , 11 , 12). 2 If x ± 2 = x x : (double at end to reverse them) (1 , 1 , 3), (1 , 2 , 2), (1 , 2 , 6), (2 , 2 , 3), (1 , 3 , 7), 1 3 2 (1 , 3 , 11), (2 , 4 , 7), (2 , 4 , 9), (3 , 4 , 6), (3 , 5 , 9), (6 , 8 , 11). 2 If x ± 3 = x x : (double at end to reverse them) (1 , 1 , 4), (2 , 1 , 2), (1 , 2 , 1), (1 , 2 , 7), (1 , 3 , 6), 1 3 2 (2 , 3 , 3), (1 , 3 , 12), (2 , 3 , 6), (3 , 3 , 4), (2 , 5 , 11), (4 , 5 , 7), (3 , 6 , 11), (7 , 9 , 12). In sum, we get 84 (note that (2 , 1 , 2) and (1 , 2 , 1) in the last case are irreversible). 1 1 2 2 2 2

7. Pick x, y, z to be real numbers satisfying ( − x + y + z ) − = 4( y − z ) , ( x − y + z ) − = 4( z − x ) , 3 4 p 2 1 2 and ( x + y − z ) − = 4( x − y ) . If the value of xy + yz + zx can be written as for relatively 5 q prime positive integers p, q , find p + q . Proposed by Sunay Joshi Answer: 1727 1 1 1 For convenience, let A = , B = , and C = . Isolating the constant on the right-hand side of 3 4 5 2 2 the first equation, we find ( − x + y + z ) − 4( y − z ) = A . By difference of squares, this becomes ( − x + 3 y − z )( − x − y + 3 z ) = A . Consider the substitution M = 3 x − y − z , N = − x + 3 y − z , P = − x − y + 3 z . Then our system reduces to N P = A , M P = B , M N = C . Multiplying the √ three together and taking the square root, we find M N P = s ABC , where s ∈ {± 1 } . Hence √ √ √ 1 1 1 M = s ABC , N = s ABC , P = s ABC . By our definition of M, N, P , we also have A B C √ √ 2 M + N + P s ABC 2 1 1 s ABC M + N + P = x + y + z , hence x = = ( + + ) = 15 and similarly 4 4 A B C 4 √ √ s ABC s ABC 2 y = 16 and z = 17 . Since s = 1, it follows that the desired quantity equals 4 4 2 2 s ABC 3 · 16 − 1 767 xy + yz + zx = (15 · 16 + 16 · 17 + 17 · 15) = = 16 16 · 60 960 Hence our answer is 767 + 960 = 1727.

8. Ryan Alweiss storms into the Fine Hall common room with a gigantic eraser and erases all n − 3 t integers n in the interval [2 , 728] such that 3 doesn’t divide n !, where t = ⌈ ⌉ . 2 Find the sum of the leftover integers in that interval modulo 1000. Proposed by Sunay Joshi Answer: 11 k t 1 2 We claim that the sum of the integers n in the interval [2 , 3 − 1] satisfying 3 | n ! is ( k + 2 k 3 − 1 t 5 k ) · − 1. To see this, first consider the condition 3 | n !. The highest power of a prime 2 n − s ( n ) p p dividing n ! is precisely ν ( n ) = , where s ( n ) denotes the sum of the digits of n in p p p − 1 4

n − s ( n ) n − 3 3 base p . Therefore t ≤ ν ( n ) is equivalent to ⌈ ⌉ ≤ . We split into two cases based 3 2 2 n − s ( n ) n − 3 3 on the parity of n . For n odd, this is ≤ , i.e. s ( n ) ≤ 3. For n even, this is 3 2 2 n − s ( n ) n − 2 3 ≤ , i.e. s ( n ) ≤ 2. In the former case, it follows that the ternary representation 3 2 2 of n must consist of either (a) one 1, (b) one 2 and one 1, or (c) three 1s. In the latter case, the ternary representation of n must consist of (d) one 2 or (e) two 1s. We now count the contribution of a given digit in the five subcases (a) through (e), where we include n = 1 among the valid numbers for convenience. (We will subtract n = 1 at the end.) One can see that the k − 1 contribution is 1 for (a), 2( k − 1)+( k − 1) = 3( k − 1) for (b), for (c), 2 for (d), and ( k − 1) for 2 k − 1 1 j 2 (e). Thus each digit 3 (0 ≤ j ≤ k − 1) contributes 1+3( k − 1)+ +2+( k − 1) = ( k +5 k ) 2 2 k 1 2 3 − 1 times its value, yielding an answer of ( k + 5 k ) · − 1, where we subtract one because we 2 2 must ignore n = 1. Plugging in k = 6, we find a total of 12011 ≡ 11 (mod 1000), our answer. 3 2 9. In the complex plane, let z , z , z be the roots of the polynomial p ( x ) = x − ax + bx − ab . 1 2 3 4 4 4 Find the number of integers n between 1 and 500 inclusive that are expressible as z + z + z 1 2 3 for some choice of positive integers a, b . Proposed by Sunay Joshi Answer: 51 3 2 4 2 2 2 For all j ∈ { 1 , 2 , 3 } , we have z = az − bz + ab . Multiplying by z , we find z = ( a − b ) z + a b . j j j j j j P P 2 2 4 4 2 Summing over j and using the fact that z = a − 2 b , we find z = a + 2 b . In other j j 4 2 words, it suffices to find the number of n ∈ [1 , 500] of the form a + 2 b for a, b ≥ 1. We first count the total number of pairs ( a, b ) satisfying the condition. 2 4 a = 1: this implies 2 b ≤ 500 − 1 , hence b ≤ 15. This yields 15 solutions. 2 4 a = 2: this implies 2 b ≤ 500 − 2 , hence b ≤ 15. This yields 15 solutions. 2 4 a = 3: this implies 2 b ≤ 500 − 3 , hence b ≤ 14. This yields 14 solutions. 2 4 a = 4: this implies 2 b ≤ 500 − 4 , hence b ≤ 11. This yields 11 solutions. 4 2 4 2 Next, we eliminate duplicates. Note that if a + 2 b = c + 2 d , then a ≡ b (mod 2). Hence it suffices to check the cases ( a, c ) = (1 , 3) and ( a, c ) = (2 , 4). 4 2 4 2 2 2 If ( a, c ) = (1 , 3), then 1 + 2 b = 3 + 2 d , implying b − d = 40. Thus the pair ( b − d, b + d ) can either be (2 , 20) or (4 , 10). These yield b = 11 and b = 7 respectively, which correspond to the duplicate solutions n = 243 and n = 99. 4 2 4 2 2 2 If ( a, c ) = (2 , 4), then 2 + 2 b = 4 + 2 d , implying b − d = 24. Thus the pair ( b − d, b + d ) can either be (2 , 12) or (4 , 6). These yield b = 7 and b = 5 respectively, which correspond to the duplicate solutions n = 114 and n = 66. Subtracting the 4 duplicates from our original count of 55 = 15 + 15 + 14 + 11, we find our answer of 51. 3 2 10. Let α, β, γ ∈ C be the roots of the polynomial x − 3 x + 3 x + 7 . For any complex number z, let f ( z ) be defined as follows: f ( z ) = | z − α | + | z − β | + | z − γ | − 2 max | z − w | . w ∈{ α,β,γ } Let A be the area of the region bounded by the locus of all z ∈ C at which f ( z ) attains its global minimum. Find ⌊ A ⌋ . Proposed by Oliver Thakar Answer: 12 √ The roots α, β, and γ are − 1 , 2 ± 3 i, which form an equilateral triangle in the complex plane. f ( z ) is simply the sum of the smaller two of the three distances between z and the vertices of 5

this triangle minus the largest of the distances. Ptolemy’s inequality tells us that f ( z ) ≥ 0 and it equals zero only when z lies on the circumcircle of the triangle with vertices α, β, γ ; clearly, the circumcenter of this triangle is at z = 1 , so the circumradius is 2. The area of the circle is 2 π · 2 , which has floor 12. 11. For the function π π g ( a ) = max cos x + cos x + + cos x + + cos( x + a ) , x ∈ R 6 4 √ √ √ m + n + p − q 2 let b ∈ R be the input that maximizes g . If cos b = for positive integers 24 m, n, p, q , find m + n + p + q . Proposed by Ben Zenker Answer: 54 By the addition formula for cosine, we may rewrite f ( x ) as π π π π f ( x ) = (1 + cos + cos + cos a ) cos x − (sin + sin + sin a ) sin x = A sin x − B sin x 6 4 6 4 √ √ A 2 2 2 2 √ Factoring out A + B , we find f ( x ) = A + B cos( x − θ ), where cos θ = . It 2 2 A + B √ 2 2 2 2 follows that g ( a ) = A + B and it suffices to maximize A + B . Expanding this expression, we find π π π π 2 2 g ( a ) = (1 + cos + cos + cos a ) + (sin + sin + sin a ) 6 4 6 4 2 2 2 2 = ( α + cos a ) + ( β + sin a ) = ( α + β + 1) + (2 α cos a + 2 β sin a ) p 2 2 2 2 = ( α + β + 1) + 2 α + β cos( a − φ ) √ √ √ 2+ 3+ 2 1+ 2 α √ where α = , β = , and cos φ = . It follows that a maximizes g iff 2 2 2 2 α + β α √ a = φ + 2 πk , k ∈ Z , where φ is any angle satisfying cos φ = . Hence the desired 2 2 α + β 2 2 quantity cos a equals cos φ , which equals √ √ √ √ √ √ √ 1 2 2 (2 + 2 + 3) (2 + 2 + 3) 18 + 2 3 + 6 − 3 2 2 4 cos φ = √ √ √ = √ √ = 1 24 ( 6 + 2 3 + 3 2 + 6) 2(2 + 2)(3 + 3) 2 Thus m = 18 , n = 12 , p = 6 , q = 18 and our answer is 18 + 12 + 6 + 18 = 54. 2 12. Observe the set S = { ( x, y ) ∈ Z : | x | ≤ 5 and − 10 ≤ y ≤ 0 } . Find the number of points P in 2 S such that there exists a tangent line from P to the parabola y = x + 1 that can be written in the form y = mx + b, where m and b are integers. Proposed by Frank Lu Answer: 15 2 First, suppose that the line y = mx + b is tangent to the parabola. Then, it follows that x +1 = 2 mx + b has exactly one solution, which in particular requires us to have that x − mx +1 − b = 0 2 m to have one solution. But from completing the square, this is only possible if 1 − b = , or 4 √ 2 that m = 2 1 − b. For m, b to be integers, notice that we must have b of the form 1 − k , so m = 2 k ; if m were odd, then 1 − b, ergo b, would not be an integer. 2 Thus, our lines are of the form y = 2 kx + (1 − k ) for some integer k ∈ Z . We now seek to classify the points ( x, y ) that lie on a line of this form. Given such a point P in our set, 2 we solve for k. Notice that solving for k here yields us with k − 1 − 2 kx + y = 0 , or that 6

p 2 k = x ± x + 1 − y. We require this to be an integer, and we are picking x, y to also be 2 2 integers. Therefore, we must have that y = x + 1 − l for some integer l, whereby we have that k = x ± l is an integer, given x is an integer. 2 To count these points: notice that x + 1 takes on the values 1 , 2 , 5 , 10 , 17 , 26 , and that the negative squares are 0 , − 1 , − 4 , − 9 , − 16 , − 25 , − 36 . We now wish to count how many pairs ( x, l ) 2 will yield a y that lies between − 10 and 0 . For x + 1 = 1 , these are − 1 , − 4 , − 9 , so there are 3 . Repeating this procedure, we find that for 2 , 5 , 10 , 17 , 26 that there are 2 , 1 , 1 , 1 , 1 , respectively. So the number of pairs ( x, y ) is thus 3 + 2 · (2 + 1 + 1 + 1 + 1) = 3 + 12 = 15 . 13. Of all functions h : Z → Z , choose one satisfying h ( ab ) = ah ( b ) + bh ( a ) for all a, b ∈ Z

0 ≥ 0 > 0 and h ( p ) = p for all prime numbers p . Find the sum of all positive integers n ≤ 100 such that h ( n ) = 4 n . Proposed by Sunay Joshi Answer: 729 Setting a = b = 1 into the functional equation, we find h (1) = 0 ̸ = 4 · 1. Thus, we may restrict our attention to n > 1. Q P k k e i We now show that if n = p > 1, then h ( n ) = ( e ) n . i i =1 i i =1 To see this, we proceed by induction on n > 1. The base case, n = 2, is evident. Suppose the result holds for all numbers less than n ; we show the result for n . If n is prime, then h ( n ) = n Q k e i by assumption, as desired. Otherwise, we may write the prime factorization n = p , i =1 i where k > 1 and e > 1 for all i . In this case, we may set a = p , b = n/p into the functional i 1 1 equation to find n n h ( n ) = p h + h ( p ) 1 1 p p 1 1 n As 1 < < n by assumption, we may apply the inductive hypothesis to find p 1 k k k X X X n n h ( n ) = p · e − 1 + · p = e − 1 n + n = e n, 1 i 1 i i p p 1 1 i =1 i =1 i =1 completing the induction. Q k e i To solve h ( n ) = 4 n for n = p , it follows that we must find all 2 ≤ n ≤ 100 for which i =1 i P k 4 3 2 2 2 e = 4. These correspond to n with the prime factorizations { p , p q, p q , p qr, pqrs } . i i =1 Considering each of these cases in turn quickly yields the list 4 4 3 3 3 3 3 2 2 2 2 2 2 2 n ∈ { 2 , 3 , 2 · 3 , 2 · 5 , 2 · 7 , 2 · 11 , 3 · 2 , 2 · 3 , 2 · 5 , 2 · 3 · 5 , 2 · 3 · 7 , 3 · 2 · 5 } = { 16 , 81 , 24 , 40 , 56 , 88 , 54 , 36 , 100 , 60 , 84 , 90 } , with sum 729. P h ( n ) Remark: in number theory, the function = e is denoted Ω( n ), and it counts the i i n number of prime factors of n with multiplicity. Numbers with Ω( n ) = k are called k -almost primes.

14. Let △ ABC be a triangle. Let Q be a point in the interior of △ ABC , and let X, Y, Z denote the feet of the altitudes from Q to sides BC , CA , AB , respectively. Suppose that BC = 15, ◦ ◦ ∠ ABC = 60 , BZ = 8, ZQ = 6, and ∠ QCA = 30 . Let line QX intersect the circumcircle p W Y of △ XY Z at the point W ̸ = X . If the ratio can be expressed as for relatively prime W Z q positive integers p, q , find p + q . Proposed by Sunay Joshi 7

Answer: 11 Let θ = ∠ W Y Z and let φ = ∠ W ZY . By the Extended Law of Sines, W Y /W Z = sin φ/ sin θ . Since W Y XZ is cyclic, ∠ W XZ = θ , and since QXBZ is cyclic, ∠ W XZ = ∠ QBZ . Hence θ = ∠ QBZ . Since △ QBZ is right with sidelengths 6, 8, 10, we have sin θ = 3 / 5. Similarly, since ◦ ∠ W ZY = ∠ W XY = ∠ QCY = 30 , sin φ = 1 / 2. The desired ratio is therefore (1 / 2) / (3 / 5) = 5 / 6 and our answer is 5 + 6 = 11. 15. Subsets S of the first 35 positive integers { 1 , 2 , 3 , ..., 35 } are called contrived if S has size 4 and the sum of the squares of the elements of S is divisible by 7. Find the number of contrived sets. Proposed by Sunay Joshi Answer: 8605 2 2 2 There are four distinct quadratic residues modulo 7, namely 0 , 1 , 2 , 4, with 0 ≡ 0, 1 , 6 ≡ 1, 2 2 2 2 3 , 4 ≡ 2, and 2 , 5 ≡ 4. There are five 4-tuples ( a , a , a , a ) with a < a < a < a 1 2 3 4 1 2 3 4 and a ∈ { 0 , 1 , 2 , 4 } satisfying a + a + a + a ≡ 0, namely (0 , 0 , 0 , 0), (0 , 1 , 2 , 4), (1 , 1 , 1 , 4), i 1 2 3 4 (1 , 2 , 2 , 2), and (2 , 4 , 4 , 4). Among the first 35 positive integers, there are 5 numbers x with 2 2 2 2 x ≡ 0, 10 numbers with x ≡ 1, 10 numbers with x ≡ 2, and 10 numbers with x ≡ 4. Thus 3 5 5 10 10 10 10 10 10 10 each 4-tuple corresponds to , , , , and subsets, respectively. 4 1 1 3 1 3 1 3 1 3 Our answer is therefore 5 + 5 · 10 + 120 · 10 + 120 · 10 + 120 · 10 = 8605. 8