Ah the classic mathematics career path. Undergraduate > Masters > Doctorate > Postdoc > Assistant Professor > Associate Professor > Professor > Prison Warden
@@CrushedAsian255 basic math classes giving weird questions when first learning about math operations (addition, subtraction, multiplication and division)
After seeing this video a few days ago I could not stop thinking about it, and even after learning the solution I was so amazed by how this could even be possible. I started learning some basics of Python this summer, and today I wrote some code that would allow prisoner 1 to determine which coin to flip and then prisoner 2 to determine where the key was based on the new arrangement. It was the most fulfilling thing I've coded so far and I'm grateful to have been introduced to this puzzle! Thanks for making such an inspiring video!
Matt Parker and I talk about the solution to the original puzzle on his channel: th-cam.com/video/as7Gkm7Y7h4/w-d-xo.html This solution is _highly_ connected to Hamming error correction codes, so much so that doing this puzzle inspired me to make a video about them: th-cam.com/video/X8jsijhllIA/w-d-xo.html
@ "cool" means that the speaker is comfortable with the statement and it's implications. "Cool!" means the speaker is comfortable and excited by the statement, this is possibly what VWLZ intended.
Haha I just came from the Hamming codes videos, so my mind was already primed to think about this in a certain way. You really are an amazing teacher BTW, in case you haven't heard it enough from all your other fans.
Why do mathematicians always set their puzzles in prisons? Simple: min-maxing. You have maximum amount of time, minimum amount of distractions and maximum motivation to solve the puzzle correctly.
A: "Wanna go to their wedding ?" B: "Nah, I'm busy, I'll just send them present." A: "There will be an extremely complicated math puzzle which related to higher dimension and computer science." B: "Done, let's go."
@@mikelap4244 it can be better odds, for example, you can tell your partner that the key will be under a coin with heads, and if the key was placed under a tails coin, make it heads, and if its heads, flip another heads coin to tails. This could increase your chance of success by quite a bit.
Same lmao, I forgot that you *had* to flip a coin. So I was like "okay, if they're the same, it's the left square, if they're different, it's the right square, ez"
Video stopped, I rewatched the first minute trying to determine if you indeed HAD to turn a coin. It looked simple with having the choice not to, as CaTastrophy427 spelled out. Even when forced to flip a coin ... see my own comment for solution.
This is honestly the first time I understand what that representation of a 4D cube is supposed to convey, it's not about somehow imagining how it would look like, it's just representing the relation of how the vertices are connected
It also is what one could look like. The flat cube, if you looked at it from the top down, is a way cubes can be positioned in 3 dimensions. The same applies for the 4d cube
the 3-D projection of the 4-D cube is brain-breaking. He demonstrates the 2-D projection of a 3-D cube and then constructs the 3-D projection of the 4-D cube, which of course prompts you to think about how that 3-D projection is expanded into 4-D which our puny brains can't do. ugh.
That's correct in the context of graph-theory and topology, but not geometry. By definition, all sides of a 4D cube must have the same size as each other, regardless of how it looks when projected
A weirdly math obsessed weird eastern european uncle of the groom gave him this riddle in order to be able to say “well *slaps knees* i gotta go, the missus needs to leave”
@@pradyunmore6727 Probably the hint was that two of the rows were repeated, especially the two that represent 32, or space in ascii. That and a suspicion that youtubers like to leave easter eggs in their videos.
For those interested in this puzzle, this puzzle is also known as "The Devil's Chessboard." Of course there are multiple ways to attack this problem, but interestingly one solution you will find online also has a "computer science" flavor to it, similar to the error correction motivation as seen in this video. A possible solution to this puzzle is to label the the cells of the 8x8 board from 0 to 63 (we do this because we are putting our computer science hats on and start counting from 0). We then note the labels of each cell holding a coin with heads (or tails ... it doesn't matter) facing up. Convert each of those labels into its corresponding 6 bit integer (note that every cell on the board is in one to one correspondence with a binary string of length 6) and XOR all those integers ALONG WITH the label of the cell holding the secret key location. Now convert the result back into an integer which points to the cell holding the coin you should now flip. When your friend looks at the board, he/she will then (using the same labeling as you) XOR all the cells with heads facing up (or tail ... if that was what you used earlier). The final XOR result will be the cell location holding the key! For those not familiar with XORing two numbers, you basically need to line up the two 6-bit integers and look at each column where if you see two 1’s or two 0’s you write a 0 below and write 1 otherwise. Another interpretation is to write a 0 if the two bits are the same and write a 1 if the two bits are different. For example, 111000 XOR 010101 = 101101. You can play around with this strategy, by using a programming language. To XOR two numbers N and M you typically would need to type “N ^ M”. To see the connection to computer science, check out an encryption technique called a "One Time Pad." It works exactly through XORs similar to the solution of this puzzle. Let's say you want to encrypt a message, M, to send your friend, and supposed it is N bits long. For a secure encryption, you and your friend should generate a (uniformly) random N bit key, K, beforehand. Then to generate your ciphertext, C, you should compute C = K XOR M (or M XOR K because XOR is commutative which is fairly straightforward to verify). Then your friend would compute C XOR K (or K XOR C) to reveal the message M! The reason this works is because K XOR K always equals 0 for any choice of K (in technical terms K is called the "inverse" of K) and 0 XOR C always equals C for any choice of C (in technical terms 0 is called the “identity”). In addition to being commutative, XOR is also associative. If these properties sound very familiar, it is because it is! XOR sounds kinda like a special addition where negative numbers are just the numbers themselves! With this in mind, I’ll use “+” to denote XOR for brevity. Putting this all together, we know that C = K + M and that when revealing your message your friend will compute C + K = K + C = K + (K + M) = 0 + M = M! How does this relate to the Devil’s Chessboard? Well we can think of XORing all the cells with heads (I will ignore the situation where we use tails instead but the analysis is the same) as our “key” K and the key location being our message M. Formally, let K = X_1 + … + X_N where X_i is a cell with heads facing up and let M be the cell holding the key location. To generate our “ciphertext” which will be the cell holding the coin we flip, we perform as stated above C = K + M. The ingenuity of this solution lies in the fact that when your friend comes in and performs the XORing procedure stated above, he/she will compute C + K which as seen before will expose our message M! To see why this is case, note that either C will have been turned from tails to heads or turned from heads to tails. In the first case, your friend will see X_1, …, X_N, and C as heads and compute X_1 + … + X_N + C = K + C. In the second case, C will have flipped a coin that was previously heads (call this X_j), and your friend will then compute X_1 + … + X_(j-1) + X_(j+1) + … X_N = X_1 + … + X_(j-1) + 0 + X_(j+1) + … X_N = X_1 + … + X_(j-1) + (X_j + X_j) + X_(j+1) + … X_N = K + C. The second to last equality used the fact that X + X = 0 (mentioned above) and the last equality was due the commutative nature of XOR. As we see, no matter the case, your friend will ALWAYS compute K + C revealing the location of the key! This puzzle is indeed very cool, and surprisingly has another computer science angle that motivates not only ideas from coding theory but also cryptography!
@@padraighill4558 Thanks for the feedback! I had written the post in a separate program and pasted it into youtube. I guess the formatting didn't carry through. There should now be new lines in the post delineating the different sections.
I have a strong feeling that this solution is functionally equivalent to the one that's proposed in the other video-for a given configuration, the same coin gets flipped, and this is just a more CompSci way of describing it. That being said, i'm definitely too lazy to attempt to prove the equivalence :P
I'm currently reading a book on quantum computing and even though it's almost totally unrelated to that topic, this video made me realise why there's a need for code correction after calculation. Very amazing how separate branches of math and science intersect and help each other's understanding
Not to be a dick but why are you reading a book on quantum computing if you didn't even know about error correction? It's a rhetorical question obviously and I see how quantum computing can be fascinating, but you'd probably appreciate qc more with a background of classical computing first.
I will say honestly it may seem unrelated on the outside, but reductions on sets of states is at the heart of computer science and one application of that general activity is error correction. Error correction does come more out of the EE or ECE field, to be sure, but the general idea is the crux of C.S. .
@@GothicKin Not to be a dick, but why don't you read properly before making a comment, he never said "I didn't know what error correction was," he said he now understands why after a quantum computation you have to do error correction to see the final and real result.
@@coleabrahams9331 It's actually more accurate to call it a booklet since it's less than 100 pages long and only covers the basics of quantum computing. Very much just an introduction. It's a Dutch book called "De quantumcomputer: een digitale revolutie op het punt van uitbreken" (The quantum computer: a digital revolution on the brink of breaking into scene) by George Van Hal. I doubt there are English versions of it, though.
True story, before I clicked on this vid, Iwas watching Standupmaths's video on generalized Fibonacci numbers, where the sequence both extends to negative numbers but allows for complex number inputs.
One of my favorite math teacher, and also a friend, died of cancer yesterday. She used to love this channel. She will never get to see this video. She was a strict, funny and caring teacher. Rest in peace Layla 😢🙏
For those who are intrested in the general case: The problem of how to encode data with a limited number of bitflips was treated in 1989 in the paper "Coding for write-efficient memory" by Ahlswede and Zhang.
I was surprised as well, but then I thought it's ok too. I've been into weddings where people talk about computers and AI a lot. That's because I have my friends who share common knowledge in this domain. So it's normal for Grant to talk about Maths in the wedding. (Btw talking about technology doesn't look weird enough, but discussing Maths problems...)
From the prisoner puzzle, the rule says you can flip one coin but doesn’t say that you have to flip a coin. So I am wondering, if “not flipping coin” is an option, I feel the 3d model will work since you can always stick too “key = the less number of head/tail” for example: 001,110 both tell the key is in the right-most slot. Of course. This is based on “if not flipping a coin is a possible option”
3B1B please explain not only Hamming codes (I already know those) but also Reed-Solomon and LDPC codes (I get overwhelmed by unknown math involved). I actually want to be able to implement them. Not just implement, but understand how and why they work and play with them. I looked at source code of Reed-Solomon from the ZXing library and although it works, I couldn't figure out how it work.
(Without these complex strategies) I think it would be really funny if the warden put every coin on heads except for tails on the key square so you can’t flip it because then they’re all heads and flipping another one would give you like a 50/50
When you first stated the problem, I understood that you "may" (instead of "must") flip one coin. The possibility of not flipping any coin definitely changes the problem. I know, for example, that it would be possible to solve for 3 squares. Have you given any thought to this variant of the problem?
For this variation, it is possible for any number of squares that is a power of 2 or 1 less than a power of 2, but it is impossible for all other cases. In case of 3 squares it was possible since it is 1 less than 4 which is a power of 2. To find how o solve for squares 1 less than a power of 2 you just use the same strategy for solution for powers of 2, but assign a binary number to not flipping any coin.
@@azertykeys9011, no, the Imperial Fists' logo has an armoured gauntlet hand. The raised fist has been a symbol of revolt throughout history. In modern times this symbol particularly represents civil rights movements and resistance to discrimination. Here it's integrated with the rainbow flag which represents sexualities that are discriminated against.
Prisoner 1 **Confidently walks in, flips a coin, leaves.** Warden **turns board 180 degrees** Prisoner 2 **Walks in, takes a guess, no key under the coin** **shocked pikachu face**
the scenario assumed the warden would attempt to interfere with you *before* you do your bit flipping, because he knows your strategy. If the warden is allowed to interfere with you *after* your bit flipping, he could just flip any coin once and change the answer. Your scenario is smart, but any interference would do the same thing, render it entirely impossible.
Surprisingly, because your shorts are very calm in general (voice and visual wise), therefore, I am much more likely to watch the whole video. Noticed this several times.
I'm not in the field of math or IT, so the error correction always looked to me like magic. I would be happy to watch you explaining how it really works.
To answer your question of why mathematicians set their puzzles in prison, the only way to force people to play through a challenging puzzle is to remove every other possible option besides solving the puzzle. In the case of prisons, you either solve the puzzle or do nothing
I'm afraid 64^(2^64) is not a size of a haystack when you're looking for a needle; rather a size of the whole history of the multiverse when you're looking for a single moment of a single gluon fluctuation
Yes, I was very happy to note that the table of 0's and 1's was the ASCII representation of "Do math!" and that the single bit flip illustrated actually turned the a into an e
I noticed that and I howled in laughter at 5 in the morning. Grant has the sharpest humour, tying in chessboards, bit flipping, math and meth in one 3 second punchline
@@meghanto Yeah, I didn't realize that and had to look back when I saw this comment. Additionally, once the warden realizes that the prisoners have come up with a foolproof solution, the warden can at least arrange the coins to spell out "F*** YOU" which is also exactly 8 characters.
Watching this at 5AM wasn't the best idea of my life It felt like watching a Japanese lesson teached in Russian But it was still amazingly interesting !
@@palmossi 1:12 "the two of you can strategize ahead of time" and the strategy is to say "if i flip a coin, the square under has the key". warden cant do nothing about that
...because neither of you know what the board will look like when you start. How prisoner 2 can tell which one was flipped when they've never seen the board is the problem we're trying to solve.
In the case of 3 coins there’s a simpler solution that doesn’t require math but it definitely doesn’t work for any other setup. “The key is under the unique coin” no matter what the initial setup is you can always make exactly two coins match which tells prisoner 2 that the unmatched coin has the key. This only works if you aren’t forced to flip a coin though
12:45 A (maybe) different proof: Let #(B) denote the number of blue vertices. Similarly for #(G) and #(R). #(BB) denote the number of blue-blue edges. Similarly for #(BG), #(BR), etc. According to the rule, the 3 edges at any blue vertex are blue-blue (BB), blue-green (BG) and blue-red (BR). Thus each blue vertex MUST serve as the end of ONE and ONLY ONE blue-green edge. Thus #(B) = #(BG). Similarly, #(G) = #(BG). As a result #(B) = #(G). Similarly, #(B) = #(G) = #(R).
Alan Turing didn't go to prison. For the "crime" of being gay, he was pressured into undergoing "chemical castration" to avoid prison time. This treatment undoubtedly contributed to his depression and suicide. Not sure why so many people liked your "joke" - it's pretty shit.
I love the answer someone gave where he said wait 8 years, flip the coin where the key is. Prisoner two comes in the room and sees dust on all the coins except 1. He knows that was the coin that was flipped and that’s where the key is. Took 8 years for freedom but when you’re serving life, that’s a drop in the bucket.
Its wild how i saw this on my shorts then I saw that black ops 3 zombies easter egg just found out they have to use this method to progress the easter egg
easy. pick up the coin with the key under it, open the compartment, take out the key, close the compartment, set the coin back down on the other side, and set they key on the chessboard.
A gorgeous illustration of Maths as *pattern making* . "A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas." - G H. Hardy
Love the high-D visualisation. My first though on the puzzle was also Hamming codes, but I couldn't get my head around the application to this particular problem. As a visualisation, it makes SOOOO much more sense! I'd love to see one that's more dedicated to Hamming, I'd love to see how you apply your visualisations to the question of overall packet length vs. number of correctable bits.
If asked to color the 4th dimensional cube's vertices I never would have thought "Put the colors on a 3d projection's diagonals" would have been the answer. It seems way to elegant and perfect to have been the answer. That's crazy.
This is a really good puzzle. The choice of a chessboard is significant because it has 64 squares. But to be a truly great puzzle, all the relevant properties of a chessboard should be significant, not just the number of squares. A chessboard can be rotated 180 degrees and it will look the same. If Prisoner 2 is led into the room and he notices that the room is 180-degree symmetrical with two entrance doors, and it also so happens that the arrangement of heads and tails is similarly symmetrical (ie a palindrome when written as a sequence), then he only has a 50% chance, no matter what he has previously discussed with Prisoner 1. There is absolutely no way to know whether he is looking at the board from the same side as Prisoner 1 was. So it's a choice between square x , and square (63-x), and those can't be the same square. So to solve the problem, Prisoner 1 would have to never leave a palindrome. He can certainly avoid leaving a palindrome, but that removes some of his options, and he doesn't have any spare options. Therefore the problem, as presented, really is impossible, after all.
I can hardly find appropriate words to describe the quality of your work on TH-cam... It's just astonishing and breathtaking ! You explain beautifully clearly and concretely ideas I would never have thought of myself and it just opens up to me a new way to see things, in math, science or more generally in real life ! I sincerely thank you for inviting me so cheerfully in such wonderful mental experiments !
Thanks for sharing this puzzle-it's a really interesting challenge! I enjoyed the opportunity to think through it. However, I have to admit I was a bit surprised when you directed viewers to another channel for the solution. I personally prefer to keep everything within your content, as I’ve always found your videos valuable, and I wasn’t particularly interested in going to another TH-camr’s channel. So I solved it myself. Thanks again for introducing me to this problem!
Loved this puzzle. I came up with two related puzzles (both solvable). #1: Same goal and constraints, but the board is 6 x 6 with a D6 in each square. To communicate the special square to your partner, you must advance just one die by just one pip. (Advancing a 6 means bringing it back to 1). This can also be done with any board where the number of squares is a power of the number of possible states for each square. Advancing one square by one state (with wrap-around) is all you need. #2: The warden is going to give you a row of stacks of coins with the tiny key hidden beneath one of the stacks. You do not know in advance how many stacks there will be in this row or how high each stack will be. You have to communicate to your partner which stack hides the key by just placing a single additional coin on one of the stacks. You can discuss strategy in advance, but warden gets to listen and try to thwart.
Ah the classic mathematics career path.
Undergraduate > Masters > Doctorate > Postdoc > Assistant Professor > Associate Professor > Professor > Prison Warden
haha
Interesting, but where does buying 78 watermelons fit into this?
@@CrushedAsian255 basic math classes giving weird questions when first learning about math operations (addition, subtraction, multiplication and division)
>Physics video commenter, the most evolved form of intellect around.
@@CrushedAsian255 he meant that if your mom is 56 years old and your car is red then how tall is your father?
He's hiding messages in the checkerboards. They're all in ASCII.
0:29 "3b1b :)"
0:51 "3b1b :("
0:57 "Tau < Pi"
1:26 "FlipBits"
1:27 "BlipBits"
1:30 "ClipBits"
1:33 "ChipBits"
1:36 "ChipBats"
1:38 "ChipRats"
1:41 "ChipVats"
1:44 "ChipFats"
1:47 "ChapFats"
2:08 "Do Math!"
4:06 "To 2 bit"
5:50 "3 Fails!"
16:11 "Please, "
16:13 "go watch"
16:16 "Stand-up"
16:19 "Maths on"
16:22 "TH-cam."
Let me know if I missed any!
Priceless! and I thought the meth joke was brilliant... =)
Wow!
I hid a message in this message.
@@apu_apustaja i can see a message tho-
Okay the "Tau < Pi" one is even more brilliant though because the original version without the bitflip says "Tau > Pi."
That bit sequence actually maping to "Do math!" and "Do meth!" is the type of small things that makes this channel amazing
Yeah, that's what makes this channel my favorite meth TH-camr.
ikr and i got to use my skills in reading binary i knew that i'll use it in the future
Entity 303? Its been a long time since I've seen that face.
Thank you for saving me from writing a line of python
😜😜
After seeing this video a few days ago I could not stop thinking about it, and even after learning the solution I was so amazed by how this could even be possible. I started learning some basics of Python this summer, and today I wrote some code that would allow prisoner 1 to determine which coin to flip and then prisoner 2 to determine where the key was based on the new arrangement. It was the most fulfilling thing I've coded so far and I'm grateful to have been introduced to this puzzle! Thanks for making such an inspiring video!
Inspiring!
Can you share a code? I would love to play around
I'm gonna have to do this myself...
Though honestly, I'm used to C++ lol, so I'll likely do it there
Matt Parker and I talk about the solution to the original puzzle on his channel: th-cam.com/video/as7Gkm7Y7h4/w-d-xo.html
This solution is _highly_ connected to Hamming error correction codes, so much so that doing this puzzle inspired me to make a video about them: th-cam.com/video/X8jsijhllIA/w-d-xo.html
cool
@ "cool" means that the speaker is comfortable with the statement and it's implications. "Cool!" means the speaker is comfortable and excited by the statement, this is possibly what VWLZ intended.
Haha I just came from the Hamming codes videos, so my mind was already primed to think about this in a certain way.
You really are an amazing teacher BTW, in case you haven't heard it enough from all your other fans.
It can be possible for n = 63; just assume n=64. As far as the flip coin is not the imaginary cell.
Got a bit confused, I didn’t get that the coin flip was mandatory from the phrasing “allows you to do” making the 3D version a cakewalk to solve
Why do mathematicians always set their puzzles in prisons?
Simple: min-maxing. You have maximum amount of time, minimum amount of distractions and maximum motivation to solve the puzzle correctly.
Assuming a spherical prison in a vacuum, of course.
And still people don't wanna go to prison.
I imagine mathematicians would flourish in prison.
Because existence is a prison and only mathematics can free you into non-existence ?
@@SacredGeometryWeb Stop explaining the plot of evangelion
A: "Wanna go to their wedding ?"
B: "Nah, I'm busy, I'll just send them present."
A: "There will be an extremely complicated math puzzle which related to higher dimension and computer science."
B: "Done, let's go."
LOL
Los jo uno 7
a: friend
b: 3Blue1Brown
@ he said that he heard this question at a wedding
net for mathematicians
This was impossibly good fun. Thanks for getting me involved!
*Me seeing Standup's vid and Blue's vid being uploaded at the same time* : Well heck
Tfw you have to pick between the same video from your favorite two channels
Wow it’s Matt!
Thanks for all the cool math videos!
@@lapiscarrot hello fellow gamer
It is amazing collab of my two favourite math-channels! Woo-hoo!
There's always the chance I just randomly choose the right square, blowing the warden's mind and my comrade's with sheer dumb luck
Its a 1% chance so good luck
@@arandomcommenter6759 1/64 chance actually
@@mikelap4244 well, at least it's better than 1 in 100
You could make it 1/32 by saying “if it’s on the bottom half, make coin 1 tails”. Not terrible odds honestly
@@mikelap4244 it can be better odds, for example, you can tell your partner that the key will be under a coin with heads, and if the key was placed under a tails coin, make it heads, and if its heads, flip another heads coin to tails. This could increase your chance of success by quite a bit.
Who would have known this would be the icebreaker to the puzzle in black ops 3, somebody give Jason a raise...
'The impossible chessboard puzzle' - Me: "Okay! You got this"
ALSO ME: *Stumbles in 2 square case*
Same lmao, I forgot that you *had* to flip a coin. So I was like "okay, if they're the same, it's the left square, if they're different, it's the right square, ez"
Video stopped, I rewatched the first minute trying to determine if you indeed HAD to turn a coin. It looked simple with having the choice not to, as CaTastrophy427 spelled out. Even when forced to flip a coin ... see my own comment for solution.
Same man 😑😂
1:03 before flip in ascii code: Tau > pi
1:03 after flip in ascii code: Tau < pi
1:25 in ascii code: 3b1b :)
???
@@bismajoyosumarto1237 If you break the bit stream into ASCii characters, that's what it makes
Is this a hint that Grant is on Steve's side rather than Matt's side?
And after the flip in the bottom right corner in 0:50 : "3b1b :("
This is honestly the first time I understand what that representation of a 4D cube is supposed to convey, it's not about somehow imagining how it would look like, it's just representing the relation of how the vertices are connected
Yup
It also is what one could look like. The flat cube, if you looked at it from the top down, is a way cubes can be positioned in 3 dimensions. The same applies for the 4d cube
the 3-D projection of the 4-D cube is brain-breaking. He demonstrates the 2-D projection of a 3-D cube and then constructs the 3-D projection of the 4-D cube, which of course prompts you to think about how that 3-D projection is expanded into 4-D which our puny brains can't do. ugh.
It somehow makes you “see” that the sides of a 4D cube are 8 3D cubes, just as the sides of 3D cube are 6 2D cubes (squares)
That's correct in the context of graph-theory and topology, but not geometry.
By definition, all sides of a 4D cube must have the same size as each other, regardless of how it looks when projected
Kn44 is love. kn44 is life.
That video blew my mind
Ayyy came from that video too! Black Ops Zombies are everywhere
This has to be it… insane videos btw
Never thought I would see a 3blue1brown video in a zombies video lol. Epic moment🎉
@@Nocturnal_Spectresuch a crazy unexpected crossover honestly
You heard this at a wedding? WHY??!
A weirdly math obsessed weird eastern european uncle of the groom gave him this riddle in order to be able to say “well *slaps knees* i gotta go, the missus needs to leave”
Mathematician weddings are just like that I guess
Grant Sanderson is definitely a master at making you feel these "Eureka" moments.
*aha! moments
Integarahl boi
Or “I’ve got it!” if you just want to speak English instead of Greek.
Eurgasms. If you will.
If you convert the arrangement of heads and tails at 0:49 into binary then translate it into english the readable text will say this: "3b1b :)"
@GoldBoy4 yes indeed! How did you find out?
Investigation I believe
Damn
@@pradyunmore6727 Probably the hint was that two of the rows were repeated, especially the two that represent 32, or space in ascii. That and a suspicion that youtubers like to leave easter eggs in their videos.
Nice easter egg
For those interested in this puzzle, this puzzle is also known as "The Devil's Chessboard." Of course there are multiple ways to attack this problem, but interestingly one solution you will find online also has a "computer science" flavor to it, similar to the error correction motivation as seen in this video. A possible solution to this puzzle is to label the the cells of the 8x8 board from 0 to 63 (we do this because we are putting our computer science hats on and start counting from 0). We then note the labels of each cell holding a coin with heads (or tails ... it doesn't matter) facing up. Convert each of those labels into its corresponding 6 bit integer (note that every cell on the board is in one to one correspondence with a binary string of length 6) and XOR all those integers ALONG WITH the label of the cell holding the secret key location. Now convert the result back into an integer which points to the cell holding the coin you should now flip. When your friend looks at the board, he/she will then (using the same labeling as you) XOR all the cells with heads facing up (or tail ... if that was what you used earlier). The final XOR result will be the cell location holding the key! For those not familiar with XORing two numbers, you basically need to line up the two 6-bit integers and look at each column where if you see two 1’s or two 0’s you write a 0 below and write 1 otherwise. Another interpretation is to write a 0 if the two bits are the same and write a 1 if the two bits are different. For example, 111000 XOR 010101 = 101101. You can play around with this strategy, by using a programming language. To XOR two numbers N and M you typically would need to type “N ^ M”.
To see the connection to computer science, check out an encryption technique called a "One Time Pad." It works exactly through XORs similar to the solution of this puzzle. Let's say you want to encrypt a message, M, to send your friend, and supposed it is N bits long. For a secure encryption, you and your friend should generate a (uniformly) random N bit key, K, beforehand. Then to generate your ciphertext, C, you should compute C = K XOR M (or M XOR K because XOR is commutative which is fairly straightforward to verify). Then your friend would compute C XOR K (or K XOR C) to reveal the message M! The reason this works is because K XOR K always equals 0 for any choice of K (in technical terms K is called the "inverse" of K) and 0 XOR C always equals C for any choice of C (in technical terms 0 is called the “identity”). In addition to being commutative, XOR is also associative. If these properties sound very familiar, it is because it is! XOR sounds kinda like a special addition where negative numbers are just the numbers themselves! With this in mind, I’ll use “+” to denote XOR for brevity. Putting this all together, we know that C = K + M and that when revealing your message your friend will compute C + K = K + C = K + (K + M) = 0 + M = M!
How does this relate to the Devil’s Chessboard? Well we can think of XORing all the cells with heads (I will ignore the situation where we use tails instead but the analysis is the same) as our “key” K and the key location being our message M. Formally, let K = X_1 + … + X_N where X_i is a cell with heads facing up and let M be the cell holding the key location. To generate our “ciphertext” which will be the cell holding the coin we flip, we perform as stated above C = K + M. The ingenuity of this solution lies in the fact that when your friend comes in and performs the XORing procedure stated above, he/she will compute C + K which as seen before will expose our message M! To see why this is case, note that either C will have been turned from tails to heads or turned from heads to tails. In the first case, your friend will see X_1, …, X_N, and C as heads and compute X_1 + … + X_N + C = K + C. In the second case, C will have flipped a coin that was previously heads (call this X_j), and your friend will then compute X_1 + … + X_(j-1) + X_(j+1) + … X_N = X_1 + … + X_(j-1) + 0 + X_(j+1) + … X_N = X_1 + … + X_(j-1) + (X_j + X_j) + X_(j+1) + … X_N = K + C. The second to last equality used the fact that X + X = 0 (mentioned above) and the last equality was due the commutative nature of XOR. As we see, no matter the case, your friend will ALWAYS compute K + C revealing the location of the key! This puzzle is indeed very cool, and surprisingly has another computer science angle that motivates not only ideas from coding theory but also cryptography!
Yeah definitely correct. I just wrote the solver to this problem using the exact same method of XOR encoding/decoding!
Use paragraphs pls
@@padraighill4558 Thanks for the feedback! I had written the post in a separate program and pasted it into youtube. I guess the formatting didn't carry through. There should now be new lines in the post delineating the different sections.
Wowza. You donated time and energy, thank you. I hope it is valuable to others.
I have a strong feeling that this solution is functionally equivalent to the one that's proposed in the other video-for a given configuration, the same coin gets flipped, and this is just a more CompSci way of describing it. That being said, i'm definitely too lazy to attempt to prove the equivalence :P
Kn44
Do you think the unsolved Giant cipher is going to be related? I’ve gotten interested in taking my shot at solving it
This is poetry.
The universe is built on subatomic kn-44s
"im doing meth"
police: jail time
computer scientists: interesting correction...
They send you to a...
...correctional facility.
... I'll see myself out.
You'll just escape jail by guessing the right key
This isn't meth. It's _mercury fulminate!_ *BOOM*
I'm currently reading a book on quantum computing and even though it's almost totally unrelated to that topic, this video made me realise why there's a need for code correction after calculation. Very amazing how separate branches of math and science intersect and help each other's understanding
What book are you reading? I would be interested to read it too
Not to be a dick but why are you reading a book on quantum computing if you didn't even know about error correction? It's a rhetorical question obviously and I see how quantum computing can be fascinating, but you'd probably appreciate qc more with a background of classical computing first.
I will say honestly it may seem unrelated on the outside, but reductions on sets of states is at the heart of computer science and one application of that general activity is error correction. Error correction does come more out of the EE or ECE field, to be sure, but the general idea is the crux of C.S. .
@@GothicKin Not to be a dick, but why don't you read properly before making a comment, he never said "I didn't know what error correction was," he said he now understands why after a quantum computation you have to do error correction to see the final and real result.
@@coleabrahams9331 It's actually more accurate to call it a booklet since it's less than 100 pages long and only covers the basics of quantum computing. Very much just an introduction. It's a Dutch book called "De quantumcomputer: een digitale revolutie op het punt van uitbreken" (The quantum computer: a digital revolution on the brink of breaking into scene) by George Van Hal. I doubt there are English versions of it, though.
3Blue1Brown uploaded: "The impossible chessboard puzzle"
Stand-up Maths uploaded: "The almost impossible chessboard puzzle"
Hmm...
True story, before I clicked on this vid, Iwas watching Standupmaths's video on generalized Fibonacci numbers, where the sequence both extends to negative numbers but allows for complex number inputs.
@@ganaraminukshuk0 saaaaame
It's the Parker Square of impossible chessboard puzzles
3b1b thumbnail is a 6x6 board, stand up maths is an 8x8 board ;)
Haha I commented this on Matt's vid! XD
Jason Blundell was here
It was at the 8:06 mark when I realized my chances of understanding the solution is next to nothing.
One of my favorite math teacher, and also a friend, died of cancer yesterday.
She used to love this channel.
She will never get to see this video.
She was a strict, funny and caring teacher.
Rest in peace Layla 😢🙏
She was more likely to die of COVID-19, so... not sure what follow-up statement I could make for that.
MeownaMeow sorry for your loss, at least she had good taste and must have seen much great content, much love
o7
f
F
Sorry my dude, I felt the same about monster group and Conway. Somebody has to solve it in his honor
For those who are intrested in the general case: The problem of how to encode data with a limited number of bitflips was treated in 1989 in the paper "Coding for write-efficient memory" by Ahlswede and Zhang.
lock picking lawyer: who needs keys?
Number one is binding... nice click out of 2
Hi, this is the lock picking lawyer and what I'm going to show you today is how to pick this jail lock with maths.
@@volcanking662 Using the pick that Bosnianbill and I made.
Meta
Lol
I can confidentally say that we're all here to figure out KN-44 for the impossible EE on BO3
fr
Only Grant would discuss this problem at a wedding 😂
but a discussion needs 2+ people... I wonder what wedding has this many fun nerds (I say nerds as a compliment and not an insult)
I was surprised as well, but then I thought it's ok too. I've been into weddings where people talk about computers and AI a lot. That's because I have my friends who share common knowledge in this domain. So it's normal for Grant to talk about Maths in the wedding.
(Btw talking about technology doesn't look weird enough, but discussing Maths problems...)
@@pvic6959 when you add fun as a prefix, we take it as a compliment. You don't need to clarify 😉
@@stv3qbhxjnmmqbw835 Just wanted to be clear! I consider myself one too :P
Even worse, it was his own wedding. :-)
I have been eagerly awaiting a new 3B1B video and I just want you to know that I dropped everything to watch this.
hi timtom
same!
hi I didnt know you watched 3b1b
weird flex but ok
One of the best math channels out there. Change my mind
I don't think anyone can do so given he certainly _is_ *one of the* best math channels
Also my personal favourite
*Steven Crowder has joined the chat*
you mean the best
Definitely one of the best. Although I do respect and appreciate Gilbert Strang equally ♥️
Random Dude I hope not
KN-44 gang rise up!! @3blue1brown get on this EE hunt and help us solve it!
From the prisoner puzzle, the rule says you can flip one coin but doesn’t say that you have to flip a coin. So I am wondering, if “not flipping coin” is an option, I feel the 3d model will work since you can always stick too “key = the less number of head/tail” for example: 001,110 both tell the key is in the right-most slot. Of course. This is based on “if not flipping a coin is a possible option”
Fun fact: The 1's and 0's at 2:20 are not random. They're the ASCII representation of "Do math!"; each row of 8 bits is one character of the message.
I think most people who watch this channel are familiar with that
I think we all knew that, from the ECC example that changes the 'a' to an 'e' by adding 4.
Why would you think most watching are familiar with this?
This is far from universal knowledge, and I would guess it is only a small minority who do.
@oH well,lord! hence why the first column is all 0s
I knew that from the amazing game The Guides: Axiom. Look it up on Play. It's pretty amazing!
"Error correction is universally sexy!" Needs to be made into a t-shirt.
r\woosh
@@tuneboyz5634 r//
You from U.S?
"Not everyone is as interested in symmetrical ways to paint a 64-dimensional cube as I am..." - nonsense!
3B1B please explain not only Hamming codes (I already know those) but also Reed-Solomon and LDPC codes (I get overwhelmed by unknown math involved). I actually want to be able to implement them. Not just implement, but understand how and why they work and play with them. I looked at source code of Reed-Solomon from the ZXing library and although it works, I couldn't figure out how it work.
(Without these complex strategies)
I think it would be really funny if the warden put every coin on heads except for tails on the key square so you can’t flip it because then they’re all heads and flipping another one would give you like a 50/50
That's why you always have a null bit ;)
All the cod black ops 3 fans will watch this 20x times for the impossible Easter egg
When you first stated the problem, I understood that you "may" (instead of "must") flip one coin.
The possibility of not flipping any coin definitely changes the problem. I know, for example, that it would be possible to solve for 3 squares. Have you given any thought to this variant of the problem?
It'll prob be way easier (for the prisoners)
The way it's stated does indeed leave room for not flipping any coin.
For this variation, it is possible for any number of squares that is a power of 2 or 1 less than a power of 2, but it is impossible for all other cases. In case of 3 squares it was possible since it is 1 less than 4 which is a power of 2. To find how o solve for squares 1 less than a power of 2 you just use the same strategy for solution for powers of 2, but assign a binary number to not flipping any coin.
Grant: "Should I make a video about x?"
Everyone: "Yes, do that, please."
Isnt that the Imperial Fists logo from Warhammer 40k? With a rainbow background for some reason...?
@@azertykeys9011, no, the Imperial Fists' logo has an armoured gauntlet hand.
The raised fist has been a symbol of revolt throughout history. In modern times this symbol particularly represents civil rights movements and resistance to discrimination.
Here it's integrated with the rainbow flag which represents sexualities that are discriminated against.
@@JNCressey Understandable, have a nice day
You know what else is universally sexy?
This channel
Out here solving puzzles you didn’t know existed
> color the vertices of a cube
"It's all graphs?"
"Always has been"
Prisoner 1 **Confidently walks in, flips a coin, leaves.**
Warden **turns board 180 degrees**
Prisoner 2 **Walks in, takes a guess, no key under the coin**
**shocked pikachu face**
He will be able to know it's flipped by looking at the color of a corner
@@TheGrenvil That would only tell you it's been rotated by either +/- 90 degrees
the scenario assumed the warden would attempt to interfere with you *before* you do your bit flipping, because he knows your strategy. If the warden is allowed to interfere with you *after* your bit flipping, he could just flip any coin once and change the answer.
Your scenario is smart, but any interference would do the same thing, render it entirely impossible.
Well, it's a chess board, most of chessboards are numbered, so it's not a big deal.
Use an encoding where orientation doesn't matter... just in case
0:04 don't you hate when you walk into a room and a chessboard just sit there
Actually, no I don't. Maybe I'm just weird like that.
@@stechuskaktus8318Me too…
I do hate it
Surprisingly, because your shorts are very calm in general (voice and visual wise), therefore, I am much more likely to watch the whole video. Noticed this several times.
"... But reliable data transmission? C'mon. I think we can all agree that's universally sexy" I'm in love with this man
Skite Innit is bringing huge traffic to this video for B03 zombies
I'm not in the field of math or IT, so the error correction always looked to me like magic. I would be happy to watch you explaining how it really works.
I've never played chess, is it anything like Black Ops 3?
LMAOO
2:23
*Him:* How do I solve this problem?
*Me:* Just do meth!
*Him:* WHAT
"I'm only gonna flip the one" - with warm, dirty fingers and touch the coin for a long time.
399 IQ
To answer your question of why mathematicians set their puzzles in prison, the only way to force people to play through a challenging puzzle is to remove every other possible option besides solving the puzzle. In the case of prisons, you either solve the puzzle or do nothing
July 5, 2020: Grant renames his channel to “Universally Sexy”.
Nah, July ninth would be the way to go.
tru tho
@@johnclever8813 that's 9/7
Better make a different channel with this name.
I'm afraid 64^(2^64) is not a size of a haystack when you're looking for a needle; rather a size of the whole history of the multiverse when you're looking for a single moment of a single gluon fluctuation
Anyone else here after watching the Skite Innit Impossible Easter Egg video??
You’ll be happy to know that flipping that one bit actually did turn math into meth in most binary to text encoding schemes
Yes, I was very happy to note that the table of 0's and 1's was the ASCII representation of "Do math!" and that the single bit flip illustrated actually turned the a into an e
I noticed that and I howled in laughter at 5 in the morning. Grant has the sharpest humour, tying in chessboards, bit flipping, math and meth in one 3 second punchline
@@meghanto Yeah, I didn't realize that and had to look back when I saw this comment. Additionally, once the warden realizes that the prisoners have come up with a foolproof solution, the warden can at least arrange the coins to spell out "F*** YOU" which is also exactly 8 characters.
YES GRANT, WE WANT MORE VIDEOS ...ON ANYTHING! Doesn’t matter lol
No, more videos in the same amound of time will mean lower quality videos and we DON'T want that
Watching this at 5AM wasn't the best idea of my life
It felt like watching a Japanese lesson teached in Russian
But it was still amazingly interesting !
I'm sorry for the oncoming traffic of call of duty zombies fans, but we're currently undergoing a breakthrough in easteregg hunting
Is this the impossible Easter egg
yes
No
I’m a simple man. I see a 3B1B video, I click like.
Maybe we are overthinking and the solution is just like putting the coin on its side
Yeah, like just turn the coin 90 deg
This solution is quantum.
I bet this is cheating
Of course, in a math channel where this relates to error correction, its about flipping the coin on its side, just like you can flip a bit on its side
@@iliakatsteryou dont know if it works if you never tried it!
Okay, I understood the Introduction. Smooth sailing so far.
but how does this solve bo3 zombies
This video is not about “bo3” zombiesd
@@palmossi yeah thats what they want you to think
@@ermkindofcringe9401 ?
@@ermkindofcringe9401 who’s “they”
How to beat:
>tell inmate "if i flip a coin, the square under has the key"
>inmate guesses correctly
>we both get out
I'm so confused why no one is saying this
This was literally the first thing I thought.
🤦♂️
@@palmossi 1:12 "the two of you can strategize ahead of time" and the strategy is to say "if i flip a coin, the square under has the key". warden cant do nothing about that
...because neither of you know what the board will look like when you start. How prisoner 2 can tell which one was flipped when they've never seen the board is the problem we're trying to solve.
Your dinner conversations must be very intriguing...
And the weddings he attends. Probably doesn't even bother to RSVP unless both spouses have at least a master's in math.
2:43 why can't I do meth and math.
In the case of 3 coins there’s a simpler solution that doesn’t require math but it definitely doesn’t work for any other setup. “The key is under the unique coin” no matter what the initial setup is you can always make exactly two coins match which tells prisoner 2 that the unmatched coin has the key. This only works if you aren’t forced to flip a coin though
kn44
I saw a short with no solution, so I watched an 18 min video for the solution, which sends me to an another video for the solution.
Nice 👍🏾
12:45
A (maybe) different proof:
Let #(B) denote the number of blue vertices. Similarly for #(G) and #(R).
#(BB) denote the number of blue-blue edges. Similarly for #(BG), #(BR), etc.
According to the rule, the 3 edges at any blue vertex are blue-blue (BB), blue-green (BG) and blue-red (BR).
Thus each blue vertex MUST serve as the end of ONE and ONLY ONE blue-green edge.
Thus #(B) = #(BG).
Similarly, #(G) = #(BG). As a result #(B) = #(G).
Similarly, #(B) = #(G) = #(R).
Or just by symmetry, since there is no preferred colour
Q: Why do mathematicians alwys set their puzzles in prisons?
A: An hommage to Alan Turing.
:(
If that was the case, you would still be in jail after finding key.
Alan Turing didn't go to prison. For the "crime" of being gay, he was pressured into undergoing "chemical castration" to avoid prison time. This treatment undoubtedly contributed to his depression and suicide. Not sure why so many people liked your "joke" - it's pretty shit.
@@octowuss1888 You're that guy who is never invited to weddings, right?
Grant Sanderson talks about more intelligent thing at someone's wedding than me at school
Haha true...
I love the answer someone gave where he said wait 8 years, flip the coin where the key is. Prisoner two comes in the room and sees dust on all the coins except 1. He knows that was the coin that was flipped and that’s where the key is. Took 8 years for freedom but when you’re serving life, that’s a drop in the bucket.
In each of your videos, every doubt I come up with in the earlier parts of the video are explained in the later parts... That's impressive!
FINALLY I MISS U
Its wild how i saw this on my shorts then I saw that black ops 3 zombies easter egg just found out they have to use this method to progress the easter egg
Wow fantastic video for sure! Many of the puzzles or so called IQ test type math problems are so interesting to try!
easy. pick up the coin with the key under it, open the compartment, take out the key, close the compartment, set the coin back down on the other side, and set they key on the chessboard.
A gorgeous illustration of Maths as *pattern making* .
"A mathematician, like a painter or a poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas." - G H. Hardy
@1:30 yeah, totally, that's how any wedding conversations i had go.
Lol i thought the same
I'm wondering if doing math on the drive home can be classified as driving under the influence
Math
Not even once
After all, it's one slight error away from meth.
Love the high-D visualisation. My first though on the puzzle was also Hamming codes, but I couldn't get my head around the application to this particular problem. As a visualisation, it makes SOOOO much more sense! I'd love to see one that's more dedicated to Hamming, I'd love to see how you apply your visualisations to the question of overall packet length vs. number of correctable bits.
If asked to color the 4th dimensional cube's vertices I never would have thought "Put the colors on a 3d projection's diagonals" would have been the answer. It seems way to elegant and perfect to have been the answer. That's crazy.
I like that coloring the hypercube is basically color the diagonals. Elegant.
black ops 3 impossible easter egg hypercube brought me here
This is a really good puzzle. The choice of a chessboard is significant because it has 64 squares. But to be a truly great puzzle, all the relevant properties of a chessboard should be significant, not just the number of squares. A chessboard can be rotated 180 degrees and it will look the same. If Prisoner 2 is led into the room and he notices that the room is 180-degree symmetrical with two entrance doors, and it also so happens that the arrangement of heads and tails is similarly symmetrical (ie a palindrome when written as a sequence), then he only has a 50% chance, no matter what he has previously discussed with Prisoner 1. There is absolutely no way to know whether he is looking at the board from the same side as Prisoner 1 was. So it's a choice between square x , and square (63-x), and those can't be the same square. So to solve the problem, Prisoner 1 would have to never leave a palindrome. He can certainly avoid leaving a palindrome, but that removes some of his options, and he doesn't have any spare options. Therefore the problem, as presented, really is impossible, after all.
Chessboards are actually often annotated with letters and numbers along the sides.
I can hardly find appropriate words to describe the quality of your work on TH-cam... It's just astonishing and breathtaking ! You explain beautifully clearly and concretely ideas I would never have thought of myself and it just opens up to me a new way to see things, in math, science or more generally in real life ! I sincerely thank you for inviting me so cheerfully in such wonderful mental experiments !
Dont know why I watched all of this while not understanding a word of it.
Thanks for sharing this puzzle-it's a really interesting challenge! I enjoyed the opportunity to think through it.
However, I have to admit I was a bit surprised when you directed viewers to another channel for the solution. I personally prefer to keep everything within your content, as I’ve always found your videos valuable, and I wasn’t particularly interested in going to another TH-camr’s channel.
So I solved it myself.
Thanks again for introducing me to this problem!
Loved this puzzle. I came up with two related puzzles (both solvable).
#1: Same goal and constraints, but the board is 6 x 6 with a D6 in each square. To communicate the special square to your partner, you must advance just one die by just one pip. (Advancing a 6 means bringing it back to 1). This can also be done with any board where the number of squares is a power of the number of possible states for each square. Advancing one square by one state (with wrap-around) is all you need.
#2: The warden is going to give you a row of stacks of coins with the tiny key hidden beneath one of the stacks. You do not know in advance how many stacks there will be in this row or how high each stack will be. You have to communicate to your partner which stack hides the key by just placing a single additional coin on one of the stacks. You can discuss strategy in advance, but warden gets to listen and try to thwart.
Hey :3
bruh
@@NPCooking69 bruh
Papi
3b1b standupmaths and flammable maths collab when
@@non-inertialobserver946 dunno m8
It's seriously awesome to see a new video by you! I know it will be fascinating and make me think. Thank you for your wonderful work :D
2:30 there is no error!
I fucking choke on my food when I read the comment😂
who's here after Skites vid🤓☝🏽✨❤️
I loved Matt’s description of the puzzle as coming up with the worst error correcting code ever. I would love to see another video on it.
Nobody:
Grant: “do meth!”
You just have to wait until all coins get covered by dust and flip the one where the key is