HMMT 二月 2021 · 冲刺赛 · 第 21 题
HMMT February 2021 — Guts Round — Problem 21
题目详情
- [14] Bob knows that Alice has 2021 secret positive integers x , . . . , x that are pairwise relatively prime. 1 2021 Bob would like to figure out Alice’s integers. He is allowed to choose a set S ⊆ { 1 , 2 , . . . , 2021 } and ask her for the product of x over i ∈ S . Alice must answer each of Bob’s queries truthfully, and Bob may use i Alice’s previous answers to decide his next query. Compute the minimum number of queries Bob needs to guarantee that he can figure out each of Alice’s integers.
解析
- [14] Bob knows that Alice has 2021 secret positive integers x , . . . , x that are pairwise relatively 1 2021 prime. Bob would like to figure out Alice’s integers. He is allowed to choose a set S ⊆ { 1 , 2 , . . . , 2021 } and ask her for the product of x over i ∈ S . Alice must answer each of Bob’s queries truthfully, and i Bob may use Alice’s previous answers to decide his next query. Compute the minimum number of queries Bob needs to guarantee that he can figure out each of Alice’s integers. Proposed by: David Vulakh Answer: 11 Solution: In general, Bob can find the values of all n integers asking only b log n c + 1 queries. 2 For each of Alice’s numbers x , let Q be the set of queries S such that i ∈ S . Notice that all Q must i i i be nonempty and distinct. If there exists an empty Q , Bob has asked no queries that include x and i i has no information about its value. If there exist i, j, i 6 = j such that Q = Q , x and x could be i j i j interchanged without the answer to any query changing, so there does not exist a unique sequence of numbers described by the answers to Bob’s queries (Alice can make her numbers distinct). From the above, b log n c + 1 is a lower bound on the number of queries, because the number of distinct 2 n nonempty subsets of { 1 , . . . , n } is 2 − 1. If Bob asks any set of queries such that all Q are nonempty and disjoint, he can uniquely determine i Alice’s numbers. In particular, since the values x , . . . , x are relatively prime, each prime factor 1 2021 of x occurs in the answer to query S iff j ∈ Q ( i ) (and that prime factor will occur in each answer i j exactly to the power with which it appears in the factorization of x ). Since all Q ( i ) are unique, all x i i can therefore be uniquely recovered by computing the product of the prime powers that occur exactly in the answers to queries Q ( i ). It is possible for Bob to ask b log n c + 1 queries so that each i is contained in a unique nonempty subset 2 i − 1 of them. One possible construction is to include the index i in the j th query iff the 2 -value bit is set in the binary representation of j . So the answer is b log 2021 c + 1 = 11. 2