4
$\begingroup$

I've spent hours on this puzzle, which shouldn't be too hard, and I'm sure I've got the right answer, but apparently it's wrong. The problem statement:

You are guessing a positive number X. You may ask the question, "Is X less than Y?" but the answer will be delayed by one question (you won't receive the answer until the next question is asked, note that the last question will not be answered).

If you can ask 30 questions, how large can X be to guarantee that it is determined every time?

So, I've covered several pages (after a few wrong turns) mapping questions, as follows (the "worst case" scenario for each):

X = 3: Y < 2? Y < 3? {last question}? -> guesses: 3

X = 4: <3? <4? <2? {}? -> 4

X = 5: <4? < 2? <3? {}? -> 4

X = 6: <4? <2? <5? <6? {}? -> 5

X = 7: <4? <6? <2? <3? {}? -> 5

X = 8: <5? <3? <7? <8? >6? {}? -> 6

...

X = 12: <7? <10? <4? <5? <2? <3? {}? -> 7

...

X = 16: <9? <13? <5? <7? <3? <4? <2? {}? -> 8

The pattern emerges where the number of guesses change at the midpoint between each power of 2:

X = 2^2 -> 4 guesses

X = 2^2 + (2^2) / 2 -> 5 guesses

X = 2^3 -> 6 guesses

X = 2^3 + (2^3) / 2-> 7 guesses

X = 2^4 -> 8 guesses

Since 31 guesses is the limit, max 30 guesses (the solution) should be one less than that:

X = 2^15 + (2^15) / 2 - 1 = 49151 

...but the puzzle page says "Wrong". I've also tried the other powers of two and midpoints and numbers nearby, but no dice.

Can someone give me a push in the right direction? I'm happy to do the legwork but I'm not sure where my mistake is!

  • 0
    ...that $X$ is in the upper third. Keep guessing upper thirds this way. Maybe.2012-09-07

0 Answers 0