PUMaC 2020 · 团队赛 · 第 15 题

Team Round Solutions

1. Consider a 2021-by-2021 board of unit squares. For some integer k, we say the board is tiled by k -by- k squares if it is completely covered by (possibly overlapping) k -by- k squares with their corners on the corners of the unit squares. What is the largest integer k such that the minimum number of k -by- k squares needed to tile the 2021-by-2021 board is exactly equal to 100? Proposed by: Ollie Thakar Answer: 224 Consider the set S of unit squares in the ( a, b ) position on the 2021-by-2021 board where a and b are both congruent to 1 modulo k. If 2021 = mk + r, with 0 < r ≤ k, then there are 2 ( m + 1) elements of S. Each k -by- k square in the tiling covers precisely one of these elements of S , and it is easy to see that by establishing a regular pattern, we can tile the whole board 2 with ( m + 1) of the k -by- k squares. Thus, we must find which k gives m = 9 , the largest of which is k = 224 .
2. Gary is baking cakes, one at a time. However, Gary’s not been having much success, and each failed cake will cause him to slowly lose his patience, until eventually he gives up. Initially, a 1 failed cake has a probability of 0 of making him give up. Each cake has a of turning out 2 well, with each cake independent of every other cake. If two consecutive cakes turn out well, the probability resets to 0 immediately after the second cake. On the other hand, if the cake fails, assuming that he doesn’t give up at this cake, his probability of breaking on the next failed cake goes from p to p + 0 . 5 . If the expected number of successful cakes Gary will bake p until he gives up is , for relatively prime p, q, find p + q. q Proposed by: Frank Lu Answer: 86 Let f ( p, c ) be the function giving the expected number of cakes Gary will bake until he gives up, given that his probability of giving up after the next failed cake is currently p, and his last c cakes were successful. 1 1 1 1 1 Now, note that f ( p, 0) = + (1 − p ) f ( p + 0 . 5 , 0) + f ( p, 1) , and f ( p, c ) = + (1 − p ) f ( p + 2 2 2 2 2 1 0 . 5 , 0) + f (0 , c + 1) for c ≥ 1 . Note that this equation is not defined for c > 1 if p 6 = 0 , and 2 both equations are only defined for 0 ≤ p ≤ 0 . 9 . For p = 1 , we see that the first equation is 1 1 now f (1 , 0) = (1 + f (1 , 1)) , and the second equation is f (1 , 1) = (1 + f (0 , 2)) . 2 2 We also observe that f (0 , c ) is constant for c ≥ 2 , since Gary’s probability of giving up at a given time depends only on the last two cakes he attempted to bake, as well as his probability of giving up right before baking his last cake (so Gary baking more than 2 successes in the row doesn’t alter the expected number of cakes he bakes afterwards). Thus, we see that f (0 , c ) = 1 + f (0 . 5 , 0) for c ≥ 2 , from the second equation. 3 3 Now, note that combining these two equations yields us that f ( p, 0) = + (1 − p ) f ( p + 4 4 1 3 0 . 5 , 0) + f (0 , 2) . But then we see that, solving the system yields us that f (0 , 0) = + 4 4 3 1 f (0 . 5 , 0)+ (1+ f (0 . 5 , 0)) , or that f (0 , 0) = 1+ f (0 . 5 , 0) , and similarly we see that f (0 . 5 , 0) = 4 4 3 3 1 1 4 1 1

• f (1 , 0)+ (1+ f (0 . 5 , 0)) , or that f (0 . 5 , 0) = + f (1 , 0) , and that f (1 , 0) = 1+ f (0 . 5 , 0) . 4 4 2 4 3 2 4 11 1 44 The last two equations yield us in turn that f (0 . 5 , 0) = + f (0 . 5 , 0) , or that f (0 . 5 , 0) = , 6 8 21 65 which in turn means that f (0 , 0) = , yielding an answer of 86 . 21 a b

