HMMT 十一月 2018 · 团队赛 · 第 10 题
HMMT November 2018 — Team Round — Problem 10
题目详情
英文原题
- [ 65 ] David and Evan are playing a game. Evan thinks of a positive integer N between 1 and 59,
inclusive, and David tries to guess it. Each time David makes a guess, Evan will tell him whether theguess is greater than, equal to, or less than N . David wants to devise a strategy that will guaranteethat he knows N in five guesses. In David’s strategy, each guess will be determined only by Evan’sresponses to any previous guesses (the first guess will always be the same), and David will only guessa number which satisfies each of Evan’s responses. How many such strategies are there?
Note: David need not guess N within his five guesses; he just needs to know what N is after fiveguesses.
解析
英文解析
- [ 65 ] David and Evan are playing a game. Evan thinks of a positive integer N between 1 and 59,
inclusive, and David tries to guess it. Each time David makes a guess, Evan will tell him whether theguess is greater than, equal to, or less than N . David wants to devise a strategy that will guaranteethat he knows N in five guesses. In David’s strategy, each guess will be determined only by Evan’sresponses to any previous guesses (the first guess will always be the same), and David will only guessa number which satisfies each of Evan’s responses. How many such strategies are there?
Note: David need not guess N within his five guesses; he just needs to know what N is after fiveguesses.
Proposed by: Anders Olsen
Answer: 36440
We can represent each strategy as a binary tree labeled with the integers from 1 to 59, where Davidstarts at the root and moves to the right child if he is too low and to the left child if he is too high.
Our tree must have at most 6 layers as David must guess at most 5 times. Once David has been toldthat he guessed correctly or if the node he is at has no children, he will be sure of Evan’s number.
Consider the unique strategy for David when 59 is replaced with 63. This is a tree where every node inthe first 5 layers has two children, and it can only be labeled in one way such that the strategy satisfiesthe given conditions. In order to get a valid strategy for 59, we only need to delete 4 of the verticesfrom this tree and relabel the vertices as necessary. Conversely, every valid strategy tree for 59 can becompleted to the strategy tree for 63. If we delete a parent we must also delete its children. Thus,
we can just count the number of ways to delete four nodes from the tree for 63 so that if a parent isdeleted then so are its children. We cannot delete a node in the fourth layer, as that means we deleteat least 1 + 2 + 4 = 7 nodes. If we delete a node in the fifth layer, then we delete its two children aswell, so in total we delete three nodes. There are now two cases: if we delete all four nodes from thesixth layer or if we delete one node in the fifth layer along with its children and another node in the
( )
sixth layer. There are ways to pick 4 from the sixth layer and 16 · 30 to pick one from the fifth 32
layer along with its children and another node that is from the sixth layer, for a total of 36440.4