0
$\begingroup$

I thought up this problem and am trying to come up with an optimal solution.

I am thinking of a number uniformly randomly between 1-100, inclusive.

  • If you guess the number, you "win".
  • Else if you guess incorrectly, but are within 10 of the number, I will tell you "hot".
  • Else, I will tell you "cold".

For example, if the number I'm thinking of is 37, guessing any value in [27,36] or [38,47] will be "hot". Any guess not in those ranges except 37 will be "cold".
You are not allowed to guess a number outside of 1-100.

My current approach:

  1. Guess in increments of 11. I guess 11, if it's hot, the number is in [1, 10] or [12, 21]; if it's cold, I guess 33, 55, and so on.
  2. Suppose the true number is "hot" at 11. Then, I can guess 1. If 1 is hot, the number must be within [2,10], else [12,21]. I could have also guessed 21 here for similar effect.
  3. Suppose the true number is within [12,21]. My goal is to split the search space in half again. So I guess 6: if hot, it must be within [12,16], else [17,21].
  4. Repeatedly split the search space in half this way.

Is there a better algorithm? What would be the runtime?

$\endgroup$
5
  • $\begingroup$ From your description, it seems that if I try the correct number you will tell it. Do you confirm ? (There is a difference between you saying "you win" and me saying "I know the number".) $\endgroup$ Jul 18 at 8:48
  • $\begingroup$ Another missing information is if you are allowed to query values out of the range, like -3 or 105. This makes a big difference. $\endgroup$ Jul 18 at 9:05
  • $\begingroup$ @YvesDaoust In fact, I do not think -3 or 105 makes any difference. $\endgroup$
    – John L.
    Jul 20 at 7:07
  • $\begingroup$ @JohnL.: I think the opposite. $\endgroup$ Jul 20 at 7:09
  • $\begingroup$ I am still waiting for the answers. $\endgroup$ Jul 21 at 7:54

1 Answer 1

1
$\begingroup$

A "cold" answer removes 21 possibilities from consideration. So you'd better try the positions 11, 32, 53 and 74 to avoid any overlaps. And if you get four "cold", you know that the number is in 85-100.

When you have a "warm", dichotomic search will indeed be the most effective. The runtime will be approximately from one to four queries plus [one to*] five queries.

*Depends on the exact rule of the game, see my comment.


Due to the fact that the domain is finite, there are boundary effects. It is not impossible that shifting the initial trials by a few units will impact the expected case slightly. But this analysis would be lengthy.

$\endgroup$
3
  • $\begingroup$ I have updated the question. Can you updated your answer? By the way, I do not think the boundary effects affects the final outcome. If you can show that I am wrong, assuming any number such as a negative number or a number greater than 100 can be guessed, that would be great. $\endgroup$
    – John L.
    Jul 20 at 4:27
  • $\begingroup$ @JohnL.: are you acting on behalf of the OP ? $\endgroup$ Jul 20 at 6:17
  • $\begingroup$ Yes. Mostly on behalf of myself, of course. I am considering myself asking the same question as well. Since you have some great ideas, I do not want to update your answer. $\endgroup$
    – John L.
    Jul 20 at 7:03

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.