3. Alice and Bob are playing a guessing game. Bob is thinking of a number n of the form 2 3 , where a and b are positive integers between 1 and 2020 , inclusive. Each turn, Alice guess a number m , and Bob will tell her either gcd( m, n ) or lcm( m, n ) (letting her know that he is 1

saying that gcd or lcm), as well as whether any of the respective powers match up in their prime factorization. In particular, if m = n, Bob will let Alice know this, and the game is over. Determine the smallest number k so that Alice is always able to find n within k guesses, regardless of Bob’s number or choice of revealing either the lcm , or the gcd . Proposed by: Frank Lu Answer: 11 We can consider how a lies in the range { 1 , 2 , . . . , 2020 } , as does b. Let k ( x, y ) be the number of guesses it takes, where a lies in { 1 , 2 , . . . , x } , and b lies in { 1 , 2 , . . . , y } . We first make the observation that k ( x, y ) = k ( y, x ) , by symmetry: Alice can just use the same strategy, but flipping the exponents on x, y. From here, assume WLOG that x ≥ y. First, we claim that k ( x, 1) = b log x c + 1 , which we will later refer to as the 1D case (a 2 diagram can illustrate why). To see this, note that every time Alice guesses a number, either Bob will reveal what it is, or Alice will be told that the exponent on 2 is larger or smaller. Effectively, then, the result will be like starting over from a completely different game with a narrower range. Hence, we see that k ( x, 1) is the minimum of max( k ( y − 1 , 1) , k ( x − y − 1 , 1)) , for y between 1 and x, and letting k (0 , 1) = 0 . An inductive argument can be used here to show this (like a binary search tree, effectively). We now claim that k ( x, y ) = b log max( x, y ) c + 1 , by inducting on the maximum of x, y, with 2 strong induction. Our base case for 1 is given. Now, given that we’ve shown this where max( x, y ) ≤ i − 1 , consider k ( x, y ) , where their maximum is i ≥ 2 and WLOG say x = i. We know that k ( x, y ) ≥ b log x c + 1 = k ( x, 1) , since 2 any strategy that Alice can use to guarantee in k ( x, y ) steps can be applied for the game with only the first exponent varying. We will now show the other direction. To do this, have Alice b ( i +1) / 2 c b ( y +1) / 2 c first guess 2 3 . First, if Alice guessed one of the exponents correctly, then note that the set of possible values reduces down to the 1-D case (as though Alice and Bob were playing with only one exponent varying), which Alice can guarantee in at most k ( i, 1) guesses. b ( i +1) / 2 c b ( y +1) / 2 c Otherwise, if Bob reports that the gcd or lcm of his number and Alice’s is 2 3 , then note that the set of possible values is at most i/ 2 for the exponents for 2 and y/ 2 for those of 3 . Strong induction yields that, from here, at most b log i/ 2 c + 1 guesses are needed, 2 which means that in total at most b log i c + 1 guesses are needed. 2 Finally, if Bob reports that the exponents are different, but gives a gcd or lcm that isn’t the number itself, then we see that whichever exponents differ from Alice’s guess are the exponents for Bob’s number. From here, Alice can play as though she was in the 1D case, with a range of exponents that is again at most i/ 2 . In all of these cases, we see that k ( x, y ) ≤ b log x c + 1 = 2 k ( x, 1) , which in turn yields us the equality, as desired. Finally, we see that our answer is just b log 2020 c + 1 = 11 . 2 2 4. Find the number of points P ∈ Z that satisfy the following two conditions: √

1. If Q is a point on the circle of radius 2020 centered at the origin such that the line P Q is tangent to the circle at Q, then P Q has integral length. 2) The x -coordinate of P is 38. Proposed by: Ollie Thakar Answer: 16 2 2 Notice that 38 + 24 = 2020 . Then, let P have coordinates (38 , y ) , and label the length of P Q as T. For now, we will only deal with positive y. We know from power of a point theorem that 2 2 6 2 ( y + 24)( y − 24) = T . Re-arranging this expression gives us ( y + T )( y − T ) = 24 = 2 · 3 . 6 2 Now, we know that y + T and y − T must be integer factors of 2 · 3 . There are (6+1)(2+1) = 21 6 2 factors of 2 · 3 , of which 20 come in pairs and 1 is a perfect square. Thus, there are 11 pairs 6 2 of factors multiplying to 2 · 3 . 2

