Inspired by 6 Tries to Guess a Number Between 1-100, how many guesses would it take if you can ask if the outcome of an operation is equal, less than, or more than a number.
In other words, Alice picks a number $x$ such that $1\leq x \leq 100$ and her friend Bob asks $f(x) \overset{?}{=} y$ to which Alice may only respond with 'correct', 'bigger', and 'lower'.
An example would be Bob asking $ x \overset{?}{\equiv} 1\pmod 3$ and Alice replying 'higher'. Bob has now eliminated ⅔ of the domain.
How many guesses would it take before he can state the correct number Bob?
Please note that I do not have an answer to this question, but since using modulo powers of 3 is equivalent to the solution I gave to a similar question, I have an upper bound of stating it on your 6th 'guess'.
Answer
Your solution from the other question works (and is ideal) here, too.
Suppose the current range is $[a, b]$ (at the beginning $a=1$, $b=100$). break the range into thirds; let $t_1 = \frac{b-a}{3} + a$, $t_2 = \frac{2(b-a)}{3} + a$.
let $f(x) = -1$ if $x \le{} t_1$, $0$ if $t_1 \le{} x \le{} t_2$, and $1$ if $t_2 \le{} x$. Now compare $f(x)$; you've eliminated two thirds of the range. Just as argued in your answer, that will guarantee that your sixth guess is a single, correct number.
You can't do any better than this, in the worst case. Any answer will separate the candidate numbers into three sets (one for each possible answer to the comparison). Assume for the worst-case analysis that the answer indicates that the largest of these three sets contains the correct answer; you want to minimize the maximum set size, which requires making sure there are one third in each basket.
No comments:
Post a Comment