HMMT 二月 2023 · 团队赛 · 第 4 题
HMMT February 2023 — Team Round — Problem 4
题目详情
- [35] Philena and Nathan are playing a game. First, Nathan secretly chooses an ordered pair ( x, y ) of positive integers such that x ≤ 20 and y ≤ 23. (Philena knows that Nathan’s pair must satisfy x ≤ 20 and y ≤ 23.) The game then proceeds in rounds; in every round, Philena chooses an ordered pair ( a, b ) of positive integers and tells it to Nathan; Nathan says YES if x ≤ a and y ≤ b , and NO otherwise. Find, with proof, the smallest positive integer N for which Philena has a strategy that guarantees she can be certain of Nathan’s pair after at most N rounds.
解析
- [35] Philena and Nathan are playing a game. First, Nathan secretly chooses an ordered pair ( x, y ) of positive integers such that x ≤ 20 and y ≤ 23. (Philena knows that Nathan’s pair must satisfy x ≤ 20 and y ≤ 23.) The game then proceeds in rounds; in every round, Philena chooses an ordered pair ( a, b ) of positive integers and tells it to Nathan; Nathan says YES if x ≤ a and y ≤ b , and NO otherwise. Find, with proof, the smallest positive integer N for which Philena has a strategy that guarantees she can be certain of Nathan’s pair after at most N rounds. Proposed by: Holden Mui, Milan Haiman Answer: 9 Solution: It suffices to show the upper bound and lower bound. Upper bound. Loosen the restriction on y to y ≤ 24. We’ll reduce our remaining possibilities by binary search; first, query half the grid to end up with a 10 × 24 rectangle, and then half of that to go down to 5 × 24. Similarly, we can use three more queries to reduce to 5 × 3. It remains to show that for a 5 × 3 rectangle, we can finish in 4 queries. First, query the top left 4 × 2 rectangle. If we are left with the top left 4 × 2, we can binary search both coordinates with our remaining three queries. Otherwise, we can use another query to be left with either a 4 × 1 or 1 × 3 rectangle, and binary searching using our final two queries suffices. Lower bound. At any step in the game, there will be a set of ordered pairs consistent with all answers to Philena’s questions up to that point. When Philena asks another question, each of these possibilities is consistent with only one of YES or NO. Alternatively, this means that one of the answers will leave at least half of the possibilities. Therefore, in the worst case, Nathan’s chosen square will always leave at least half of the possibilities. For such a strategy to work in N questions, it must be 460 true that ≤ 1, and thus N ≥ 9. N 2