4
$\begingroup$

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'.

$\endgroup$
  • $\begingroup$ I don't think &frac23 is working. You may have to do \$\frac23\$ instead $\endgroup$ – kaine Oct 21 '14 at 20:10
  • $\begingroup$ @kaine Works for me. What is not working for you? Please note that I meant to use an HTML entity, not LaTeX. $\endgroup$ – SQB Oct 21 '14 at 20:18
  • $\begingroup$ Hm... works on phone but not on computer... i see exactly "ampersand" frac23 instead of the fraction. Must be on my end. $\endgroup$ – kaine Oct 21 '14 at 20:20
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

My answer to that question would seem to work.

Express $x$ in trinary. Repeatedly ask if digit $i$ from the right is equal to $1$. This will yield $3^5$ possible answers in $5$ questions. At that point you know $x$, since $3^5 > 100$. Ask that value for your 6th question.

To be more explicit:

$$f(x,i) = floor\left({x \mod 3^i \over 3^{i-1}}\right)$$

and $y_i = 1$. Ask for $i = 1,2,3,4,5$.

$\endgroup$
  • $\begingroup$ This choice of f is more elegant than mine, although the result is the same. $\endgroup$ – TheRubberDuck Oct 21 '14 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.