Blind Man Walking

Time for a new puzzle I suppose. Though most people who read this blog have already heard this puzzle anyway, so whatever. Anyway, I first learned this puzzle somewhere randomly on the internets:
Consider a square wooden board with four holes drilled in it, arranged in a 2x2 square, with pegs available to fill the holes. A blind man is going to play a game on this board, he wins the game if at the end of one of his turns either every hole has a peg in it or no hole has a peg in it.

A turn consists of the man selecting any two holes, finding out their current status, and he may then change their status to anything he likes. His turn is then over. If he has won, he is now told so, if he has not won, the board will be randomly spun before his next turn.

Find a strategy that guarantees he can win within N turns, for some number N.

The bit about winning in N turns is just to rule out the random strategy, which would work eventually. You need a strategy that is guaranteed to work in a limited number of turns. Also by "randomly spun" I suppose it should be taken for given that the spins will be in multiples of 90 degrees.

6 comments:

edison said...

Kory, either you're bad at explaining the rules, or this puzzle isn't that hard...

(there's also the possibility that my english is too poor to understand this puzzle, but since we both know my english is better than yours, i ruled out this probability)

can't the blind men just choose any fixed 2 holes (for example, 2 holes nearest to me) and simply asked for the pegs to be removed (if there's any in it)?

After a few rounds, he's bound to win it..

kstevens said...

right, after a few rounds he is bound to win. But you need to guarantee that after a fixed number of rounds you will have won. For example, you need to say "I will win in 10 rounds". Now, probably you will win within 10 rounds (or 50, or 1000, you can say whatever) if you do what you say, but probably is not guaranteed.

edison said...

10 rounds seems to suffice... i'm actually quite confident to bet big on winning this game in 10 rounds :)

While i haven't done any calculation, but on a glance, the odds seems to be heavily on my side

edison said...

before you complain, yes, i do understand the word 'GUARANTEE' :)

It's just that i think that if the odds are already heavily stacked on my side, i might feel comfortable 'guaranteeing' it... (even though mathematically it's not 100% sure)..

kstevens said...

right, with 10 turns, you are almost guaranteed to win. Close enough that I would be willing to bet pretty much anything on it. However, the point of the puzzle is not to come up with a solution that almost always works, thats easy. Coming up with a solution that always works is a decent amount harder.

AT said...

If you must, just adjust the problem definition so that there is a malicious person doing the rotating - for whatever strategy you have, the person makes the worst rotation to prevent you from winning (or at least delay you the longest).

-AT