PUMaC 2020 · 团队赛 · 第 13 题
PUMaC 2020 — Team Round — Problem 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 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
解析
- 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.