Just cut the board in half with each question. 64 = 2^6 = 6 questions.
(Is she on the Kingside? Is she on ranks 1 thru 4? etc.)
How would you solve this?
Sort:
Jun 7, 2013
0
#4
Interesting answer LIM. Funnily enough, there was a bit else to the question that I thought was irrelevant, it went:
"Show that you can not ensure the exact position when you are allowed to ask five questions."
lol sorry...I guess I should have left it intact...
Yeah, 2^6 = 64 so there ya go. No question is guaranteed to eliminate over half the squares.
@LIM the 5th question does reduce it to two squares, but only after the "no." Before the 5th question is answered it's still at 4 squares.
I think one question is enough. "On which square is your queen?"
GrahamRead wrote:
I think one question is enough. "On which square is your queen?"
They wouldn't be able to answer truthfully though.
GrahamRead wrote:
I think one question is enough. "On which square is your queen?"
Nope - the stipulation is that they must be answered yes or no.
Let's walk it through and show that 6 questions are required.
(the Q is on a8)
Is she on files e-h? no
Is she on ranks 1-4? no
Is she on files c-d? no
Is she on ranks 5-6? no
Is she on the b-file? no
Squares a7 and a8 remain. I need one more question.
roi_g11 wrote:
BigDoggProblem wrote:
Let's walk it through and show that 6 questions are required.
(the Q is on a8)
Is she on files e-h? no
Is she on ranks 1-4? no
Is she on files c-d? no
Is she on ranks 5-6? no
Is she on the b-file? no
Squares a7 and a8 remain. I need one more question.
But you only knew to exclude the 8th rank and the a-file from your questions because you knew the answer. Those questions would not work if you did not know the location ahead of time.
No, I was showing worst case - the questioner is unlucky and always asks the 'wrong' question.
roi_g11 wrote:
well I can get it down to two possible squares using 5 questions, but can't figure out what the sixth question would be to solve it for any square:
1. On a Light square? (32)
2. On the King side? (16)
3. On the White half? (8)
4. On the two right-most files of that quadrant? (4)
5. On the two top-most ranks of that quadrant? (2)
6. But what question would give you the final square?
You're down to squares S1 and S2, so just ask "Is she on S1?".
I think your light square question is the mistake.
Is it on the kingside? 32
Is it on white's half? 16
On the 2 right files of that quadrant? 8
On the 2 top ranks of that quadrant? 4
Of that group of 4 squares consisting of the 2 files and ranks addressed in the two previous question, is it on the top rank? 2
Of that same group, is it on the right? 1
"In a game on a chessboard one player has to guess where his opponent has placed the Queen. You are allowed to ask six questions which must be answered truthfully by a yes/no reply. Design a strategy by which you can always find the Queen."