Puzzles & Math Problems
This page is for puzzles and other assorted things that I liked when they were posed to me. Some you may have seen before but if you haven't seen them - give them a go! You only get one flash attempt!
This one is very simple, using only division, multiplication, addition and subtraction, can you make the number 25 using only 2, 4, 6 and 8. Each number can only be used once but you may reuse operations if you like.
There's no trick here, just combinatorial search space and an annoying sense that it should be easy.
My train of thought for this problem: I first started trying to do something of the for (a * b) + (c * d). Its easy to see here that we are going to be unable to inject any oddness (oddity?) into our solution this way, and so there's no chance of getting 25.
I then tried to produce an odd number. Some candidates were 6 / 2 = 3 or similarly (6 + 4) / 2 = 5 and (6 + 8) / 2 = 7. Taking 3 as an example, we can see that to get within adding/subtracting range we would need to massage the other two numbers into either 22 or 28, which isn't possible with what we have left over. For the other two odds its worse still: we only have one number left over to work with.
The next thing I tried was to assume that my last step would be division e.g. get to, say 50, and then divide by 2. 6 * 8 + 4 = 52 and 52 / 2 get us painfully close, but not close enough. Numbers like 100 and 150 prove un-attainable also.
After this I got pretty stumped. If division didn't work as the final step, and addition/subtraction seemed out due to the oddity issue, how could it be done. Multiplication as the final step is all that is left, but the intermediate products all seem yucky: 12.5, 6.25, 4.166 and 3.125. For this reason I was aesthetically disinclined to look into this path further, however it was this aversion that kept the solution out of reach.
As you may have worked out, its possible to make 6.25 with 6 + (2 / 8), and then we can get to 25 by multiplying the remaining 4. This answer makes a lot of sense when you see it, but at least personally I found it very tricky to puzzle out, I hope you got it!
The set up is this: two prisoners are offered a chance at liberty by their warden, who, as usual, has a fondness for puzzles. Tomorrow, he will invite the first prisoner into a room where there is a chess board with the usual 8 by 8 chequered squares. Under each square there is a compartment where a key can be hidden. On top of each square is a coin, showing either heads or tails. In view of the first prisoner the warden places the key under one of the 64 squares and instructs them to flip exactly one of the coins. After they have flipped the coin, they leave the room and prisoner two comes in. Prisoner two gets a single guess about the location of the coin and wins freedom for themselves and their partner if they get it right, and otherwise are condemned to suffer the cruelty of the modern prison-industrial complex. Additionally, the warden can surveil the prisoners while they plan for the puzzle, and can construct a maximally adversarial scenario for their chosen strategy. What strategy should the prisoners use?
This puzzle seems impossible. There are \(2^{64}\) possible board states and somehow the first prisoner must communicate the location of the key with only a single flip.
One naïve strategy which does a bit better than random guessing is to use the to left corner as a sign bit: if it is heads, guess randomly in the top half, if it is tails, guess randomly in the bottom half. The first prisoner can always get to the correct state by either flipping the coin if it shows the wrong face or flipping another if it is already correct. Unfortunately this solution only gets us to a \(1/32\) chance, not the odds I'd live when my freedom is on the line.
To approach this problem its easier to think of a simpler case to build intuitions. Instead of 8 by 8 lets consider a 2 by 2 puzzle. One idea is to think of the coins as binary numbers, and to have them "turn on" or off integers. If we assign the board positions number 0, 1, 2 and 3, we can take the sum of the "on" digits mod 4 to get a number \(\in \{0,1,2,3\}\) which encodes a position. This approach seems to work! Taking the board position (with location index):
T, H (0, 1)
T, H (2, 3)
for example, we get 0 + 1 + 0 + 3 = 4 mod 4 = 0. If we need to indicate position 0, we can flip 0 to preserve the count, if we need 1 we can turn off 3, 2: we can turn on 2 and 3: we can turn off 1. Voila. Done. Solved.
Unfortunately, this solution doesn't work for all cases. If we have a board with a single head in position 3 for a sum of 3, there is no coin we can flip to indicate position 2. The general issue is that we have multiple ways to indicate one outcome (flip pos. 1 OR 3 to indicate 0), meaning we necessarily will be unable to indicate some other positions.
Thinking about it, as the warden can choose the location of the key, we need to be able to indicate *any* location from a given board. As there are 64 possible locations and 64 possible flips, we will need each flip to correspond to exactly *one* location. If there are any double-ups the warden can exploit this.
I'll skip all of the other failed attempts, and now give the solution I found:
If we imagine imagine the full board, numbered 0 to 63 in base 10 or 000000 through 111111 in base 2, we can imagine again the coins "turning on" each number, except this time instead of adding them to a sum mod n, the coins add them into a digit-wise XOR calculation. For example, the board with all tails has nothing turned on, and so represents \(000000_2\) or \(0_{10}\). If we turn on position \(3_{10}\) and position \(45_{10}\), we get \(000011_2\)XOR \(101101_2\) = \(101110_2= 46_{10}\). Because the 64 different numbers together span every 6 digit binary number, we are able to access any final position from any starting position with one coin flip.
So that's it: a tricky solution to a tricky problem. The exceptional 3blue1brown has a video on this problem, which is well worth a watch! See also Hamming codes - this problem is something like the opposite of error correction, as we want our message to be able to may to *any* other message with a single bit shift.