Of those pairs of factors, 3 pairs have 1 odd factor and 1 even factor, while the remaining pairs 6 2 have 2 even factors. ( y + T )( y − T ) = 2 · 3 means that the only the pairs with 2 even factors will lead to integer values of T and y. Each factor pair leads to a unique solution pair of y and T. Thus, there are 8 possibilities for y, when y > 0 . Then, there are 8 more possibilities for y that are negative, so the total is 16. Note: We also accepted the answer of 14 since it isn’t clear that P is allowed to be taken on the circle and still yield a valid configuration. 5. Suppose two polygons may be glued together at an edge if and only if corresponding edges of the same length are made to coincide. A 3 × 4 rectangle is cut into n pieces by making straight line cuts. What is the minimum value of n so that it’s possible to cut the pieces in such a way that they may be glued together two at a time into a polygon with perimeter at least 2021? Proposed by: Austen Mazenko Answer: 202 For n pieces, edges must be glued together at least n − 1 times, and each gluing event reduces the overall perimeter by twice the length of the edges being glued together. Furthermore, every time a cut is made to divide the bar into more pieces, it increases the total perimeter by at most twice the length of the largest cut, which is 5 (the length of the rectangle’s diagonal). To form n pieces, there are at most n − 1 cuts. Hence, an upper bound for the perimeter is 3 + 4 + 3 + 4 + 2 · 5 · ( n − 1) − 2 · 0 · ( n − 1) = 10 n + 4 since every edge being glued together has a length > 0 and all cuts have length ≤ 5. Accordingly, we need 10 n + 4 ≥ 2021 = ⇒ n ≥ 202 since n must be an integer. To see that n = 202 is sufficient, put the bar on the coordinate i plane so that it has one vertex on the origin and one at (4 , 3). First, make 200 cuts from ( , 0) N i to (4 , 3 − ) for 1 ≤ i ≤ 200 and some large integer N . N Finally, cut the bottom right triangle like so: 1 N 1 N 1 Now, all of the thin strips have two edges of length , so they may be glued together in N sequence like so: 3

√ ( ) ( ) 2 2 201 201 1 By Pythagorean Theorem, each cut has length at least 3 − + 4 − − . Making N N N N arbitrarily large, each cut may have a length sufficiently close to 5 and each small edge may have sufficiently small length so that the perimeter will exceed 2021, as desired. 6. We say that a string of digits from 0 to 9 is valid if the following conditions hold: First, for 2 ≤ k ≤ 4 , no consecutive run of k digits sums to a multiple of 10 . Second, between any two 0s, there are at least 3 other digits. Find the last four digits of the number of valid strings of length 2020 . Proposed by: Frank Lu Answer: 9040 Let a be the number of valid strings of length l whose last digit is 0 , and define b to be those l l whose second to last digit is 0 , c third to last digit is 0 , and d to be all other valid strings. l l Let t = a + b + c + d . l l l l l Then, observe that we can construct the following recurrences: First, a = d , as for any valid string where there is no 0 in the last three digits, we can l l − 1 append a 0 to get a valid string. This holds for l ≥ 2 . Next, b = 7 a . To see this, suppose we have a valid string ending with a 0 of length l l − 1 l − 1 , whose last three digits are x, y, 0 . Then, we can add any digit except for 0 , and the digits equivalent to − y and − x − y (mod 10) , all of which are distinct. By a similar logic, c = 7 b . l l − 1 Note, however, that these equations only hold for l ≥ 4 . Finally, we note that d = 7 c + 6 d , by applying a similar logic. Summing all of these l l − 1 l − 1 up, we see that t = 7 t . We do, however, need to compute t first, as we’ve seen that this l l − 1 3 recurrence only holds for l ≥ 4 . We compute: a = 1 , d = 9 , b = c = 0 . For l = 2 : a = 1 1 1 1 2 9 , b = 9 , c = 0 , d = 72 , and for l = 3 : a = 72 , b = 72 , c = 72 , d = 504 . This yields that 2 2 2 3 3 3 3 l − 3 t = 10 , t = 90 , t = 720 , which gives us that for l ≥ 4 , t = 720 · 7 , which gives us that 1 2 3 l 2017 t = 720 · 7 . 2020 Now, to compute the last four digits: we see that this is equivalent to 0 (mod 16) , so we need 500 to find what it is (mod 625) . Note that 7 ≡ 1 (mod 625) , by Euler totient, which gives us 17 17 that t ≡ 95 · 7 (mod 625) . But as this is divisible by 5 , we can just find what 19 · 7 2020 4 16 4 (mod 125) is. However, we see that 7 = 2401 ≡ 25 + 1 (mod 125) , so hence 7 ≡ (25 + 1) ≡ 17 1+25 · 4 ≡ 101 (mod 125) . But then we have that 19 · 7 ≡ 133 · 101 ≡ 58 (mod 125) , implying that t ≡ 290 (mod 625) . Noting that we have that t is divisible by 16 yields us that 2020 2020 t ’s last four digits are 9040 . 2020 7. Let X , Y , and Z be concentric circles with radii 1, 13, and 22, respectively. Draw points A , B , and C on X , Y , and Z , respectively, such that the area of triangle ABC is as large as 2 possible. If the area of the triangle is ∆, find ∆ . Proposed by: Daniel Carter Answer: 24300 Let the circles be centered at the origin O and without loss of generality A = (1 , 0). Consider fixing A and B and letting C vary. The area of the triangle is maximized when the height from C onto AB is perpendicular to the tangent of Z at C , or in other words when CO is perpendicular to AB . Likewise we have AO is perpendicular to BC , so B and C have the same x -coordinate. Let B = ( x, b ) and C = ( x, c ) with x and b negative and c positive. 2 2 2 2 Then the circle equations give x + b = 169 and x + c = 484, and CO ⊥ AB gives x ( x − 1) + bc = 0. Solve the first two equations for b and c and plug into the third to give √ 2 2 x ( x − 1) + (169 − x )(484 − x ) = 0. Rearranging, squaring, and simplifying gives the cubic 3 2 x − 327 x + 40898 = 0. We know x is negative, so we can look for a root of the form − n 4

