These will mostly be kind of mathy, given my background and interests, but hopefully not too much so. Please put all solutions in spoilers so that everyone can play. 64 Coins You are on a gameshow with a friend (a lot of these puzzles will start out like this). You can confer with your friend before the challenge starts but not after. The challenge is as follows. Your friend is taken from the room. You are presented with a chessboard with a coin on each square. Each coin has been placed either heads up or tails up by the host, and your friend doesn't know how they are arranged. The host tells you a number between 1 and 64 inclusive. You pick a coin on the chessboard and the host flips over that coin, and then you leave the room. Your friend is brought back in and has to guess the number in order for the two of you to win. Can you always win? Remember that once you are told the number, the only communication you have with your friend is through the coins on the chessboard, and your friend doesn't know how the coins were originally set. Also all you can do is pick a coin on the chessboard for the host to flip over, and you have to pick one coin. Is there a strategy so that you and your friend can always win?
Spoiler Is changing the angle of the coin a viable strategy? Like, the tails up coins have their numbers pointing upwards, but the one you flip is pointing, say, to the upper right corner of the board?
Edited the question to prevent that kind of thing. There isn't anything "tricky" going on here; this isn't a lateral thinking puzzle, just straight-up "how much information can you encoded into the heads-tails distribution of a lot of coins".
Spoiler i don't know if i'm on the track, but are there 32 heads and 32 tails randomly placed, or is the amount of heads and tails random too?
Number of heads and tails is up to the discretion of the host, so you can't make any assumptions about it.
Spoiler: Hint for 64 coins Consider the reduced game of having only one square with one coin and having to guess a number between 1 and 1 inclusive. Consider having only two squares each with a coin and having to guess a number between 1 and 2 inclusive. Consider having only four squares each with a coin and having to guess a number between 1 and 4 inclusive.
Spoiler Hmm. Okay, so, for the two squares case... The coins could start as any of HH, HT, TH, or TT. And... I don't see any way to determine anything. No matter what the final combination of coins is, it could have come from flipping either of the two coins from one of the other states. So unless I'm missing something, I can't even see a way you could solve the two-coin case.
i went and looked up the answer and i STILL DONT GET IT edit: apparently my sister figured out a four coin solution a while ago but that was as far as she was able to get, and we couldn't figure out anything after that
Spoiler Evidence that I completely misinterpreted the question, parsing 'the host flips over the coin' as 'the host flips the coin' The puzzle is marginally easier with that information, but still not easy enough for me to get it
So fun fact: the person I got this puzzle from had a reputation in the department for giving people puzzles like an itinerant sphinx, to the point where he could say "hi, I've got a puzzle for you" and scare off certain professors. Because nerd-sniping is a fact of life in a math department. Spoiler: Hint for 64 coins Does your friend really need to know the initial state of the coins? How much information does a chessboard covered in coins contain? How much information do you need to convey?
Spoiler You need to communicate six bits of information. The question of how much information the board contains is harder. Naively, 64 bits. But you can only change one. But that's not necessarily a problem. For instance, say you could simply remove the coin from one square. It's obvious how to convey things. (I am assuming the chessboard has a fixed and known "orientation".) You could in principle have a protocol which tells you, for each possible input state, how to modify the output state. But I can't nearly as easily think of a thing that will let you distinguish between output states that could have resulted from different inputs. So I think the rule has to respect input state in some way. Okay, hmm. If there are no heads, flip coin N, leaving a board with Exactly One Head, which is in position N. If there's exactly one, you flip a second one... But this gets tricky. Say you do the Nth one after the first head. There's no way for someone to tell a board with a head in position five, N=62, from a board with a head in position 3, N=2. Looking back at the two coin situation: From either of HH or TT, you can produce HT for 1 and TH for 2. From either of HT or TH, you can produce HH for 1 and TT for 2. But this only works because you only have to communicate a single bit.
I haven't really tested my idea, but after a few minutes of thought: EDIT: Came up with a failure state. Spoiler Conference with friend before hand: Assuming the orientation of the board itself does not change, let the top left coin equal 1 with each rightward coin increment in value by 1 and each row increment by 8, so the top right coin is worth 8, the bottom left is worth 57, and the bottom right is worth 64. Or Code: 01,02,03,04,05,06,07,08 09,10,11,12,13,14,15,16 17,18,19,20,21,22,12,24 25,26,27,28,29,30,31,32 33,34,35,36,37,38,39,40 41,42,43,44,45,46,47,48 49,50,51,52,53,54,55,56 57,58,59,60,61,62,63,64 Add the value of all coins together, with heads being positive numbers and tails being zero. Once you have the value of all coins, divide the result by 64 and regard only the remainder. Read remainder 0 as 64. That's the value of the board. In play: When the host tells you his number, read the value of the board and flip one coin to add or subtract in order to bring the board's value to his number. EDIT: Thought a bit more and now I know this solution doesn't work as there's a failure state: If the number is 1 too high and Coin 1 is tails while coin 63 is heads, you can't flip either of them to get the desired number. As it's reliant on two coins, then with random distribution it fails 1/4 of the time. That said, there's my algorithm wastes a lot of memory space anyways. You could probably allocate that memory to other places.
Actually. I think I just realized what the question is in fact. Spoiler Given a single bit of information and a shared algorithm, can an entropic system reliably be made meaningful? So, with that in mind I must say: THERE IS OF YET INSUFFICIENT DATA TO SOLVE THIS PUZZLE.
Spoiler I can now win a four-square game but it is already getting more complicated so I am not going to scale any more after this. For a four-square game, then if the arrangement is HHHH or TTTT, simply flip over the one in the same position that the host says. So for the number one it would be THHH or HTTT and for the number two HTHH or THTT. For HHTT, HTHT, HTTH, TTHH, THTH or THHT, the same rule applies. All of these can also be turned into "three are the same and the one that is different is in the position of the number the host said." Then we are left with HTTT, HHHT, THHH, TTTH and HTHH, TTHT, THTT and HHTH. These can all be turned into "four in a row" if the host says "four," or a "sandwich" (HTTH or THHT) if the host says "three," or into "doubles" (HHTT or TTHH) if the host says "two" and into "alternating" (HTHT or THTH) if the host said "one." I think... If anyone is willing to check my work, I will appreciate it.
