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