2 2 where n is a factor of 40898 = 2 · 11 · 13 . We don’t need to try many to find the solution √ √ √ √ x = − 11. Then b = − 4 3, c = 11 3, and the area of the triangle is 90 3 = 24300. 8. Let there be a tiger, William, at the origin. William leaps 1 unit in a random direction, then leaps 2 units in a random direction, and so forth until he leaps 15 units in a random direction to celebrate PUMaC’s 15th year. There exists a circle centered at the origin such that the probability that William is contained 1 in the circle (assume William is a point) is exactly after the 15 leaps. The area of that circle 2 can be written as Aπ . What is A ? Proposed by: Aditya Gollapudi Answer: 1240 Let D = { θ , θ , ..., θ } represent the random directions that William has selected. Then the 1 2 15 ∑ ∑ 15 15 point that William is at can be represented by ( i cos( θ ) , i sin( θ )). Thus the area i i i =1 i =1 ∑ ∑ 15 15 2 2 of the smallest circle containing is π (( i cos( θ )) + ( i sin( θ )) ) and we need only i i i =1 i =1 ∑ ∑ ∑ 15 15 15 2 2 2 2 solve for ( i cos( θ )) + ( i sin( θ )) Expanding this out we get i cos( θ ) + i i i i =1 i =1 i =1 ∑ ∑ ∑ ∑ ∑ 15 15 15 15 15 2 2 i sin( θ ) + ij cos( θ + θ ) + ij sin( θ + θ ) which can be i i j i j i =1 i =1 j =1 ,j 6 = i i =1 j =1 ,j 6 = i ∑ ∑ 15 15 2 simplified to i + cos( θ + θ ) By the symmetry of the distribution and the i j i =1 j =1 ,j 6 = i 1 1 symmetry of cos, the second term is less than zero of the time and greater than zero half 2 2 1 of the time. Thus the area of the circle in which William is contained of the time is simply 2 ∑ 15 2 15 ∗ 16 ∗ 31 π i which is well known to be π = 1240 π i =1 6 9. Consider a regular 2020-gon circumscribed into a circle of radius 1. Given three vertices of this polygon such that they form an isosceles triangle, let X be the expected area of the isosceles 1 triangle they create. X can be written as where m and n are integers. Compute m tan((2 π ) /n ) m + n. Proposed by: Ollie Thakar Answer: 5049 Draw radii from the center of the circumcircle to each vertex of the isosceles triangle. If the 1 central angles thus created are α, α, 2 π − 2 α then the area is simply sin α − sin(2 α ) . This 2 can be seen with law of sines. Let the original side lengths of the triangle be A, B, C, and angles be a, b, c. Then, because the center divides the triangle into three sub-triangles, the 1 1 1 subtriangles have areas RC cos c, RB cos b , and RA cos a, which I found by dividing them 2 2 2 into two congruent right triangles and using base times height. Law of sines tells us, however, that A = 2 R sin a, B = 2 R sin b, C = 2 R sin c. Plugging these relations into our area formula, 1 remembering also that R = 1 and cos a sin a = sin(2 a ) tells us that the total area of the 2 1 triangle is Area = (sin(2 a ) + sin(2 b ) + sin(2 c )) , which is the formula that I used to get 2 1 sin α − sin(2 α ) . 2 For each vertex, the combined area of all of the isosceles triangles whose distinct angle lies at 1 2 π 4 π 2018 π that vertex is simply the sum of sin α − sin(2 α ) where α ∈ { , , ..., } . 2 2020 2020 2020 The sum of sin α for α in the above range is just the height of the regular 2020-gon with 1 side-length 1, which is h = . tan( π/ 2020) 1009 The sum of sin(2 α ) for α in the above range is the imaginary part of the sum 1 + z + ... + z where z is the 1010th root of unity, so is clearly 0. The total number of isosceles triangles is 1009 ∗ 2020 , and the sum of all of their areas, by our 1 1 above logic, is 2020 ∗ , so the expected area of one of the triangles is . 2 tan( π/ 2020) 1009 tan( π/ 2020) 5

