It seems like this assumed that you know which side of the board is the top. Note: The chessboards I have owned don't have letters or numbers, so I hadn't assumed this one was labeled. It looks like the chessboard in this video is also unlabeled. People keep suggesting that the labels are a solution, so I thought it would be helpful to clarify (note added Sept 2021)
I was thinking about that pretty much the whole way through. They had two different chairs, and prisoner 2 doesn't walk in until after prisoner 1 leaves, so it would be entirely possible prisoner 2 didn't know which orientation prisoner 1 looked at it from. I was wondering when they were gonna address it.
I have a feeling that bc of the symmetry it won't matter. The proof should be simple enough, but needs a good way to describe how the bits change as a rotation happens
"And it takes years to forget (the solution)" Grants memory is wild. I watched this a few months ago and it's like I'm hearing it for the first time again lol
I had to think about it for a few minutes (after watching the video) and I think I get it. So the first prisoner who sees where the coin is hidden follows these steps: 1. Determine the binary number that represents the square where the key is. In his example, it's square 33 so: 100001 2. Determine the binary number currently encoded in the board state by counting whether there is an odd or even number of heads in each region. 3. Determine the binary number that needs to be added/subtracted from the current board state so that it will equal the binary number representing the square the key is in. 4. Flip the coin in the square represented by the binary number that you need to add/subtract, as doing so will leave the board in a state that encodes the location of the key. Then the second prisoner simply needs to determine the number encoded in the current board state, and look in that square for the key. Brilliant! What an elegant and simple solution to this seemingly impossible puzzle.
@@jacksonfranke902 In the same way as the first prisoner determined the number encoded in the current board state: by counting whether there is an odd or even number of heads in each region.
Matt's channel has to have the weirdest watch time analytics. Everyone seems to watch like 4 mins of his videos... pauses it... then restarts it sometime between 5 seconds and 2 weeks later.
I came across this puzzle about 5 years ago when a colleague told me about it. Being a computer programmer I immediately turned to solving it using computing and worked it out after about 4 days. Wrote a little c program for it, and was very chuffed with myself. I told my girlfriend at the time and she wasn't that impressed.
You could record 3B1B on the worst mic possible and he would STILL sound like that Edit: I think people in the replies are missing the joke here. Me, someone who is NOT an audiophile, finds 3B1Bs voice to be photogenic in a sound way.
Imagine spending days solving this puzzle, explaining your strategy to your inmate, practicing finding the right coin to flip, and then when the day comes he miscounts and picks the wrong square
The beauty of this method is that you only need to be able to count from 0 to 7 for the column and again for the row. Not impossible to get wrong, but much less likely than when counting all the way to 63.
My biggest takeaway from this was the throwaway thing at 28:53 - “I was thinking 5 shifted twice plus 1.” Because holy crap, I never thought about binary that way - shifting any number over doubles it! This is going to *revolutionize* my mental math.
@@Anonymous4045 it doesn't work for base 1 tho. Base 1 wouldn't work the same way other bases work, zero can't be represented and all other number you just repeat some symbol that number of times. For example, 3 would be | | |. So if you were to "shift" it, | | | | isn't the same as 3x1, but rather 3+1.
@@GvinahGui By "shifting" a number, In base 10 "100" would be 10**2. Shifted left would be "1000", 10**3. In base 1, it's a bit different because zero doesn't really exist, so I'll just use spaces to represent the absence of a number. So if you had "1", shifted over to the left results in "1 ", the same as before numerically. So therefore, "1" in base one shifted to the left results in "1", which is 1x greater than what it was before . This is because order in base 1 is not significant, no tick represents anything more than another tick does
Even if the warden doesn't know what the prisoners are saying, there's still a chance they'll happen to set up the board in a way that makes the prisoners' solution not work. Though what if the prisoners talk about a strategy they're not going to apply as a red herring? And then when they use encryption, they talk about their real strategy? And then, because the warden was trying to thwart the fake solution, the real solution succeeded?
I'm a computer engineering undergrad student with a electronics technician degree, multiple years of tutoring digital circuits at my university, and I still can't tell binary numbers this fast.
You can do really fast like this: If the number is even half it and write down a 0 if its odd write down a 1, subtract 1 and half it. Repeat until your number ist 0. Finally reverse the digits you wrote down (or write them back to front in the first place)
I've seen the start of this video three years ago, and since then was thinking about it sometimes, when i had to wait somewhere. Yesterday evening when watching out for my baby, i finally found the solution and now watched the rest of the video. Thanks a lot for those three years :) I also think you can calculate it a little easier by solving the row and column indenpently, since it is already layed out nicely into this square. You just merge every row, by counting the heads in that row (even = 1, odd=0), then you only have to do it up the number of 8 (3 bits), and later flip the coin which is in the row AND column you have to change.
This is probably the best math video I have ever seen (and both channels make a lot of great content about math, so this says a lot). Not only they take a very intricate puzzle and show how to solve it using somewhat simple math, but also they talk about their mental processes and what they were thinking about when trying to solve the puzzle. Normally, as a math undergrad, our classes (and by extent the content created by mathematicians) are just definition and theorem, definition and theorem, without any intuition about the processes (both historically and particularly) that took to think a problem, to solve a theorem, etc. It is great to see other fellow mathematicians showing their ideais not in the "already polished" away but in its raw form. I think this does a great job to show what a mathematician really does in their daily lives, instead of just laying out the pretty, compacted, textbook results
I realized this, went to another tab to see if it was my screen. The other tab was "Matt and Grant do the whole coin puzzle for real [UNEDITED]. " and I had a small heart attack before I went to ANOTHER tab and it disappeared.
I actually realized it before watching to the end, to be precise, right after Grant mentioned *finite field* . My idea is that to label each block 0-63 in binary (6bit) and add up all the positions with head with finite field additions (xor), lets call it "sum". The result will be a 6bit binary vector. Since we have full control of all binary vectors, and since finite field addition (xor) satisfies the property that (a xor b) xor a = b, we can find the "difference" between the "sum" and the position of the key (in 6bit binary vector representation), and flip the coin that has binary value of that "difference". This way, the "new sum" will be the position of key!!! And they did exactly that. The only thing that I didn't think through is how to compute it efficiently, since doing xor on this many numbers manually is kind of slow and error prone. Their technique of using strips and blocks just makes it a lot easier and doable in reality. The key inspiration here is *finite field* and that property of xor, which I learned from Ben Eater's video introducing CRC (cyclic redundancy code): ruclips.net/video/izG7qT0EpBw/видео.html an actual error checking code that is still widely used in production. Thanks for the great content, this puzzle was a lot of fun to think about.
Man I didn’t expect there to be a practical solution. What I was able to find was a proof that for any size 2^n board it is possible to assign each unique 2^n square to a set of 2^(2^n - n) cases in such a way so that each unique number is only 1 flip away from any of the other sets for unique numbers. This will require both prisoners to have all 2^64 cases memorized but I now see there is a more practical way of organizing them so as to not just memorize.
@@vivekbhagat8353 Sure, I'll try. 'Shifting' is the idea that when you work in a number base, you can do multiplication or division by just moving the 'decimal point' So in base 10, I can multiply 3.0 by ten just by moving the decimal point to the right, and I get 30. In binary, I can multiply 101 (the binary value for five) by two just by moving the point to the right and I get 1010 (which is the binary way of writing ten). So the situation is that Grant is looking at this binary number: 010101 and fairly rapidly identifying it as the decimal number "21." Grant has quickly recognized part of this binary number as a pattern that he knows by heart -- that binary 101 is the decimal number "5". He adds two zeros to the right and makes the pattern into 10100 -- this is what he means when he says "Shifted Twice." If he adds one to that, he'd get his target binary number 10101. So when Grant 'shifts' his binary representation of five (101) two to the right to get (10100) -- he's multiplying twice by two. 5 x 2 x 2 = 20. And then he adds one to get 21.
@@rcb3921 Great explanation. I was confused by that too. Sounds like part of getting the solution THAT fast also involves having some reference number that you can identify without thinking.
Got it! Took half an hour but I figured it out. Without watching the video, my sollution: You start with 000000 Each tile on the board represents a configuration of digits to flip, so the first one is flip nothing, the next 6 are flip one digit, the next 15 are flip 2 digits and so on. This ends up filling the board, and no matter what 6 digit binary number you end up with, you can always just flip to the right configuration with one coin flip. Man, I enjoyed this one! Not impossible but still difficult. There probably are multiple valid sollutions, so I do wonder if they came up with the same one.
They came up with a different numbering for the squares. The number of valid solutions is ridiculously large (assuming I've not made any mistakes, around 1.6e105), but most of them are challenging to remember.
I know I’m two years late but I’m just happy to see pascal reappearing once again (even though it’s not for reasons exclusive to this puzzle) The pennies go 1-6-15-20-15-6-1 lol
I immediately jumped to Hamming codes when hearing this, but only because of Grant and Ben's videos. Looking forward to more errors correction math. Ya'll are great!
I'm confused about the three coin problem. Suppose the key is under the "c" coin (so you need to show a result of 2), and the current coin configuration is 010. In the 0*a+1*b+2*c operation, 010 results in 1. The configurations that lead to a result of 2 are 001 and 101. It's impossible to flip one coin and turn the 010 into either of those. What am I missing? Edit: I was missing the rest of the video when they say this doesn't work.
@bluedragon2997 I think that there are certain start patterns for the 3 square option which means that you cannot always get the necessary result. For instance, start with 010 = 1. Options of end patterns are 110, 000, 011 for flipping 1st, 2nd, 3rd . These are equivalent to 1, 0, and 3(which is also 0). So, no single coin flip results in 2.
I had already spent a while trying to solve it, but did not manage, so then I decided to just watch the video. However, at 17:16 you convinced me to give it one more go and after thinking about it off and on for two more days I managed to figure it out! It was very rewarding to solve it by myself, so thank you for this final encouragement and thank you for making videos about this fantastic puzzle!
I literally stopped at 17:16 and began reading comments 4 days ago and your comment motivated me to try for my self and I finally found the solution today! Thank you
In the discussion at around 29:12, what you're looking at is literally just the two coordinates of the chessboard. 101 = 5 010 = 2 So the thing to flip is at (5, 2) or ((6, 3) if you're feeling like 1 indexing). And at 29:39 that is indeed the square Grant is pointing at.
From this perspective, it's essentially the 8 case happening twice at the same time. (Well, it's also the 2 case happening six times at the same time...) (EDIT: which is why Grant was viewing it as the corners of a 6-dimensional cube)
That's the same reason why hexcode is so good for 8-bit color codes and octal code is so good to encode file system rights. :-D Every digit has its own meaning.
I love this video. I walked through this puzzle with my son and he got it right away as soon as I got to part of the solution where you start to figure out which coin to flip, then it clicked for him and he got the rest himself. The solution and the puzzle are so elegant, it's beautiful. Thank you!
"You can only hear the solution once, and it takes years to forget about it." Approximately four years for me, apparently. The only thing about this puzzle is that I can clearly remember solving the thing in the past and now I'm utterly stumped. I have a feeling I had probably recently watched one of Grant's videos about detecting bit flips in data transfers...
By XORing each row and column, you can speed up the addition process a bit. Basically, I ended up with sixteen binary bits that you can only effect two of (I actually had them in two eight digit numbers, one horizontal and one vertical). You can then apply the same error checking algorithm to get six binary bits that code for a position on the board (that can be changed to any other position by affecting only two of the digits, one vertical and one horizontal)! Beautiful puzzle. Thanks guys!
I learned about this puzzle in 2013 and it stewed in my brain until *2018* before I solved it! And I still wasn’t satisfied that it was the most elegant solution (I used 3 overlapping quaternary bits and a 4-binary bit solution smashed together) love to finally see this video!
I loved Grant's method of splitting the board into stripes, bands, and blocks. It reminded me of how the towers of hanoi puzzle is related to counting numbers in base 3 and just how efficient the system of numeric bases is in counting numbers.
I managed to figure out a solution, but instead of visualizing the 64 squares as a board or a line, I visualized them as a 6-dimensional hypercube (2x2x2x2x2x2). Comparing the coins in an edge of the hypercube already gives you a bit of information. There is also always a way to flip a coin in order to show where the coin is. For each square, its identifier is x+8*y in base 2, where x and y are the coordinates on the chessboard (I know one side is A to H, and the other one 1 to 8, but here, all sides are 0 to 7 instead). For example, 000000 (A1) is the null bit, as it doesn't affect anything, and 111111 (H8) affects every single bit. To get your board identifier, start at 000000, go through every square, and if it's heads, XOR the value with the current identifier. Then XOR the board ID with the target ID, and there you go! The decoding is just: calculate board ID, then that's it!
Here's my magic trick variation of the puzzle: My accomplice is blindfolded, then someone in the audience set's up a 4x4 square with coins randomly heads-up or heads down. Then I tell them that we'll both flip over a coin and then my accomplice will tell them which coin THEY flipped. I even offer them to go first, I just flip the board to "zero". No matter which coin they flip over, it will always encode itself. There are some tricks to do the calculation in your head within seconds (Even drunk people you've just taught the trick to.).
@@richardmclean9479 I doubt I can explain it better than the video, but I'll give it a go. On a 4x4 grid, you have 16 coins. To describe one of the 16 positions you need to convey 4 bits of information by only flipping one coin. For example whether there is an even or an odd number of heads in total would be one bit of information, however you cannot control this because you have to flip a coin. Instead look at only the lower half of the board, there is also one bit of information you can get from there (is there an odd or is there an even number of heads?), but this time you can choose to change it by flipping a coin in the lower half, or not changing it by flipping a coin in the other half. Rinse and repeat for the other sets that are mentioned in the video (lower half, right half, every second row, every second column) and you can encode any four bits into the grid by only flipping one coin. Here's the neat calculation trick for 4x4: Look at rows two three and four and figure out if there's an odd or an even number of heads in each of them. If they are all the same (even-even-even or odd-odd-odd) the encoded coin is in the first row. If one is different from the other two, then the encoded coin is in that row (odd-even-even would be the second row, even-odd-even the third and odd-odd-even the fourth for example). Then repeat the same for the column and you know exactly which coin is encoded. When I see the random 4x4 grid, I just find the encoded coin and flip it. Give it a try and you'll see that now the second third and fourth rows and columns all have the same parity (i.e. odd-odd-odd or even-even-even). When the audience then flips a coin, the row that coin is in and the column it is in will be different from the other two and therefore encode it self (unless it is in the first row, in which case nothing changes and by default it points to the first row, so no problem there). My accomplice then comes into the room and just needs to find the encoded coin by the same algorithm.
@@Kaepsele337 one tiny nitpick from me: i first read "I even offer them to go first" as: offer them the option that they go first, which i considered weak since then you'd obviously be able to work out how to counter what they flipped. But now trying to phrase out my objection i think you might've meant it as "I even offer them that i would go first" (quite impressive, for most* cases!) -- so the offer as stated might be a bit ambiguous. * Only for the "most" cases since it the board was all zeroes your "flip the state to zero" approach wouldn't work, and if you LEFT it as all zeroes it wouldn't be nearly as impressive. :-) Maybe add in a requirement that there's at least 3 (or 5) heads and tails on the board?
@@irrelevant_noob If the board is all zeroes, you flip the zero to make it add to zero still. Certainly not super impressive to the audience when there are two heads and 62 tails staring at you, compared to random chaos, but still works.
I found 5 solutions: 1. Just rub a coin against the wall, creating a flat edge. Tell your friend that the coin with the flat edge is the coin with the key underneath. 2. Yell the square with the coin. For example, "G5!!!". Your friend now knows where the key is. 3. Take all the coins and stack it on one square, the square the key is on. 4. Find the key yourself by throwing all of the coins off the board. 5. Kill the malicious warden, perhaps using the coins and/or board.
This ended up being one of the most enjoyable problem-solving experiences for me! I paused the video, and launched into 8 days of thinking, discussing with friends, writing Python code, and finally ended up with a solution. My solution involved assigning all possible combinations of 1, 2, ..., 6 colors to the squares. Conceptually the same, but the regions ended up being very messy and hard to count. Encoding the squares with binary numbers is much more elegant. Thanks for sharing this fantastic puzzle!
I just found myself skipping over the part where you act it out, to get to the part where you actually explain how it works, just to pause right there to give it a try myself. I am incredibly thankful you explicitly mentioned how you can only learn the solution once :D
Here is the solution I came up with when you said "Most people don't pause the video": First, let's assume that the board is always gonna be 2^m. (In other cases, we can simply consider fictional tiles always filled with 1s (heads) or 0s(tails)). Second, let's start with the simple case, a board of 2x2 tiles. We want to pass two "bits" of information. So we need to somehow find two independent comparisons that we can make and change them independently. For example, We compare bottomleft and bottomright, and then compare topleft and bottomright. Given a random board, we want to transmit "the key is in left | right half" and "the key is in top | bottom half". Let's say, if topleft and bottomright are of different parity, then the key is in the top half. And if bottomleft and bottomright are of different parity, then the key is in the left half. You can see clearly that you always have an option to flip only one tile and transmit those two bits of information (i.e. bottomright if you want to change both parities, topright if you want to change nothing, and the two others quarters for each axis separately.) Now, to transition from the case of 2x2 to 2^n by 2^n, you simply need to observe that each you are always bound to one "quarter" of the whole board. For example, assume the board is 4x4. Once you run your initial reasoning over which quarter to change, then you are bound to choose the tile to flip in that quarter. So the solution then is to compare the sum of tiles in each corner from each quarter. 0|1|2|3 4|5|6|7 8|9|a|b c|d|e|f First comparison: "0123" vs "abef" and "89cd" vs "abef" Second comparison: "028a" vs "57df" and "46ce" vs "57df" The first comparison will tell you which quarter the key is in (and hence which tile you need to flip) The second comparison narrows it down inside each quarter's quarter. And you can easily apply this to any 2^n by 2^n board. For any arbitrary number, I feel lazy to think about it, so just ask the warden for a bigger board :P Say something like "it would be more difficult to solve"
So if I got it correctly: The prisoners decide on this scheme to encode the chess board in 6 bits - the number of bits enough to represent the numbers from 0 to 63. Prisoner 1 encodes the initial board using this scheme, and then chooses the coin to be flipped. The coin chosen is special. When it is flipped, it changes the encoding of the board. The 6-bit encoding of this new board is now the binary equivalent of the _cell on the board which stores the key!_ So now, prisoner 2 can just figure out the 6-bit encoding of the board and bada boom bada bing, the key is revealed.
You are wrong. Not Prisoner 1 decides about the encoding. Otherwise the solution would be too simple without any math. (simplest - make 0 everything and flip to 1 those above the key, a just do any ordered pattern and flipping of a coin above the key will fall out of a pattern). So the board is "encoded" by guards. What Pr1 can do is to change the state of it to any possible 0..63 number by only one coin.
@@ultimatedude5686 This mysterious 'encoding' is explained in the video... I just tried to give a gist of the method presented. In short, to encode the chess board means to represent something about the chess board in a different form. Every square on the board labelled from 0 to 63 can be written in binary using no more than 6 bits. So we define 6 sets. Set i contains those numbers whose ith bit in binary is 1. For example, 35 is written as 100011, so it is a part of sets 1,5,6. Now, for each set, if the number of heads in that set of squares is even, we write a 0, and if it's odd, we write a 1. Hence for each set, we get a 0 or a 1. So we get a sequence of 6 bits, which is the 'encoding' of the chessboard.
Matt, Grant, Michael Penn, and redpenbluepen top notch production. With each offering unique presentations and approaches, one can really absorb the concepts and appreciate the quality. You two provide the long story, ones who go the mile to really set up and prepare the student. The latter two are a quicker pace and is more geared towards proofs and practice. Thanks you and best wishes. 🍻
Before I viewed their solution, I came up with my own which is very similar, but I think mine is a little easier to compute by hand. 1) Number the rows and columns from 0 to 7. 2) Number the squares sᵢⱼ where 0 ≤ i ≤ 7 and 0 ≤ j ≤ 7. 3) Compute the "column bits" by XORing the bits in each column: cᵢ = sᵢ₀ ⊕ sᵢ₁ ⊕ ... ⊕ sᵢ₇ 4) Compute the "row bits" by XORing the bits in each row: rⱼ = s₀ⱼ ⊕ s₁ⱼ ⊕ ... ⊕ s₇ⱼ 5) Compute the column value by multiplying the row numbers by the corresponding column bits and then bitwise XORing the results: C = 0c₀ ⊕ 1c₁ ⊕ 2c₂ ⊕ ... ⊕ 7c₇ 6) Compute the row value by multiplying the row numbers by the corresponding row bits and then bitwise XORing the results: R = 0r₀ ⊕ 1r₁ ⊕ 2r₂ ⊕ ... ⊕ 7r₇ Let the co-ordinates of the square where the key is hidden be (Cₕ, Rₕ) (h for hidden). We compute the co-ordinates of the square to flip (i,j) by XORing the current values with the hidden values: (i,j) = (C ⊕ Cₕ, Rₜ ⊕ Rₕ). Why does any of this work? If we flip the bit sᵢⱼ, it will cause column bit cᵢ and row bit rⱼ to flip, while all the other column and row bits are unaffected. If we compute the new column value C', first note that the new value of cᵢ' is (1⊕cᵢ) and if we substitute that into the expression for the column value we see that C' = 0c₀ ⊕ 1c₁ ⊕ ... ⊕ (i-1)cᵢ₋₁ ⊕ i(1⊕cᵢ) ⊕ (i+1)cᵢ+₁ ⊕ ... ⊕ 7c₇. But i(1⊕cᵢ) = i ⊕ icᵢ. And XOR is commutative and associative just like regular addition so we can move that i to the end of the expression and we get C' = 0c₀ ⊕ 1c₁ ⊕ 2c₂ ⊕ ... ⊕ 7c₇ ⊕ i = C ⊕ i = C ⊕ (C ⊕ Cₕ) (by definition of i) = (C ⊕ C) ⊕ Cₕ (because XOR is associative) = 0 ⊕ Cₕ (because XOR is its own inverse) = Cₕ The exact same thing works for the rows, so we've solved the puzzle! The second prisoner computes the row and column values and they point to the key. I made a spreadsheet you can play around with in Google sheets if you're interested docs.google.com/spreadsheets/d/1cVzJ-7KortGh7TmGKOnoc6XyOJix3Gu4rzVwfLnmf1U/edit?usp=sharing
Now that I understand the solution, weirdly, I have an easier time explaining it without the visual support. So, for other people out there that see things like me, maybe this will be easier. Each square with heads on it translates to the square index, from 0 to 63, written in binary. You want prisoner 2 to be able to sum, with the XOR operator (addition without carry), all squares with heads, and having the sum represent the square where the key is. Now, XOR has the nice property that flipping from 0 to 1 or from 1 to 0 are both represented by XORing the square index, i.e. X xor X = 0. So, flipping a coin is the same as XORing its index to the sum. As prisoner 1, you are given a board with a starting sum, let's call it WARDEN, and let's call the key position KEY. You must change the starting sum by one flip so that the new sum is KEY, resulting in the equation WARDEN xor FLIP = KEY. Rearranging the equation, you get FLIP = WARDEN xor KEY. So, as prisoner 1, you list all squares with heads AND the square with the key, XOR them together, and this gives you the square to flip. Also, even if it doesn't prove anything, you can see that, if there were fewer than 64 squares (i.e. if the number of squares is not a power of two), the value FLIP you computed could end up giving you a non-existent index, so the algorithm wouldn't work. Hope this may help!
After months of not completing watching this video i came up with a solution... and i think its easier to understand than the solution in this video - but harder to calculate: The set of all subsets of a set with N elements is 2^N. We need 6 bits to encode the position of the key. So the board fields 1 to 6 are designated for that purpose - we name them "encoding fields". All other fields are assigned one subset of those 6 bits (which is 2^6 = 64) except the subsets with one element... which happens to be exactly 58, including the empty set (no change if flipped) as well as the set that includes all 6 encoding fields. We name those "subset fields". Now each of the 58 subset fields - if it has heads coin - is interpreted to invert the bits of its subset out of the first 6 encoding fields. Now the coins with heads on the 58 subsequent fields convert the binary value of the first 6 coins into some other value from 0-63. If only 1 bit of that value is incorrect, you just flip that bit. If 2 or more bits are incorrect, there is a subset field that flips exactly those ... and that is the coin that needs to be flipped. All the 2 prisoners need to agree on before the game, is which fields are assigned the 6 encoding bits and the which field is assigned each subset.
Just to point out something interesting about the way the problem is posed: In chess computing, a method of hashing known as Zobrist hashing is used to make hashing of successive chessboard positions cheaper. A Zobrist hash has the property that it can be computed cheaply from the Zobrist hash of a related chessboard position in time proportional to the number of altered squares on the chessboard. Since successive positions in chess differ in at most two squares, this is a huge computational savings over recomputing a hash that requires you to consider all 64 squares at once. The chessboard puzzle posed here is closely related to the way Zobrist hashing is actually implemented. I would go so far as to say that the puzzle was designed by someone familiar with the technique, and provocatively posed on a chessboard as a nod to it.
“Take some time and solve this puzzle on your own” the most advanced math I took in college was statistics and all I knew was excel spread sheets I CANNOT fathom what I was suppose to come up with
Well this isn't really a higher-maths problem, it's just a game puzzle... Pen and paper should do fine. But they could've suggested we go over smaller-size boards first, like 1x2, 2x2, or even 4x4... Guess that's such a trivial step in approaching these puzzles that they would just assume we'd do that even without a hint for it. ^^
All the vector stuff they were discussing made it seem much more math heavy than it needed to be. I definitely wouldn’t have come up with this solution either though, hahaha
The first method works perfectly. You don't need the 6 regions at all. Instead of the "classic" addition, you should use the "XOR" addition where adding and substracting are the same. Write binary numbers and decide that for every digit 1+1=0. That's it.
I had heard this puzzle about 4 years ago but never solved it. Thanks for giving me the opportunity to pause the video and solve it, cause I actually did! It took me about 2 days, was pretty tough, and I reasoned about it in a similar way. Once I realized "the trick," the pieces came together and I figured it out, so I watched the rest of the video to see that I was right! Great video, thanks a lot for this.
theoretically if you could both memorize 64^2 different strings of 64 bit values and assign 64 specific values to each square, it would be possible no matter the boardstate to change one coin to match one of the 64 possible assigned values that match the box that the key is in. not humanly possible, but 100% guarenteed
17:10 "You can't feel that bad because anyone watching is looking it up." Not me! I solved it last night after watching the 3Blue1Brown video (the one that explains why it's only possible when the number of squares is a power of two) and am watching this just to compare my approach to yours. :)
After seeing 3b1b's video on this. I solved thus puzzle on a road trip. Hours of fun! I eventually came up with the same solution but with the meanings of the coins rearanged (the conis meant the same things, but were in different places on the board). My thaught process was wildly different and my explanation on how it worked was MUCH messier, but it was essentially the same. I love how two seemingly different solutions with almost completely different processes came out to be the same thing, this is why I love math. (By the way 3b1b's video helped a ton in steering me in the right direction) This puzzle made an otherwize boring car ride fun, thanks Matt and Grant and keep up the amazing work.
When I paused I found a solution that I assumed would be the solution they gave but it was actually different. Mine might be slightly harder to calculate in practice but is simpler to describe. Step 1: We label all the tiles 0-63, then we add them up mod 64 and that is the tile we get, but there’s a catch. When we add x + -x, we get 2x instead of 0. With that one change we can add any number 0-63 with the change of one coin. Firstly, if the numbers already code for the right space, flip the 0 coin. If the numbers are 32 away, flip the 32 coin. For all other possible values, n, there are 4 possible scenarios. If n and -n are both 0, flip n. If n is 1 and -n is 0, flip -n. If n is 0 and -n is 1, flip -n. If n and -n are both 1, flip -n.
Took me ~30 minutes of thinking and ~1 hour of coding to solve. My first guess was to take parities of every coin, every 2d coin, every 3d, every n-th coin but it didn't work when i coded it. I tried every 2^n-th coin, every prime number but it also didn't work. Then I decided to change my approach and tried to add up all the numbers (also found out that it won't work in 25% of cases) and following the same logic as in the video remembered that XOR function is symmetrical and got the final solution. No need to think in terms of 6-dimensional cubes :) P.S. BTW, it won't work in case of a non-power-of-two number of squares. Some modifications to this strategy will be required.
Great video! I watched the first part a few weeks ago and have come back to see if my solution matches yours. I came up with something different than the solution you discuss with Matt. Interestingly, my solution provides a different way of glimpsing into which configurations may or may not be possible. Here's what I did: Take the parity of each row, and the parity of each column. Each is an eight-bit sequence. Note that by choosing a coin on the main grid to flip, we can selectively switch any one bit of the "row parity" sequence and any one bit of the "column parity" sequence. We now have a new challenge (or rather, two identical challenges): With our eight bits of "row parity", flip exactly one of them to communicate the row containing the key. And independently do the same for the columns. Hm... This feels like a familiar puzzle. In fact it's the same one as the original with only eight coins! Done twice! I'm still stuck. Eight is a lot. But... If we arrange THOSE eight in a 2x4 board, and take the parity of the rows and columns of THAT, we can reduce this eight-coin puzzle to a four-coin version and a two-coin version in the very same way we reduced the original! And that four-coin version can be reduced further by laying it out in a 2x2 grid to get two 2-coin versions. At that point, solve by hand. For me I arbitrarily decided that 00 and 10 point to the first coin, and 01 or 11 point to the second. Bubble up these smaller puzzles to eventually find which coin of the row-sequence needs to flip, and which of the column-sequence to flip, and then flip the corresponding coin in the big chess board. I imagine that my solution implicitly is just selecting a different way to partition the board into the six regions overlapping regions you discuss with Matt. What's fun is trying my solution on different board sizes. A 6x6 looks easy! Take each row and column, let's lay THOSE out in a 2x3 and... hm. I also struggled to color my 3-color cube before deciding it was a no-go. In terms of generalizing my solution, we can say that an N-tile board is solvable if each of N's prime factors is "solvable" (since we factor it down with each cris-cross reduction). After watching this, I'd wager that 2 is the only such solvable prime - which means the powers of 2 are the only viable boards! Thanks so much for this treasured riddle. As you mention to Matt, a good puzzle is a real gem and this one definitely gave me a ride. Let me know what you think of my solution.
@@ИльяХерунцев Not really. Up to that point and including basically all the sister video to this one on 3B1B's channel is basically just Grant rambling about how he proved that an alteration of the puzzle made it impossible, which is unnecessary and confusing when the solution doesn't require any sort of thinking about vectors in higher dimensional cubes. He disrespected us by taking up so much time being proud of breaking the puzzle instead of explaining its solution or the smartest way to go about solving the puzzle.
@@QuesoCookies that's not a video nor a channel about solutions to particular problems, that's a video of two people having fun and sharing it with others FOR FREE, they don't have to do anything for you but do it for free and you have the audacity to be pissed about not them just showing freaking solution right away
@@ИльяХерунцев people can view the video in whatever way they want! if they only care for the explanation then what’s the problem with that? also you’re acting like this video being free is some sort of charity work or done out of good will. it’s not. it’s not free because they are nice it’s free because it makes the most money this way. they get paid for this yknow? youtube as a platform makes big money BECAUSE the videos are free to watch. if making the video cost money made more money then it would cost money to watch. also they aren’t doing anything for me or you we don’t know them. it’s just a silly little youtube video. let people watch how they please and enjoy or not enjoy as they please
Thank you for pushing me to look for a solution before giving the answer. The "you can't forget a solution once it's been given and there are few good riddles" pushed me to pause and think. While I initially had nothing comme tu mind and was therefore not going to try, a few minutes in and the solution was forming. And I'm pretty happy I could work it out
I need to flex here.. I solved it in about 30 minutes what I did differently is that I separated row and column positions from each other and encoded that in the row and column bands respectively and also, you could add up the number of heads in each row/column and then calculate with those partial sums to make the calculations easier
I came up with probably exactly the same solution as ypu! Separating Rows and Colums helps a lot! Partial sums I find pnly useful if you are able to write them down. I tweaked the encoding a bit, so that the decoding can be done easily in your head. It starts like: "If the number of heads (or tails, what ever is easier to count) on the left side of the Board is odd, then the key is on the left side, do the same on the left sides of each halfs, etc." As a bonus, with this encoding the coin to flip is the one which hides the key, if the coins have certain symmetries. Therefore it is easy to spot (as it breaks the symmetrie) and the encoding is invariant to the orientation of the board in these situations
10:15 You might explain it later in the video, but how do you know which is the null bit and which is the active bit? Couldn't the warden rotate the board so you don't know which way is up? Apparently, you need to agree on an extra piece of information, e.g., which side of the table the chair is on so you can tell the orientation of the board your partner was assuming.
I'm 3 years late to this, but its good to know that my 5 minutes of thought on this were roughly the same as Matt's initial idea. I'm not going to spend 3 days thinking about it, but it's nice to know I'm thinking somewhat the same as him.
We have been SCAMMED. 6:56, the cameraman was hiding the key, and the camera switched to a different perspective. Since the camera man was clearly not running the cameras, Matt must have been , thus he knew where the key was all along. Love these math videos, you guys are awesome. Thumbs up from New Orleans.
A variation which IMHO makes the trick more impressive, but easier, is to have the warden arrange the coins in whatever he sees, fit, then have prisoner #1 flip a single coin and leave the room, and *then* have the warden place the key and flip (only) the coin where the key is placed. So neither prisoner gets to see where the key is, but prisoner #2 finds it anyway. The strategy prisoner #1 uses to select a coin to flip is the same as the one prisoner #2 uses to identify the coin that was flipped.
"If I can't do it, I must prove nobody can!" Does the solution require that you need to agree upon the axis and their direction of them? A malicious warden might just put the chair on the other side of the board?
Two of my favorite youtube math-heads collaborating on a math puzzle? That's like... *counts on fingers and uses a couple of toes as well*... AT LEAST TWICE THE AWESOME!
I watched the introduction and stopped it when it they said I should if I wanted to solve it. It took me about 8 or 9 days of stewing on it before I managed to solve it, and then I finished watching the video. While my encoding scheme divided the board differently, it was the same solution. Anyone watching this who hasn't seen the solution yet, ABSOLUTELY pause it and try it yourself, it's absolutely doable, given a basic grounding in information theory.
@@stensoft Even if the board isn't labeled, you could tell that it has been turned 90 degrees because a dark square would be on the right. I think it would work half the time when counting from the wrong side (180 degrees), because a flip will make the rank (the row number) of a coin equal to 7 - rank, or rank XOR 7. So if there are an odd number of 1-coins, then it will work because it is an odd number of XOR 7s, which is equal to one XOR 7, which moves the coin to the right side of the board. If there are an odd number of 1-coins, then the square identified won't change and you'll just count from the wrong side and get the wrong square. But, a malicious warden will make that chance 0% and force an even number of 1-coins. So if the board is turned, you would have to guess the right side.
This was a blast, thanks for making it happen!
We want you on Joe Rogan podcast
I’m just glad we managed to escape.
Your hair cut reminds me of a milder version of David Lynch's Eraserhead. Lol. And i mean that as a compliment.
Random Dude do we though?
@@vincentraitt5697 yes. Imagine what 3blue1brown would be talking about after he hits Rogan's super-weed. Lel
It seems like this assumed that you know which side of the board is the top.
Note: The chessboards I have owned don't have letters or numbers, so I hadn't assumed this one was labeled. It looks like the chessboard in this video is also unlabeled.
People keep suggesting that the labels are a solution, so I thought it would be helpful to clarify (note added Sept 2021)
That is a good point. We did.
That's a brilliant point
I was thinking about that pretty much the whole way through. They had two different chairs, and prisoner 2 doesn't walk in until after prisoner 1 leaves, so it would be entirely possible prisoner 2 didn't know which orientation prisoner 1 looked at it from. I was wondering when they were gonna address it.
lol imagine if the warden just flipped the board after the other guy left....everything down the drain
I have a feeling that bc of the symmetry it won't matter. The proof should be simple enough, but needs a good way to describe how the bits change as a rotation happens
3B1B looks almost exactly how I didn't imagine him
First time I saw him, I thought it was some sort of joke.
I can’t believe he isn’t a brown pi symbol. How could he lie to us like this?
Anyone else think he kind of looks like a young Norm Macdonald
he's kinda-
Somehow he sounds very different though (yes, I know, and i know it's late, but still)
It is 1 in the morning and I have finally figured out a solution. Now I can finally watch the second half of this video after almost 3 years.
Solved it today after a year - now I am free
lol
"Mathematicians don't like […] losing, so they simply prove they can't win"
532 likes, no comments disagreeing
Lier
@@angelr.5123 "Liar"?
@@Suppenfischeintopf Ja, You are a slanderer
@@angelr.5123 Fun fact: There's this very obscure thing calked a "joke", and you just missed one.
"And it takes years to forget (the solution)"
Grants memory is wild. I watched this a few months ago and it's like I'm hearing it for the first time again lol
It's been a few months. You could have another go at it now.
Probably just preference/focus. I don't forget math I see but won't remember what you wore today.
If it makes you feel better, this is my 3rd time watching the Full Video ! ahahahah
The solution just does not stick in to my memory ahahah
Solving it yourself lasts you years is what he means. Watching it doesnt help much😊
What makes his memory wild?
I had to think about it for a few minutes (after watching the video) and I think I get it.
So the first prisoner who sees where the coin is hidden follows these steps:
1. Determine the binary number that represents the square where the key is. In his example, it's square 33 so: 100001
2. Determine the binary number currently encoded in the board state by counting whether there is an odd or even number of heads in each region.
3. Determine the binary number that needs to be added/subtracted from the current board state so that it will equal the binary number representing the square the key is in.
4. Flip the coin in the square represented by the binary number that you need to add/subtract, as doing so will leave the board in a state that encodes the location of the key.
Then the second prisoner simply needs to determine the number encoded in the current board state, and look in that square for the key. Brilliant!
What an elegant and simple solution to this seemingly impossible puzzle.
See if they had explained it like you just have, I think a lot more people (me) would have been able to understand. Thank you for this.
Oh so that's what they're saying! Now I finally know what's going on lol
ohhhhhhhhhhhhhhhhhh
But how does the second prisoner actually decode it to figure out the solution?
@@jacksonfranke902 In the same way as the first prisoner determined the number encoded in the current board state: by counting whether there is an odd or even number of heads in each region.
Matt's channel has to have the weirdest watch time analytics.
Everyone seems to watch like 4 mins of his videos... pauses it... then restarts it sometime between 5 seconds and 2 weeks later.
Can anyone view anyone's channel analytics now?
@@GodsOfMW2 Nope
I was wondering the same thing. I wonder if the RUclips people keep track of that.
lmfao I watch some of his videos that way!
I literally just did this
Seeing 3Blue1Brown in person was slightly mind blowing. I always assumed him to be a disembodied voice.
I came across this puzzle about 5 years ago when a colleague told me about it. Being a computer programmer I immediately turned to solving it using computing and worked it out after about 4 days. Wrote a little c program for it, and was very chuffed with myself. I told my girlfriend at the time and she wasn't that impressed.
You’ll find your Amy Farah Fowler someday… 🥰📝
Warden: **rotates chessboard** **evil laugh**
Chessboards are marked a-h om the x axis 1-8 on the y axis... this puzzle is always directional.
@@CyrusLogie if the board we're rotated, the wrong color would be in each corner
BlokenArrow Not if it were rotated 180 degrees
@@Alextrovert that would be rotating it twice. 🖕👉👇
BlokenArrow Where did you learn that rotations had to be 90 degrees?
You could record 3B1B on the worst mic possible and he would STILL sound like that
Edit: I think people in the replies are missing the joke here. Me, someone who is NOT an audiophile, finds 3B1Bs voice to be photogenic in a sound way.
It's like Charlie Parker still sounding like Charlie Parker on a cheap plastic saxophone.
I think they only had one lav mic
sound like what? "amazing"
Compare with wTJI_WuZSwE you will find that the above statement is false.
His voice compresses very well.
Imagine spending days solving this puzzle, explaining your strategy to your inmate, practicing finding the right coin to flip, and then when the day comes he miscounts and picks the wrong square
I noticed my initial miscounting since columns and rows need to have same parity.
So he picks the Parker Square?
The beauty of this method is that you only need to be able to count from 0 to 7 for the column and again for the row. Not impossible to get wrong, but much less likely than when counting all the way to 63.
My biggest takeaway from this was the throwaway thing at 28:53 - “I was thinking 5 shifted twice plus 1.” Because holy crap, I never thought about binary that way - shifting any number over doubles it! This is going to *revolutionize* my mental math.
Well ye, that’s a common theme for all bases. Shifting over in base 10 makes it 10x bigger, and in base 16 it’s 16x bigger, and base 1 it’s 1x bigger
@@Anonymous4045 it doesn't work for base 1 tho. Base 1 wouldn't work the same way other bases work, zero can't be represented and all other number you just repeat some symbol that number of times. For example, 3 would be | | |.
So if you were to "shift" it, | | | | isn't the same as 3x1, but rather 3+1.
@@GvinahGui By "shifting" a number, In base 10 "100" would be 10**2. Shifted left would be "1000", 10**3. In base 1, it's a bit different because zero doesn't really exist, so I'll just use spaces to represent the absence of a number. So if you had "1", shifted over to the left results in "1 ", the same as before numerically. So therefore, "1" in base one shifted to the left results in "1", which is 1x greater than what it was before . This is because order in base 1 is not significant, no tick represents anything more than another tick does
so was 42 shifted right tho
>
To avoid the evil warden you need to have each of the prisoners create RSA key pairs so they can communicate without being eavesdropped.
Diffie-Helman key exchange protocol for the win!
Even if the warden doesn't know what the prisoners are saying, there's still a chance they'll happen to set up the board in a way that makes the prisoners' solution not work.
Though what if the prisoners talk about a strategy they're not going to apply as a red herring? And then when they use encryption, they talk about their real strategy? And then, because the warden was trying to thwart the fake solution, the real solution succeeded?
"One is binding, small click from two..."
Here is the mod 3 arithmetic Bosnian Bill and I made.
3 seems to be a spool, some counter rotation on 4, and we got this thing open
Let me show that again so you see it was not a fluke
What comment section am I in?!
@@noahmichaels4999 welcome to the lockpicking fanbase
I’m sorry, but the most impressive part of this whole process was Grant slapping down 43 in binary just casually as it happens to come up.
I'm a computer engineering undergrad student with a electronics technician degree, multiple years of tutoring digital circuits at my university, and I still can't tell binary numbers this fast.
You can do really fast like this: If the number is even half it and write down a 0 if its odd write down a 1, subtract 1 and half it. Repeat until your number ist 0. Finally reverse the digits you wrote down (or write them back to front in the first place)
@@SugarBeetMC That's not binary. Binary doesn't have letters. You've got to be using at least base 16.
@@Lucky10279 0b is just notation for binary
@@Lucky10279
Then tell me, what base is this?
0xB101
Math channels have to be one of the only ones to say "pause right now and think about it! Please leave the video you might regret if you don't" lol
That and movie review channels
Also chess channels
I've seen the start of this video three years ago, and since then was thinking about it sometimes, when i had to wait somewhere. Yesterday evening when watching out for my baby, i finally found the solution and now watched the rest of the video. Thanks a lot for those three years :)
I also think you can calculate it a little easier by solving the row and column indenpently, since it is already layed out nicely into this square. You just merge every row, by counting the heads in that row (even = 1, odd=0), then you only have to do it up the number of 8 (3 bits), and later flip the coin which is in the row AND column you have to change.
This is probably the best math video I have ever seen (and both channels make a lot of great content about math, so this says a lot). Not only they take a very intricate puzzle and show how to solve it using somewhat simple math, but also they talk about their mental processes and what they were thinking about when trying to solve the puzzle. Normally, as a math undergrad, our classes (and by extent the content created by mathematicians) are just definition and theorem, definition and theorem, without any intuition about the processes (both historically and particularly) that took to think a problem, to solve a theorem, etc. It is great to see other fellow mathematicians showing their ideais not in the "already polished" away but in its raw form. I think this does a great job to show what a mathematician really does in their daily lives, instead of just laying out the pretty, compacted, textbook results
Underrated comment
Even with the solution, it's still crazy to think about how you can extract any information from any situation with a single bit flip.
There is a dead pixel on your camera [void screams]
That's the pixel the key is under
Right in the middle of Matt's face. Ugh.
No lie, I expected this to be the top comment.
I realized this, went to another tab to see if it was my screen. The other tab was "Matt and Grant do the whole coin puzzle for real [UNEDITED].
" and I had a small heart attack before I went to ANOTHER tab and it disappeared.
I thought my new screen was screwed and checked it immediately!
I actually realized it before watching to the end, to be precise, right after Grant mentioned *finite field* . My idea is that to label each block 0-63 in binary (6bit) and add up all the positions with head with finite field additions (xor), lets call it "sum". The result will be a 6bit binary vector. Since we have full control of all binary vectors, and since finite field addition (xor) satisfies the property that (a xor b) xor a = b, we can find the "difference" between the "sum" and the position of the key (in 6bit binary vector representation), and flip the coin that has binary value of that "difference". This way, the "new sum" will be the position of key!!!
And they did exactly that. The only thing that I didn't think through is how to compute it efficiently, since doing xor on this many numbers manually is kind of slow and error prone. Their technique of using strips and blocks just makes it a lot easier and doable in reality.
The key inspiration here is *finite field* and that property of xor, which I learned from Ben Eater's video introducing CRC (cyclic redundancy code): ruclips.net/video/izG7qT0EpBw/видео.html an actual error checking code that is still widely used in production.
Thanks for the great content, this puzzle was a lot of fun to think about.
Man I didn’t expect there to be a practical solution. What I was able to find was a proof that for any size 2^n board it is possible to assign each unique 2^n square to a set of 2^(2^n - n) cases in such a way so that each unique number is only 1 flip away from any of the other sets for unique numbers. This will require both prisoners to have all 2^64 cases memorized but I now see there is a more practical way of organizing them so as to not just memorize.
Grant: "I was thinking 'Five shifted twice plus one' heh heh, everyone thinks about binary differently."
Me: this changes *everything*
I would have been thinking "Um, sixteen... and then that's four, plus one," so I guess some people think about binary a lot more efficiently.
Sorry but can you explain what he meant by that, I could not understand what it meant when he said " five shifted twice plus one"
@@vivekbhagat8353 Sure, I'll try.
'Shifting' is the idea that when you work in a number base, you can do multiplication or division by just moving the 'decimal point' So in base 10, I can multiply 3.0 by ten just by moving the decimal point to the right, and I get 30. In binary, I can multiply 101 (the binary value for five) by two just by moving the point to the right and I get 1010 (which is the binary way of writing ten).
So the situation is that Grant is looking at this binary number: 010101 and fairly rapidly identifying it as the decimal number "21." Grant has quickly recognized part of this binary number as a pattern that he knows by heart -- that binary 101 is the decimal number "5". He adds two zeros to the right and makes the pattern into 10100 -- this is what he means when he says "Shifted Twice." If he adds one to that, he'd get his target binary number 10101.
So when Grant 'shifts' his binary representation of five (101) two to the right to get (10100) -- he's multiplying twice by two. 5 x 2 x 2 = 20. And then he adds one to get 21.
@@rcb3921 Great explanation. I was confused by that too. Sounds like part of getting the solution THAT fast also involves having some reference number that you can identify without thinking.
@@lucasholcomb643yes, exactly! And I'm not at all surprised that one reference number for Matt is 42 😁
Got it! Took half an hour but I figured it out.
Without watching the video, my sollution:
You start with 000000
Each tile on the board represents a configuration of digits to flip, so the first one is flip nothing, the next 6 are flip one digit, the next 15 are flip 2 digits and so on.
This ends up filling the board, and no matter what 6 digit binary number you end up with, you can always just flip to the right configuration with one coin flip.
Man, I enjoyed this one! Not impossible but still difficult. There probably are multiple valid sollutions, so I do wonder if they came up with the same one.
They came up with a different numbering for the squares. The number of valid solutions is ridiculously large (assuming I've not made any mistakes, around 1.6e105), but most of them are challenging to remember.
This was my solution too, I'm happy I took the time to think about it before watching their solution.
I know I’m two years late but I’m just happy to see pascal reappearing once again (even though it’s not for reasons exclusive to this puzzle)
The pennies go 1-6-15-20-15-6-1 lol
I immediately jumped to Hamming codes when hearing this, but only because of Grant and Ben's videos. Looking forward to more errors correction math. Ya'll are great!
I did the same exact thing
Same, but I went the extra mile of convincing myself it was senseless without thinking about it.
I just finished coding my Hamming code project before finding this video!
When mathematicians talk they joke about induction .
Nice profile name
Oh yeah
And this is why they don't talk to people who aren't mathematicians.
I'm confused about the three coin problem.
Suppose the key is under the "c" coin (so you need to show a result of 2), and the current coin configuration is 010. In the 0*a+1*b+2*c operation, 010 results in 1. The configurations that lead to a result of 2 are 001 and 101. It's impossible to flip one coin and turn the 010 into either of those.
What am I missing?
Edit: I was missing the rest of the video when they say this doesn't work.
😂
Hi, im confused. Did they not solve the 3x1, or did its solution not work for the entire board
@bluedragon2997 I think that there are certain start patterns for the 3 square option which means that you cannot always get the necessary result.
For instance, start with 010 = 1.
Options of end patterns are 110, 000, 011 for flipping 1st, 2nd, 3rd . These are equivalent to 1, 0, and 3(which is also 0). So, no single coin flip results in 2.
I had already spent a while trying to solve it, but did not manage, so then I decided to just watch the video. However, at 17:16 you convinced me to give it one more go and after thinking about it off and on for two more days I managed to figure it out! It was very rewarding to solve it by myself, so thank you for this final encouragement and thank you for making videos about this fantastic puzzle!
I literally stopped at 17:16 and began reading comments 4 days ago and your comment motivated me to try for my self and I finally found the solution today! Thank you
They got out of that prison fairly easily.
You might even say that it's a Parker prison.
🧌
In the discussion at around 29:12, what you're looking at is literally just the two coordinates of the chessboard.
101 = 5
010 = 2
So the thing to flip is at (5, 2) or ((6, 3) if you're feeling like 1 indexing). And at 29:39 that is indeed the square Grant is pointing at.
Spoiler
That's a beautiful way to put it!
From this perspective, it's essentially the 8 case happening twice at the same time.
(Well, it's also the 2 case happening six times at the same time...)
(EDIT: which is why Grant was viewing it as the corners of a 6-dimensional cube)
That's the same reason why hexcode is so good for 8-bit color codes and octal code is so good to encode file system rights. :-D Every digit has its own meaning.
@@NicosLeben: Think of the saved disk space possible if vendors had known all my colleagues wanted nothing but mode 777.
"we have only one mic, and the guest's voice is more important than mine."
Wouldn't want to waste Grant's beautiful voice.
But also, we definitely need music to mask both voices.
I love this video. I walked through this puzzle with my son and he got it right away as soon as I got to part of the solution where you start to figure out which coin to flip, then it clicked for him and he got the rest himself. The solution and the puzzle are so elegant, it's beautiful. Thank you!
"You can only hear the solution once, and it takes years to forget about it."
Approximately four years for me, apparently. The only thing about this puzzle is that I can clearly remember solving the thing in the past and now I'm utterly stumped. I have a feeling I had probably recently watched one of Grant's videos about detecting bit flips in data transfers...
When your two smart friends are discussing their answers to the exam
I think I see a dead pixel or something in your camera, a very clearly discrepant pixel at 9:06 to the left of Matt's face.
Classic.
@@standupmaths Could've been worse, a discrepant pixel in both my screen *and* the camera.
it's a very tiny Parker square
it's a puzzle where you have to kill or fix one pixel in order to find a code from the video
Damn, took me a while to not freak out that I had a dead pixel in my display!
There’s a tiny white spot or dead pixel or something on Matt’s face a bit before half way through the video and I can’t stop looking at it
It was driving me nuts, until I confirmed it was on the video and not a dead pixel on my TV!
I hate you.
I couldn't focus on the content at all after i spotted it.
Same :(
I thought it was my screen at first!
By XORing each row and column, you can speed up the addition process a bit.
Basically, I ended up with sixteen binary bits that you can only effect two of (I actually had them in two eight digit numbers, one horizontal and one vertical). You can then apply the same error checking algorithm to get six binary bits that code for a position on the board (that can be changed to any other position by affecting only two of the digits, one vertical and one horizontal)!
Beautiful puzzle. Thanks guys!
I learned about this puzzle in 2013 and it stewed in my brain until *2018* before I solved it! And I still wasn’t satisfied that it was the most elegant solution (I used 3 overlapping quaternary bits and a 4-binary bit solution smashed together) love to finally see this video!
I loved Grant's method of splitting the board into stripes, bands, and blocks. It reminded me of how the towers of hanoi puzzle is related to counting numbers in base 3 and just how efficient the system of numeric bases is in counting numbers.
For those of us that love the math but don’t have a lot of time, the explanation begins at 9:20
Thanks
Thanks
It's been a long time coming since that Punchcard machine collab
( Parker Grant Convergence 2)
Parker Grant Convergence 2: Prison Vindaloo
Mom: What are you watching?
Me: Im watching people doing meth.
Mom (quietly): Time to do error correction.
lol
I managed to figure out a solution, but instead of visualizing the 64 squares as a board or a line, I visualized them as a 6-dimensional hypercube (2x2x2x2x2x2). Comparing the coins in an edge of the hypercube already gives you a bit of information. There is also always a way to flip a coin in order to show where the coin is. For each square, its identifier is x+8*y in base 2, where x and y are the coordinates on the chessboard (I know one side is A to H, and the other one 1 to 8, but here, all sides are 0 to 7 instead). For example, 000000 (A1) is the null bit, as it doesn't affect anything, and 111111 (H8) affects every single bit. To get your board identifier, start at 000000, go through every square, and if it's heads, XOR the value with the current identifier. Then XOR the board ID with the target ID, and there you go! The decoding is just: calculate board ID, then that's it!
I'm actually not sure is this is satire or not, but don't bother to figure it out lmao
"...but that is a moot point because Grant can visualise cubes in all dimension spaces with equal ease."
lmaoo i'm weak
you're talking about the correction right?
Did Matt say that in this video?
Wow, I suggested Matt apply for a Grant last week, and boom! Quickest approval process in history.
Is that a Grahnt or a Grant?
best collaboration in Maths history: "Matt Parker & Grant Sanderson"
Here's my magic trick variation of the puzzle:
My accomplice is blindfolded, then someone in the audience set's up a 4x4 square with coins randomly heads-up or heads down.
Then I tell them that we'll both flip over a coin and then my accomplice will tell them which coin THEY flipped. I even offer them to go first, I just flip the board to "zero". No matter which coin they flip over, it will always encode itself.
There are some tricks to do the calculation in your head within seconds (Even drunk people you've just taught the trick to.).
Would love to hear more about this...this is one of those videos that I didn't grasp too well, how does 4x4 compare?
@@richardmclean9479 I doubt I can explain it better than the video, but I'll give it a go. On a 4x4 grid, you have 16 coins. To describe one of the 16 positions you need to convey 4 bits of information by only flipping one coin. For example whether there is an even or an odd number of heads in total would be one bit of information, however you cannot control this because you have to flip a coin. Instead look at only the lower half of the board, there is also one bit of information you can get from there (is there an odd or is there an even number of heads?), but this time you can choose to change it by flipping a coin in the lower half, or not changing it by flipping a coin in the other half. Rinse and repeat for the other sets that are mentioned in the video (lower half, right half, every second row, every second column) and you can encode any four bits into the grid by only flipping one coin.
Here's the neat calculation trick for 4x4: Look at rows two three and four and figure out if there's an odd or an even number of heads in each of them. If they are all the same (even-even-even or odd-odd-odd) the encoded coin is in the first row. If one is different from the other two, then the encoded coin is in that row (odd-even-even would be the second row, even-odd-even the third and odd-odd-even the fourth for example). Then repeat the same for the column and you know exactly which coin is encoded.
When I see the random 4x4 grid, I just find the encoded coin and flip it. Give it a try and you'll see that now the second third and fourth rows and columns all have the same parity (i.e. odd-odd-odd or even-even-even). When the audience then flips a coin, the row that coin is in and the column it is in will be different from the other two and therefore encode it self (unless it is in the first row, in which case nothing changes and by default it points to the first row, so no problem there). My accomplice then comes into the room and just needs to find the encoded coin by the same algorithm.
@@Kaepsele337 You absolutely did, thank you!!
@@Kaepsele337 one tiny nitpick from me: i first read "I even offer them to go first" as: offer them the option that they go first, which i considered weak since then you'd obviously be able to work out how to counter what they flipped.
But now trying to phrase out my objection i think you might've meant it as "I even offer them that i would go first" (quite impressive, for most* cases!) -- so the offer as stated might be a bit ambiguous.
* Only for the "most" cases since it the board was all zeroes your "flip the state to zero" approach wouldn't work, and if you LEFT it as all zeroes it wouldn't be nearly as impressive. :-) Maybe add in a requirement that there's at least 3 (or 5) heads and tails on the board?
@@irrelevant_noob If the board is all zeroes, you flip the zero to make it add to zero still. Certainly not super impressive to the audience when there are two heads and 62 tails staring at you, compared to random chaos, but still works.
5:21 "it takes years to forget about (the solution)"
can confirm, I'm here 3 years later and I still remembered
I found 5 solutions:
1. Just rub a coin against the wall, creating a flat edge. Tell your friend that the coin with the flat edge is the coin with the key underneath.
2. Yell the square with the coin. For example, "G5!!!". Your friend now knows where the key is.
3. Take all the coins and stack it on one square, the square the key is on.
4. Find the key yourself by throwing all of the coins off the board.
5. Kill the malicious warden, perhaps using the coins and/or board.
As was the case here, I like to skip to the solution part and try to work out what the puzzle was. If you're like me, start watching at 9:07
Alternative title: Two mathematicians bully viewers into solving a puzzle. xD
Hey Matt - I do audio engineering and dialogue cleanup - If you send me the audio, I can clean it up for you
Matt for Matt kind of deal.
matt just wants to watch the videos early ;)
@@omri9325 Surprised it isn't Matt Gray
Please edit the audio. Only Grant's voice is clear.
Matt Gio Wild
This ended up being one of the most enjoyable problem-solving experiences for me! I paused the video, and launched into 8 days of thinking, discussing with friends, writing Python code, and finally ended up with a solution. My solution involved assigning all possible combinations of 1, 2, ..., 6 colors to the squares. Conceptually the same, but the regions ended up being very messy and hard to count. Encoding the squares with binary numbers is much more elegant. Thanks for sharing this fantastic puzzle!
I just found myself skipping over the part where you act it out, to get to the part where you actually explain how it works, just to pause right there to give it a try myself. I am incredibly thankful you explicitly mentioned how you can only learn the solution once :D
Here is the solution I came up with when you said "Most people don't pause the video":
First, let's assume that the board is always gonna be 2^m. (In other cases, we can simply consider fictional tiles always filled with 1s (heads) or 0s(tails)).
Second, let's start with the simple case, a board of 2x2 tiles. We want to pass two "bits" of information. So we need to somehow find two independent comparisons that we can make and change them independently. For example, We compare bottomleft and bottomright, and then compare topleft and bottomright.
Given a random board, we want to transmit "the key is in left | right half" and "the key is in top | bottom half". Let's say, if topleft and bottomright are of different parity, then the key is in the top half. And if bottomleft and bottomright are of different parity, then the key is in the left half.
You can see clearly that you always have an option to flip only one tile and transmit those two bits of information (i.e. bottomright if you want to change both parities, topright if you want to change nothing, and the two others quarters for each axis separately.)
Now, to transition from the case of 2x2 to 2^n by 2^n, you simply need to observe that each you are always bound to one "quarter" of the whole board. For example, assume the board is 4x4. Once you run your initial reasoning over which quarter to change, then you are bound to choose the tile to flip in that quarter. So the solution then is to compare the sum of tiles in each corner from each quarter.
0|1|2|3
4|5|6|7
8|9|a|b
c|d|e|f
First comparison: "0123" vs "abef" and "89cd" vs "abef"
Second comparison: "028a" vs "57df" and "46ce" vs "57df"
The first comparison will tell you which quarter the key is in (and hence which tile you need to flip)
The second comparison narrows it down inside each quarter's quarter.
And you can easily apply this to any 2^n by 2^n board. For any arbitrary number, I feel lazy to think about it, so just ask the warden for a bigger board :P Say something like "it would be more difficult to solve"
You can rest easy knowing that no evil warden can defeat your logic skills.
So if I got it correctly:
The prisoners decide on this scheme to encode the chess board in 6 bits - the number of bits enough to represent the numbers from 0 to 63.
Prisoner 1 encodes the initial board using this scheme, and then chooses the coin to be flipped.
The coin chosen is special. When it is flipped, it changes the encoding of the board.
The 6-bit encoding of this new board is now the binary equivalent of the _cell on the board which stores the key!_
So now, prisoner 2 can just figure out the 6-bit encoding of the board and bada boom bada bing, the key is revealed.
Sounds about right to me
Idk what you mean by encode the chess board
You are wrong.
Not Prisoner 1 decides about the encoding. Otherwise the solution would be too simple without any math. (simplest - make 0 everything and flip to 1 those above the key, a just do any ordered pattern and flipping of a coin above the key will fall out of a pattern).
So the board is "encoded" by guards. What Pr1 can do is to change the state of it to any possible 0..63 number by only one coin.
@@TushhsuT no you didn't get what he means, by encoding it means to hash a state.
@@ultimatedude5686 This mysterious 'encoding' is explained in the video... I just tried to give a gist of the method presented.
In short, to encode the chess board means to represent something about the chess board in a different form.
Every square on the board labelled from 0 to 63 can be written in binary using no more than 6 bits. So we define 6 sets.
Set i contains those numbers whose ith bit in binary is 1. For example, 35 is written as 100011, so it is a part of sets 1,5,6.
Now, for each set, if the number of heads in that set of squares is even, we write a 0, and if it's odd, we write a 1.
Hence for each set, we get a 0 or a 1. So we get a sequence of 6 bits, which is the 'encoding' of the chessboard.
I thought that this dead pixel on Matt Parker's head was some dirt on my monitor, and I almost broke my monitor screen trying to clean it.
The warden: rotates the board 90 degrees when you leave the room
Matt, Grant, Michael Penn, and redpenbluepen top notch production. With each offering unique presentations and approaches, one can really absorb the concepts and appreciate the quality.
You two provide the long story, ones who go the mile to really set up and prepare the student. The latter two are a quicker pace and is more geared towards proofs and practice.
Thanks you and best wishes. 🍻
Before I viewed their solution, I came up with my own which is very similar, but I think mine is a little easier to compute by hand.
1) Number the rows and columns from 0 to 7.
2) Number the squares sᵢⱼ where 0 ≤ i ≤ 7 and 0 ≤ j ≤ 7.
3) Compute the "column bits" by XORing the bits in each column: cᵢ = sᵢ₀ ⊕ sᵢ₁ ⊕ ... ⊕ sᵢ₇
4) Compute the "row bits" by XORing the bits in each row: rⱼ = s₀ⱼ ⊕ s₁ⱼ ⊕ ... ⊕ s₇ⱼ
5) Compute the column value by multiplying the row numbers by the corresponding column bits and then bitwise XORing the results:
C = 0c₀ ⊕ 1c₁ ⊕ 2c₂ ⊕ ... ⊕ 7c₇
6) Compute the row value by multiplying the row numbers by the corresponding row bits and then bitwise XORing the results:
R = 0r₀ ⊕ 1r₁ ⊕ 2r₂ ⊕ ... ⊕ 7r₇
Let the co-ordinates of the square where the key is hidden be (Cₕ, Rₕ) (h for hidden). We compute the co-ordinates of the square to flip (i,j) by XORing the current values with the hidden values: (i,j) = (C ⊕ Cₕ, Rₜ ⊕ Rₕ).
Why does any of this work?
If we flip the bit sᵢⱼ, it will cause column bit cᵢ and row bit rⱼ to flip, while all the other column and row bits are unaffected. If we compute the new column value C', first note that the new value of cᵢ' is (1⊕cᵢ) and if we substitute that into the expression for the column value we see that
C' = 0c₀ ⊕ 1c₁ ⊕ ... ⊕ (i-1)cᵢ₋₁ ⊕ i(1⊕cᵢ) ⊕ (i+1)cᵢ+₁ ⊕ ... ⊕ 7c₇.
But i(1⊕cᵢ) = i ⊕ icᵢ. And XOR is commutative and associative just like regular addition so we can move that i to the end of the expression and we get
C' = 0c₀ ⊕ 1c₁ ⊕ 2c₂ ⊕ ... ⊕ 7c₇ ⊕ i
= C ⊕ i
= C ⊕ (C ⊕ Cₕ) (by definition of i)
= (C ⊕ C) ⊕ Cₕ (because XOR is associative)
= 0 ⊕ Cₕ (because XOR is its own inverse)
= Cₕ
The exact same thing works for the rows, so we've solved the puzzle! The second prisoner computes the row and column values and they point to the key.
I made a spreadsheet you can play around with in Google sheets if you're interested docs.google.com/spreadsheets/d/1cVzJ-7KortGh7TmGKOnoc6XyOJix3Gu4rzVwfLnmf1U/edit?usp=sharing
Now that I understand the solution, weirdly, I have an easier time explaining it without the visual support. So, for other people out there that see things like me, maybe this will be easier.
Each square with heads on it translates to the square index, from 0 to 63, written in binary. You want prisoner 2 to be able to sum, with the XOR operator (addition without carry), all squares with heads, and having the sum represent the square where the key is.
Now, XOR has the nice property that flipping from 0 to 1 or from 1 to 0 are both represented by XORing the square index, i.e. X xor X = 0. So, flipping a coin is the same as XORing its index to the sum.
As prisoner 1, you are given a board with a starting sum, let's call it WARDEN, and let's call the key position KEY. You must change the starting sum by one flip so that the new sum is KEY, resulting in the equation WARDEN xor FLIP = KEY. Rearranging the equation, you get FLIP = WARDEN xor KEY.
So, as prisoner 1, you list all squares with heads AND the square with the key, XOR them together, and this gives you the square to flip.
Also, even if it doesn't prove anything, you can see that, if there were fewer than 64 squares (i.e. if the number of squares is not a power of two), the value FLIP you computed could end up giving you a non-existent index, so the algorithm wouldn't work.
Hope this may help!
ah yes
This helps. I didn't even properly understand the problem.
'managed to find a dungeon' sure...
We all know Matt Parker has a dungeon in his basement just in case he needs it for a math(s) puzzle.
Alex Martin
“math puzzle” uhuh yeah sure
Someone's now thinking: "that's the weirdest thing someone has ever done in my dungeon, and I've been renting it out for 25 years".
After months of not completing watching this video i came up with a solution... and i think its easier to understand than the solution in this video - but harder to calculate:
The set of all subsets of a set with N elements is 2^N. We need 6 bits to encode the position of the key. So the board fields 1 to 6 are designated for that purpose - we name them "encoding fields".
All other fields are assigned one subset of those 6 bits (which is 2^6 = 64) except the subsets with one element... which happens to be exactly 58, including the empty set (no change if flipped) as well as the set that includes all 6 encoding fields. We name those "subset fields".
Now each of the 58 subset fields - if it has heads coin - is interpreted to invert the bits of its subset out of the first 6 encoding fields.
Now the coins with heads on the 58 subsequent fields convert the binary value of the first 6 coins into some other value from 0-63. If only 1 bit of that value is incorrect, you just flip that bit. If 2 or more bits are incorrect, there is a subset field that flips exactly those ... and that is the coin that needs to be flipped.
All the 2 prisoners need to agree on before the game, is which fields are assigned the 6 encoding bits and the which field is assigned each subset.
That is exactly how I did it! Only had to pause the video for a few years! 😅 So glad I did though.
Just to point out something interesting about the way the problem is posed:
In chess computing, a method of hashing known as Zobrist hashing is used to make hashing of successive chessboard positions cheaper. A Zobrist hash has the property that it can be computed cheaply from the Zobrist hash of a related chessboard position in time proportional to the number of altered squares on the chessboard.
Since successive positions in chess differ in at most two squares, this is a huge computational savings over recomputing a hash that requires you to consider all 64 squares at once.
The chessboard puzzle posed here is closely related to the way Zobrist hashing is actually implemented. I would go so far as to say that the puzzle was designed by someone familiar with the technique, and provocatively posed on a chessboard as a nod to it.
“Take some time and solve this puzzle on your own” the most advanced math I took in college was statistics and all I knew was excel spread sheets I CANNOT fathom what I was suppose to come up with
Well this isn't really a higher-maths problem, it's just a game puzzle... Pen and paper should do fine.
But they could've suggested we go over smaller-size boards first, like 1x2, 2x2, or even 4x4... Guess that's such a trivial step in approaching these puzzles that they would just assume we'd do that even without a hint for it. ^^
All the vector stuff they were discussing made it seem much more math heavy than it needed to be. I definitely wouldn’t have come up with this solution either though, hahaha
The first method works perfectly. You don't need the 6 regions at all.
Instead of the "classic" addition, you should use the "XOR" addition where adding and substracting are the same. Write binary numbers and decide that for every digit 1+1=0. That's it.
The 6 regions are just a way of doing the XOR in a human-friendly way because writing out the calculation for all those numbers isn't fun.
6:28 This is how I imagine Matt leaves a room 100% of the time.
I had heard this puzzle about 4 years ago but never solved it. Thanks for giving me the opportunity to pause the video and solve it, cause I actually did! It took me about 2 days, was pretty tough, and I reasoned about it in a similar way. Once I realized "the trick," the pieces came together and I figured it out, so I watched the rest of the video to see that I was right! Great video, thanks a lot for this.
theoretically if you could both memorize 64^2 different strings of 64 bit values and assign 64 specific values to each square, it would be possible no matter the boardstate to change one coin to match one of the 64 possible assigned values that match the box that the key is in. not humanly possible, but 100% guarenteed
17:10 "You can't feel that bad because anyone watching is looking it up." Not me! I solved it last night after watching the 3Blue1Brown video (the one that explains why it's only possible when the number of squares is a power of two) and am watching this just to compare my approach to yours. :)
These guys are the Gods of "Recreational Math"... I loved it 🤩 thank you so so much 🥰!
What madness is this, can't watch both vids at same time
Stand up maths best moments when
and try to pause the video and solve it
Just finished watching both vids and wow that's an ingenious solution, love the crossover
YOOOO AGADMATORINO
It was in this position that the Warden resigned the game
Matt and Grant got captured captured captured
After seeing 3b1b's video on this. I solved thus puzzle on a road trip. Hours of fun! I eventually came up with the same solution but with the meanings of the coins rearanged (the conis meant the same things, but were in different places on the board). My thaught process was wildly different and my explanation on how it worked was MUCH messier, but it was essentially the same.
I love how two seemingly different solutions with almost completely different processes came out to be the same thing, this is why I love math. (By the way 3b1b's video helped a ton in steering me in the right direction)
This puzzle made an otherwize boring car ride fun, thanks Matt and Grant and keep up the amazing work.
When I paused I found a solution that I assumed would be the solution they gave but it was actually different. Mine might be slightly harder to calculate in practice but is simpler to describe. Step 1: We label all the tiles 0-63, then we add them up mod 64 and that is the tile we get, but there’s a catch. When we add x + -x, we get 2x instead of 0. With that one change we can add any number 0-63 with the change of one coin. Firstly, if the numbers already code for the right space, flip the 0 coin. If the numbers are 32 away, flip the 32 coin. For all other possible values, n, there are 4 possible scenarios. If n and -n are both 0, flip n. If n is 1 and -n is 0, flip -n. If n is 0 and -n is 1, flip -n. If n and -n are both 1, flip -n.
Jokes on you I watched the video and still don't understand the solution
Hey! :3
bruh
Me DM’img my alt because I’m lonely
The Trinity.
Pappa?
papa is here
Took me ~30 minutes of thinking and ~1 hour of coding to solve. My first guess was to take parities of every coin, every 2d coin, every 3d, every n-th coin but it didn't work when i coded it. I tried every 2^n-th coin, every prime number but it also didn't work. Then I decided to change my approach and tried to add up all the numbers (also found out that it won't work in 25% of cases) and following the same logic as in the video remembered that XOR function is symmetrical and got the final solution. No need to think in terms of 6-dimensional cubes :)
P.S. BTW, it won't work in case of a non-power-of-two number of squares. Some modifications to this strategy will be required.
Great video! I watched the first part a few weeks ago and have come back to see if my solution matches yours. I came up with something different than the solution you discuss with Matt. Interestingly, my solution provides a different way of glimpsing into which configurations may or may not be possible. Here's what I did:
Take the parity of each row, and the parity of each column. Each is an eight-bit sequence. Note that by choosing a coin on the main grid to flip, we can selectively switch any one bit of the "row parity" sequence and any one bit of the "column parity" sequence. We now have a new challenge (or rather, two identical challenges): With our eight bits of "row parity", flip exactly one of them to communicate the row containing the key. And independently do the same for the columns. Hm... This feels like a familiar puzzle. In fact it's the same one as the original with only eight coins! Done twice!
I'm still stuck. Eight is a lot. But... If we arrange THOSE eight in a 2x4 board, and take the parity of the rows and columns of THAT, we can reduce this eight-coin puzzle to a four-coin version and a two-coin version in the very same way we reduced the original! And that four-coin version can be reduced further by laying it out in a 2x2 grid to get two 2-coin versions. At that point, solve by hand. For me I arbitrarily decided that 00 and 10 point to the first coin, and 01 or 11 point to the second.
Bubble up these smaller puzzles to eventually find which coin of the row-sequence needs to flip, and which of the column-sequence to flip, and then flip the corresponding coin in the big chess board.
I imagine that my solution implicitly is just selecting a different way to partition the board into the six regions overlapping regions you discuss with Matt. What's fun is trying my solution on different board sizes. A 6x6 looks easy! Take each row and column, let's lay THOSE out in a 2x3 and... hm. I also struggled to color my 3-color cube before deciding it was a no-go. In terms of generalizing my solution, we can say that an N-tile board is solvable if each of N's prime factors is "solvable" (since we factor it down with each cris-cross reduction). After watching this, I'd wager that 2 is the only such solvable prime - which means the powers of 2 are the only viable boards!
Thanks so much for this treasured riddle. As you mention to Matt, a good puzzle is a real gem and this one definitely gave me a ride. Let me know what you think of my solution.
Takes years to forget? You underestimate my abilities
6:18
I'm leaving this comment here so in a few days when I think I have solved it, I can just resume the video where I left off.
They only use the strategy, not like reveal how to do it
Thanks for the timestamp. I guess I'll be doing the same
(And leaving a comment so that every time someone replies I get reminded about the puzzle)
Don't mind me either
@@ammyvl1 What? Your comment doesn't make any sense. What they do and talk about communicates what the strategy is and how it works.
!remindme
The solution starts at 22:09
I love you
Thats some disrespect right here
@@ИльяХерунцев Not really. Up to that point and including basically all the sister video to this one on 3B1B's channel is basically just Grant rambling about how he proved that an alteration of the puzzle made it impossible, which is unnecessary and confusing when the solution doesn't require any sort of thinking about vectors in higher dimensional cubes. He disrespected us by taking up so much time being proud of breaking the puzzle instead of explaining its solution or the smartest way to go about solving the puzzle.
@@QuesoCookies that's not a video nor a channel about solutions to particular problems, that's a video of two people having fun and sharing it with others FOR FREE, they don't have to do anything for you but do it for free and you have the audacity to be pissed about not them just showing freaking solution right away
@@ИльяХерунцев people can view the video in whatever way they want! if they only care for the explanation then what’s the problem with that? also you’re acting like this video being free is some sort of charity work or done out of good will. it’s not. it’s not free because they are nice it’s free because it makes the most money this way. they get paid for this yknow? youtube as a platform makes big money BECAUSE the videos are free to watch. if making the video cost money made more money then it would cost money to watch. also they aren’t doing anything for me or you we don’t know them. it’s just a silly little youtube video. let people watch how they please and enjoy or not enjoy as they please
This is the best math riddle solution that has ever been made.
Thank you for pushing me to look for a solution before giving the answer. The "you can't forget a solution once it's been given and there are few good riddles" pushed me to pause and think.
While I initially had nothing comme tu mind and was therefore not going to try, a few minutes in and the solution was forming.
And I'm pretty happy I could work it out
I need to flex here.. I solved it in about 30 minutes
what I did differently is that I separated row and column positions from each other and encoded that in the row and column bands respectively
and also, you could add up the number of heads in each row/column and then calculate with those partial sums to make the calculations easier
I came up with probably exactly the same solution as ypu! Separating Rows and Colums helps a lot! Partial sums I find pnly useful if you are able to write them down. I tweaked the encoding a bit, so that the decoding can be done easily in your head. It starts like: "If the number of heads (or tails, what ever is easier to count) on the left side of the Board is odd, then the key is on the left side, do the same on the left sides of each halfs, etc." As a bonus, with this encoding the coin to flip is the one which hides the key, if the coins have certain symmetries. Therefore it is easy to spot (as it breaks the symmetrie) and the encoding is invariant to the orientation of the board in these situations
10:15 You might explain it later in the video, but how do you know which is the null bit and which is the active bit? Couldn't the warden rotate the board so you don't know which way is up? Apparently, you need to agree on an extra piece of information, e.g., which side of the table the chair is on so you can tell the orientation of the board your partner was assuming.
Not having heard the solution yet, this sounds like a Shannon limit problem. Reliably encoding information over a noisy communication channel.
I'm 3 years late to this, but its good to know that my 5 minutes of thought on this were roughly the same as Matt's initial idea. I'm not going to spend 3 days thinking about it, but it's nice to know I'm thinking somewhat the same as him.
We have been SCAMMED. 6:56, the cameraman was hiding the key, and the camera switched to a different perspective. Since the camera man was clearly not running the cameras, Matt must have been , thus he knew where the key was all along. Love these math videos, you guys are awesome. Thumbs up from New Orleans.
*They said infinity war would be the most ambitious crossover in history*
Me:
Grant: hold my π
Matt: hold my Parker square
I knew such a comment will be here eventually
A variation which IMHO makes the trick more impressive, but easier, is to have the warden arrange the coins in whatever he sees, fit, then have prisoner #1 flip a single coin and leave the room, and *then* have the warden place the key and flip (only) the coin where the key is placed. So neither prisoner gets to see where the key is, but prisoner #2 finds it anyway. The strategy prisoner #1 uses to select a coin to flip is the same as the one prisoner #2 uses to identify the coin that was flipped.
That seems like a cool variation
"If I can't do it, I must prove nobody can!" Does the solution require that you need to agree upon the axis and their direction of them? A malicious warden might just put the chair on the other side of the board?
It absolutely does and I don't think there's a way to solve it without
You have to agree on the null corner, but counting down columns rather than across rows doesn't change the solution.
Most chessboards do have letters and numbers to identify the squares from all sides
True, true, so it would still work if you used the chessboard coordinates.
@@leodip97 I've never seen or owned a chessboard with the numbers and letters on it
I watched this video 3 months ago.. And i dont remember the solution.
It doesnt take years to forget
KN-44
Black Ops 3?
Two of my favorite youtube math-heads collaborating on a math puzzle? That's like... *counts on fingers and uses a couple of toes as well*... AT LEAST TWICE THE AWESOME!
@18:50 Dead pixel in the camera (look closely in Matt's left eye, white pixel).
I watched the introduction and stopped it when it they said I should if I wanted to solve it.
It took me about 8 or 9 days of stewing on it before I managed to solve it, and then I finished watching the video. While my encoding scheme divided the board differently, it was the same solution.
Anyone watching this who hasn't seen the solution yet, ABSOLUTELY pause it and try it yourself, it's absolutely doable, given a basic grounding in information theory.
Me, watching this at literally 1am: *ah, yes, this will surely be of use for me at some point in my life*
Plot twist: the malicious warden turns the board around before the second person comes in
Unless he turns it upside down, it will still work due to the fact that they encode the position by rows and columns
@@stensoft Even if the board isn't labeled, you could tell that it has been turned 90 degrees because a dark square would be on the right. I think it would work half the time when counting from the wrong side (180 degrees), because a flip will make the rank (the row number) of a coin equal to 7 - rank, or rank XOR 7. So if there are an odd number of 1-coins, then it will work because it is an odd number of XOR 7s, which is equal to one XOR 7, which moves the coin to the right side of the board. If there are an odd number of 1-coins, then the square identified won't change and you'll just count from the wrong side and get the wrong square.
But, a malicious warden will make that chance 0% and force an even number of 1-coins. So if the board is turned, you would have to guess the right side.
Other way around matt, a venn diagram has every possible intersection, an euler diagram only has populated set intersections.