I know the answer of this puzzle. I want to know does this puzzle works perfectly for every n × n chess board? Is there a upper bound to n? What is the upper bound for n, if m coins are allowed to flip?
You and your friend are imprisoned. Your jailer offers a challenge. If you complete the challenge you are both free to go. The rules are
The jailer will take you into a private cell. In the cell will be a chessboard and a jar containing 64 coins. The jailer will take the coins, one-by-one, and place a coin on each square on the board. He will place the coins randomly on the board. Some coins will be heads, and some tails (or maybe they will be all heads, or all tails; you have no idea. It's all at the jailers whim. He may elect to look and choose to make a pattern himself, he may toss them placing them the way they land, he might look at them as he places them, he might not …). If you attempt to interfere with the placing of the coins, it is instant death for you. If you attempt to coerce, suggest, or persuade the jailer in any way, instant death. All you can do it watch. Once all the coins have been laid out, the jailer will point to one of the squares on the board and say: “This one!” He is indicating the magic square. This square is the key to your freedom. The jailer will then allow you to turn over one coin on the board. Just one. A single coin, but it can be any coin, you have full choice. If the coin you select is a head, it will flip to a tail. If it is a tail it will flip to a head. This is the only change you are allowed to make to the jailers initial layout. You will then be lead out of the room. If you attempt to leave other messages behind, or clues for your friend … yes, you guessed it, instant death! The jailer will then bring your friend into the room. Your friend will look at the board (no touching allowed), then examine the board of coins and decide which location he thinks is the magic square. He gets one chance only (no feedback). Based on the configuration of the coins he will point to one square and say: “This one!” If he guesses correctly, you are both pardoned, and instantly set free. If he guesses incorrectly, you are both executed. The jailer explains all these rules, to both you and your friend, beforehand and then gives you time to confer with each other to devise a strategy for which coin to flip.
What strategy would you use to escape?