10. Let N be the number of sequences of positive integers greater than 1 where the product of all 64 b of the terms of the sequence is 12 . If N can be expressed as a (2 ) , where a is an odd positive integer, determine b. Proposed by: Frank Lu Answer: 128 Let g ( n ) be the number of ordered tuples of any size so that the entries multiply to n, and all are positive integers that are at least 2 . Let f ( n ) be the sum over all such ordered tuples of the sum of the entries in the tuples. For sake of convenience, we set g (1) = 1 , representing how we have the empty product of a tuple of length 0 , and similarly we have that f (1) = 0 , representing the empty sum. ∑ Then, we see that, summing over possible first entries, yields us that g ( n ) = g ( d ) . We’ll d | n,d 6 = n ∑ write this as 2 g ( n ) = g ( d ) We also know that g ( p ) = 1 for any prime p, as we have that the d | n only ordered tuple is ( p ) . k k − 1 By a similar logic, we can see that g ( p ) = 2 , by using an inductive argument. a b Now, observe that, given n = p q , where p, q are distinct primes and a, b ≥ 1 , that we have ∑ ∑ ∑ ∑ that 2 g ( n ) = g ( n ) + g ( d ) = g ( n ) + g ( d ) + g ( d ) − g ( d ) = 2 g ( n/p ) + 2 g ( n/q ) − d | n d | n/p d | n/q d | n/pq 2 g ( n/pq ) . We thus see that g ( n ) = 2 g ( n/p ) + 2 g ( n/q ) − 2 g ( n/pq ) , unless n = pq, where in this case we have that g ( pq ) = 3 . a b g ( p q ) a Now, let f ( a ) = . Note then that our recurrence relation becomes 2 f ( a + 1) = b a − 1 b +1 2 a a +1 a 2 f ( a ) + 2 f ( a + 1) − 2 f ( a ) , or that f ( a + 1) − f ( a ) = 2 f ( a + 1) − f ( a ) , unless b +1 b b b +1 b +1 b b we have both a, b equaling zero, where then we have that f (1) = 3 . 1 This yields us, for a, b where at least one of a, b is greater than 1 , that f ( a ) − f (0) = b b ∑ a − 1 b b − 1 2 f ( i + 1) − f ( i ) . But f (0) = g ( q ) , which for b > 1 is equal to 2 , so in fact this b − 1 b − 1 b i =0 ∑ a becomes f ( a ) − f (0) = f ( a ) − f (0) + f ( i ). But we can then rewrite this as b b b − 1 b − 1 b − 1 i =1 ∑ a f ( a ) = f ( a ) + 2 f ( i ) , for all positive integers a and for b > 1 , and for b = 1 , a > 1 . b b − 1 b − 1 i =0 We can thus see that, with f ( a ) = 1 for a 6 = 0 that f ( a ) = a + 2 . Note that f will be a 0 1 b degree b polynomial. ( ) ∑ b a + i Now, suppose we can write f ( a ) = c , for some coefficients i. It thus follows that b i i =0 i ( ) ( ) ( ) ( ) ( ) ∑ ∑ ∑ ∑ ∑ b a b b b a + i j + i a + i a + i +1 a f ( a ) = c + c = c + c = c + b +1 i i i i 0 i =0 j =0 i =0 i =0 i =0 i i i i +1 0 ( ) ( ) ∑ b a + b +1 a + i c + ( c + c ) . b i i − 1 i =1 b +1 i But starting with the fact that the coefficients begin as 1 , 1, with a +2 = a +1+1 , it thus follows ( )( ) ( )( ) ∑ ∑ b b b a + i b a + i a b a − 1 that we have that f ( a ) = , giving us in turn that g ( p q ) = 2 ( ) . b i =0 i =0 i i i i 128 64 Applying this to our situation, we want to evaluate f (2 3 ) . We can express this then as ( )( ) ∑ 64 64 128+ i 127 2 ( ) . Note that in this sum inner sum, we have two terms whose largest i =0 i i power of 2 dividing them is 1 , namely i = 0 , i = 64 , and one term whose largest power of 2 ( )( ) ( ) 64 128+32 196 dividing them is 2 , namely . Their sum is + 1 . But note that this is divisible 32 32 64 by 4 , yielding us the answer 128. To see this, consider the product (192 ∗ 191 ∗ 190 ∗ . . . ∗

129. / (64 ∗ 63 ∗ . . . ∗ 1) . Observe then that we can pair elements together in the denominator by i and 64 − i, and pairing i and 320 − i, save for the elements 192 , 64 , 160 , 32 . Only one of these is equivalent to 3 (mod 4) when the largest power of 2 is divided out. This is then equivalent ( ) 196 to 3 (mod 4) , showing that + 1 is at least divisible by 4 . 64

11. Three (not necessarily distinct) points in the plane which have integer coordinates between 1 and 2020, inclusive, are chosen uniformly at random. The probability that the area of the 6

a triangle with these three vertices is an integer is in lowest terms. If the three points are b collinear, the area of the degenerate triangle is 0. Find a + b . Proposed by: Daniel Carter Answer: 13 Let the three points be ( x , y ) for i ∈ { 1 , 2 , 3 } . By the shoelace area formula, the area of the i i triangle is | x y + x y + x y − x y − x y − x y | / 2, so it is an integer if the numerator is 1 2 2 3 3 1 2 1 3 2 1 3 even. Considering the numerator mod 2, shifting any of the x or y by 2 at a time preserves i i the parity of the numerator. Add or subtract an even number from each of x , y , x , and y 2 2 3 3 ′ ′ ′ ′ ′ ′ to make x , y , etc. so that x and x are either x or x + 1 and y and y are either y or 1 1 1 2 2 2 3 2 3 y + 1. If the resulting triangle has integer area, so did the original. 1 Note that there are an equal number of even numbers as odd numbers between 1 and 2020 ′ inclusive. Thus the probability that x = x is 1 / 2, and likewise for the other coordinates 1 2 ′ ′ ′ ′ and possibilities. Out of the sixteen possibilities for x , y , x , and y , six of them form a 2 2 3 3 right triangle with area 1 / 2, and ten of them form a degenerate triangle with area 0. Thus the probability the original triangle had integer area is 10 / 16 = 5 / 8, so the answer is 5 + 8 = 13. 12. Given a sequence a , a , a , . . . , a , let its arithmetic approximant be the arithmetic sequence 0 1 2 n n ∑ 2 b , b , . . . , b that minimizes the quantity ( b − a ) , and denote this quantity the sequence’s 0 1 n i i i =0 anti-arithmeticity . Denote the number of integer sequences whose arithmetic approximant is the sequence 4 , 8 , 12 , 16 and whose anti-arithmeticity is at most 20 . Proposed by: Frank Lu Answer: 15 First, we find a formula for the anti-arithmeticity for a sequence a , a , a , a , as well to find 0 1 2 3 what the arithmetic sequence should be. Suppose we have arithmetic sequence a − 3 d, a − 3 ∑ 2 d, a + d, a + 3 d. Then, we see that the value of ( a + (2 i − 3) d − a ) can be evaluated to i i =0 2 2 equal 4 a + 20 d − 2( a + a + a + a ) a − 0 1 2 3 a + a + a + a 2 2 2 2 2 0 1 2 3 (6 a +2 a − 2 a − 6 a ) d + a + a + a + a . We can re-write this as equal to 4( a − ) + 3 2 1 0 0 1 2 3 4 a + a + a + a 3 a + a − a − 3 a 3 a + a − a − 3 a 2 2 2 2 2 2 2 0 1 2 3 3 2 1 0 3 2 1 0 a + a + a + a − 4( ) − 20( d − ) − 20( ) . We 0 1 2 3 4 20 20 a + a + a + a 2 2 2 2 2 0 1 2 3 see then that the minimal value of this is equal to a + a + a + a − 4( ) − 0 1 2 3 4 3 a + a − a − 3 a 2 3 2 1 0 20( ) . 20 There are two ways to continue. Either through algebraic manipulation or via linear algebra arguments with orthogonal vectors (1 , − 1 , − 1 , 1) and (1 , − 3 , 3 , − 1) , we see that this is equal 2 2 to ( a − a − a + a ) / 4 + ( a − 3 a + 3 a − a ) / 20 . 3 2 1 0 3 2 1 0 Now, note that we are given that a + a + a + a = 40 , 3 a + a − a − 3 a = 40 . But we 0 1 2 3 3 2 1 0 see that that the anti-arithmeticity needs to be an integer. But let a − 3 a + 3 a − a = s, 3 2 1 0 and let a − a − a + a = t. We can then see that a + a = 20 + t/ 2 , a − a = 12 + s/ 10 , 3 2 1 0 0 3 3 0 and similarly we see that a + a = 20 − t/ 2 , a − a = 4 − 3 s/ 10 , which requires us to have 1 2 2 1 s divisible by 10 , and t divisible by 2 , and s/ 10 , t/ 2 to have the same parity. We make the 2 2 substitution s/ 10 = a, t/ 2 = b to get that our anti-arithmeticity value is just a + 5 b , with a, b having the same parity. For the values to be at most 20 , we can just enumerate: (0 , 0) , (0 , ± 2) , ( ± 1 , ± 1) , ( ± 2 , 0) , ( ± 3 , ± 1) , ( ± 4 , 0) . The total number of pairs: 1 + 2 + 4 + 2 + 4 + 2 = 15 . 13. Will and Lucas are playing a game. Will claims that he has a polynomial f with integer coefficients in mind, but Lucas doesn’t believe him. To see if Will is lying, Lucas asks him on minute i for the value of f ( i ) , starting from minute 1. If Will is telling the truth, he will 7

report f ( i ). Otherwise, he will randomly and uniformly pick a positive integer from the range [1 , ( i +1)!]. Now, Lucas is able to tell whether or not the values that Will has given are possible immediately, and will call out Will if this occurs. If Will is lying, say the probability that Will e e a 1 k makes it to round 20 is . If the prime factorization of b is p . . . p , determine the sum 1 k b ∑ k e . i i =1 Proposed by: Frank Lu Answer: 289 Suppose Will has given the values a , a , . . . , a . Given that Will has lasted up to turn n , there 1 2 n is a polynomial so that p so that p ( i ) = a for each i . Furthermore, if q is also a polynomial i where this is possible, then we have that p ( i ) − q ( i ) is divisible by ( i − 1)( i − 2) . . . ( i − n ). But by integer coefficients, we have that p ( i ) = z ( i − 1)( i − 2) . . . ( i − n ) + q ( i ). Thus, it follows that Will has one unique possible value of a modulo n ! that works, which means n +1 1 he has a chance of making it to the next round. Furthermore, the probability that he n ! makes it past minute 2 is 1 (any line will work). Thus, the probability that he makes it to ∏ n − 1 1 round n is equal to p = , given that he is lying. Now, we need to determine the prime i =1 i ! valuations for each of the primes between 1 and 20. For a given prime p , this is equal to ∑ ∑ ∑ ∑ 19 ∞ ∞ 19 i i b c = b c . For p = 11 , 13 , 17 , 19, this expression is just equal to k k i =1 k =1 k =1 i =1 p p 20 − p . For p = 7, this equals 7 ∗ 1 + 6 ∗ 2 = 19, and for p = 5 this is 5 ∗ 1 + 5 ∗ 2 + 5 ∗ 3 = 30. For p = 3, the sum evaluates to (3 ∗ (1 + . . . + 5) + 2 ∗ 6) + (9 ∗ 1 + 2 ∗ 2) = 45 + 25 = 70. Finally, for p = 2, this is 2 ∗ (1 + . . . + 9) + 4 ∗ (1 + . . . + 3 + 4) + 8 ∗ 1 +2 ∗ 4 + 4 ∗ 1 = 90 + 40 + 8 + 8 + 4 = 150. The total sum is thus 1 + 3 + 7 + 9 + 19 + 30 + 70 + 150 = 20 + 49 + 220 = 289. 14. Let N be the number of convex 27-gons up to rotation there are such that each side has length 1 and each angle is a multiple of 2 π/ 81. Find the remainder when N is divided by 23. Proposed by: Michael Gintz and Rahul Saha Answer: 12 Let us consider the roots of unity. Every such polygon can be constructed by taking some subset of the roots of unity which adds to 0, and each such subset uniquely defines a polygon. Two define the same polynomial if they are rotations of each other. We wish to show that the subsets are only those made by unioning equilateral triangles. Consider some subset that works. Letting ω be the smallest primitive root we have some polynomial in ω which has a root at ω . Then since the cyclotomic polynomial is the minimal polynomial of ω , this new polynomial must be a multiple of that. However, the cyclotomic polynomial of powers of 27 54 primes is known to be 1 + x + x , so our set of roots must contain equilateral triangles. Thus we can consider whether we have the first 27 roots. Two polygons will be equivalent iff these binary strings of length 27 are equivalent by rotation. Since this is a 27 gon there are 9 ones so by https://math.stackexchange.com/questions/721783/number-of-unique-sequences- with-circular-shifts our answer is ( ) ∑ 1 a/d + b/d φ ( d ) 27 a/d d | 9 ( ( ) ( ) ( )) 1 27 9 3 1 + 2 + 6 ≡ 12 (mod 23) . 27 9 3 1 Note: Since the desired polygons in this problem are impossible, due to the condition on the angles, we also accepted the answer of 0 . 15 Suppose that f is a function f : R → R so that for all x, y ∈ R (nonnegative reals) we ≥ 0 ≥ 0 3 1 have that f ( x )+ f ( y ) = f ( x + y + xy )+ f ( x ) f ( y ) . Given that f ( ) = and f (1) = 3 , determine 5 2 2021 b log ( − f (10 − 1)) c . 2 8

Proposed by: Frank Lu Answer: 10104 First, we simplify down our functional equation for f. Notice that, using Simon’s Favorite Factoring trick, we may write this as (1 − f ( x ))(1 − f ( y )) = 1 − f ( x + y + xy ) . We can then simplify down our function by writing g ( x ) = 1 − f ( x ) , yielding the function g ( x ) g ( y ) = g ( x + y + xy ) . Now, notice that, letting h ( x ) = g ( x − 1) , this is equivalent to writing h ( x + 1) h ( y + 1) = h ( x + y + xy + 1) . But then, notice that this is equivalent to writing h ( x ) h ( y ) = h ( xy ) for all x, y that are real and at least 1 , the domain of h. From here, notice that the values of h that 8 3 3 1 we have are h ( ) = g ( ) = 1 − f ( ) = , and similarly that h (2) = g (1) = 1 − f (1) = − 2 . 5 5 5 2 8 1 2021 Now, notice then that h (5) = h (8) /h ( ) = − 8 / = − 16 . Therefore, we see that h (10 ) , 5 2 2021 2021 10105 by the multiplicativity, equals h (10) = ( − 32) = 2 . Therefore, it follows that 2021 2021 2021 10105 f (10 − 1) = 1 − g (10 − 1) = 1 − h (10 ) = − 2 + 1 , yielding our answer of 10104 . 9