Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
You set up the problem with $X$ the number to be guessed, with $X$ contained in a set, $N$, about which set you say nothing. You ask how large $N$ can be, but the rest of the discussion seems to be about how large $X$ can be. I think you ought to edit your question for consistency of notation. I also suspect that if you are trying to guess a number between $1$ and $N$, then you should first ask if it's less-than-or-equal to $2N/3$ (roughly), then $4N/9$. The reason is that if the answer to the first question is no, then you've wasted the second question, but as compensation you know... –  Gerry Myerson Sep 7 '12 at 13:46
    
...that $X$ is in the upper third. Keep guessing upper thirds this way. Maybe. –  Gerry Myerson Sep 7 '12 at 13:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.