The impossible chessboard puzzle
Vložit
- čas přidán 4. 05. 2024
- An information puzzle with an interesting twist
Solution on Stand-up Maths: • The almost impossible ...
Help fund future projects: / 3blue1brown
An equally valuable form of support is to simply share some of the videos.
Special thanks to these supporters: 3b1b.co/chess-thanks
Home page: www.3blue1brown.com
Thanks to these viewers for their contributions to translations
Hebrew: Omer Tuchfeld
------------------
0:00 Introduction
3:58 Visualizing the two-square case
5:46 Visualizing the three-square case
12:19 Proof that it's impossible
16:22 Explicit painting of the hypercube
------------------
Thanks to everyone who endured me probing them with this puzzle and provided helpful discussion, especially Cam Christensen, Matt Parker, and Mike Sklar. Mike, by the way, deserves credit for coming up with the particularly clean way to see that it's impossible when n is not a power of 2.
These animations are largely made using manim, a scrappy open-source python library: github.com/3b1b/manim
If you want to check it out, I feel compelled to warn you that it's not the most well-documented tool, and it has many other quirks you might expect in a library someone wrote with only their own use in mind.
Music by Vincent Rubinetti.
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
open.spotify.com/album/1dVyjw...
If you want to contribute translated subtitles or to help review those that have already been made by others and need approval, you can click the gear icon in the video and go to subtitles/cc, then "add subtitles/cc". I really appreciate those who do this, as it helps make the lessons accessible to more people.
------------------
3blue1brown is a channel about animating math, in all senses of the word animate. And you know the drill with CZcams, if you want to stay posted on new videos, subscribe: 3b1b.co/subscribe
Various social media stuffs:
Website: www.3blue1brown.com
Twitter: / 3blue1brown
Reddit: / 3blue1brown
Instagram: / 3blue1brown_animations
Patreon: / 3blue1brown
Facebook: / 3blue1brown
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?
@@TheAznCoderPro 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.
@@TheAznCoderPro he meant that if your mom is 56 years old and your car is red then how tall is your father?
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
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 "CZcams."
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."
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
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."
ok
LOL
Los jo uno 7
a: friend
b: 3Blue1Brown
@COVID-19 to COVID-20 PRO then Max he said that he heard this question at a wedding
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 CZcamsr.
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
😜😜
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.
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 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!
@@lapiscarrot3557 hello fellow gamer
ooooh thats why you both uploaded the video about this puzzle at the same time
'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 😑😂
It's possible with two square case:
If key is under left square and left coin is heads: flip right coin; left coin = heads
If key is under left square and left coin is tails: flip left coin; left coin = heads
If key is under right square and left coin is heads: flip left coin; left coin = tails
If key is under right square and left coin is tails: flip right coin; left coin = tails
If coin is heads, the key is under the left square, otherwise, the key is under the right square
This doesn't work for more than 2 squares because a coin can only encode 2 possible states
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
(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
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.
"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*
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.
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”
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
Matt Parker and I talk about the solution to the original puzzle on his channel: czcams.com/video/as7Gkm7Y7h4/video.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: czcams.com/video/X8jsijhllIA/video.html
cool
@Man ༒ᏝØЯĐ 山ΛSξξꪑ ꪑΛᏝᖽᐸ Øf 山ΛNSᏝΞY ꪑΛηηØЯ ༒ اسلام ࿐ "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
> color the vertices of a cube
"It's all graphs?"
"Always has been"
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
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
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.
I can hardly find appropriate words to describe the quality of your work on CZcams... 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 !
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.
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.
@@carloscuello6634 Using the pick that Bosnianbill and I made.
Meta
Lol
The visuals in your videos vastly help me get a grasp on the concept being described.
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.
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!
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.
Love the puzzle and the video!! Here is a fun variant of the puzzle. The warden leaves 91 coins (perhaps in a 7x13 array) randomly flipped. They hide a red key and a blue key under two squares of a standard 8x8 chess board. (Although they could both be in the same square.) The first player has to make exactly two flips (which could be flipping the same coin twice), and the second player has to be able to determine the location of the red key and the blue key (not just the pair of squares but identifying which key is where). Enjoy!
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.
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
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.
This was a delightful video. One fun thing I noticed while playing with trying to color cubes is that the constraint that we can get to each color with one coin flip only introduces constraints between corners with same parity (same parity of 1s in their coordinates). This means that any solution can be formed from independent solutions on the even and odd corners. This also makes reasoning through the 3D case easier because you don't have to distract yourself with colors on half of the vertices. And it makes for an even simpler coloring problem: In 3D, you are looking for a coloring of the tetrahedron formed from, say, even corners of the cube, and with opposite corners connected. You obviously can't 3-color the corners of that tetrahedron. In higher dimensions, the polytope you get by taking the even corners, and connecting them across cube faces is harder to visualize, but it is interesting to know that solving the original puzzle is the same as finding a coloring of the vertices of that polytope.
"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.
Hello Grant! This was very relaxing especially during these times. I wanted to ask you if you would be doing videos on foundations of mathematics like mathematical logic, axiomatic set theory etc. It would truly be a gem to understand Godel's incompleteness theorems from your unique perspective.
These videos are super cool in helping me come up with puzzle designs in games. Ty so much for working on cool content and making it digestible
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
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
and free
*Steven Crowder has joined the chat*
you mean the best
Definitely one of the best. Although I do respect and appreciate Gilbert Strang equally ♥️
Thank you very much Grant for this fascinating journey, please make more videos about recreational maths puzzles! :D
How to beat:
>tell inmate "if i flip a coin, the square under has the key"
>inmate guesses correctly
>we both get out
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
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.
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
Maybe we are overthinking and the solution is just like putting the coin on its side
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 only gonna flip the one" - with warm, dirty fingers and touch the coin for a long time.
399 IQ
Interesting follow-up question I thought of:
It seems to be that, using the modulo encoding strategy described in the two- and three-coin case that is expanded on in Matt's video, that the probability of success with that strategy is always 75%, because there are always two candidate coins that one could flip to encode the desired result and if they fall in one out of their four configurable states, we're screwed. For example, in the three-coin case, if we need to add 2, we could either flip the 2-coin to a 1 (heads, if heads is encoded to 1) or flip the 1-coin to a 0 (tails); the only way to fail at this is if the 2-coin is already heads and the 1-coin is already tails, which has a random probability of 1/4. It seems as though this logic doesn't depend on the number of coins because there's always two ways to get to any number modulo N either by adding or subtracting an element of Z/nZ (unless maybe we need to add n/2, in which case either adding or subtracting will work, which seems to suggest this strategy will always succeed in that "lucky" case, but I'm not sure), so it seems like our odds are always 75% with this strategy. But is it possible to come up with a strategy that, in general, has a *more* than 75% of succeeding? As we've shown, 100% is impossible if the number of coins is not a power of 2, but maybe if we remove the restriction that the warden is evil and knows our strategy and is instead "neutral" and assigns a board configuration randomly, it could be possible to come up with a strategy that has at least a higher chance of winning than, say, Russian roulette (as mentioned in Matt's video).
Oh no
2:30 there is no error!
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
You know what else is universally sexy?
This channel
2:23
*Him:* How do I solve this problem?
*Me:* Just do meth!
*Him:* WHAT
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 !
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
This was very intuitive to me as a computer scientist. I immediately jumped to ECC and hamming codes and every step after was pretty straightforward to understand. On my own I may not have come up with the colouring idea though and would have instead gone with another terminology like grouping but colour is far more intuitively elegant.
I feel like I’m walk up many small steps... you make it very easy to ascend. I appreciate you ✌️❤️
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?
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.
The way that the nodes were arranged on these Qn graphs reminded me of some undergrad research I participated in where we investigated F-WORM colorings. An F-WORM coloring is a coloring of a graph G in which there does not exist a copy of subgraph F which is either rainbow (every node is different) or monochromatic (every node is the same). Hence, F-W(ith)O(ut)R(ainbow or)M(onochromatic). In our team’s investigations, I was especially fascinated with Sn+1-WORM colorings of Qn; i.e., colorings of hypercubes such that any node and its neighbors wasn’t rainbow or monochromatic, and exactly the kind shown in this video. The minimum number of colors is trivial for bipartite graphs such as Qn; it’s always 2. We were mostly interested in the maximum number of colors for a valid F-WORM coloring. The research was inconclusive on this particular front (we weren’t able to prove a lowest upper bound for any more than Q4), but it was still interesting nevertheless.
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 👍🏾
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.
@1:30 yeah, totally, that's how any wedding conversations i had go.
Lol i thought the same
If you remove the constraint that prisoner 1 MUST flip a coin and you change the rule that he CAN flip a coin, there are many more board sizes that will have a solution.
For example, a chessboard of size 3 will have a solution (optionally flip one coin so that you end with 2heads/1tails or 2tails/1heads indicating that the key is under the single head or single tail.
Using coloring, this would mean that you do not need all three RGB colors to be adjacent to every node but only 2 of them as you already have one color you are standing on and you are allowed not to move. This means that, for example, R nodes would need only G and B neighbours. And it is simple to demonstrate that if the rule changes from MUST to CAN flip a coin, the puzzle has solutions for many more boards!
Excellent video, just fantastic !
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). I'd guess from your video 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.
Great video. You are a master at giving those "Aha!" moments. I would love to see you explain hamming codes. It sounded like an interesting topic.
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
16:47 I love how you are displaying a 4D object by using a 3D rendering of it, but you have to do that on a 2D surface.
Now I wonder if there would be a way to render a 5D object in a few decades when we have access to truely 3D Holograms. It would still really mess with our heads and it wouldn't really work since we basically already see a 2D image anyway. Our brain just does a really good job at faking depth (Having a second eye helps though too).
And yes I spent way too long trying to think of a way to render a Cube on a Line. Sadly it doesn't even make sense...
And we're using our 1D brains to understand that.
Please do make a video on hamming codes... As a person doing IT who had that subject a few months ago, I would love to see how you explain it and get a whole new level of understanding.
When I heard the puzzle description, I would have thought prisoner 1 had the choice to flip a coin or not. However, if the coloring requires all neighbors to be different, this is equivalent to saying that prisoner 1 is forced to flip a coin. I thought I would add this as a clarification. Otherwise, there would be for example a possible strategy with a size-3 board.
I guess the other problem would also be interesting. In that other problem, each vertex has n neighbors, but the vertex itself must also be considered in the coloring, i.e. the n colors must be distributed among n+1 vertices.
Edit: confirmed. It is stated in the solution video that prisoner 1 has to flip a coin.
I like Matt Parker's video that uses a prison device, and he went through and introduced his students/participants and why each one was in Math Prison. (I guess in the UK he would call it "Maths Prisoun".)
The first one of course was "divided by zero". Another I recall was "refused to take a position on pi vs tau."
I so did not understand this when you released this video, but after watching the Hamming Codes video you uploaded today this is suddenly understandable.
Thank you :D
You heard this at a wedding? WHY??!
FINALLY I MISS U
I'd definitely be interested to see how the amount of information required to encode error correction compares with the amount of info in the base message (like is 6 bits for a 64 bit message typical? that seems 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.
Chessboards are actually often annotated with letters and numbers along the sides.
I would love a video on how Hamming Codes refer back to this puzzle, these kinds of puzzles are super fun to watch and think through!
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 a simple man. I see a 3B1B video, I click like.
Yes please! I would love to see a video on the puzzle's relation to error correction
This channel is the best! Please keep making this awesome content!
For the 3 piece chessboard I'd go with the odd one out strategy. Basically since I know the location of the key I'd flip a coin such that the coin on the key space is different from the ones surrounding it. It wouldn't work for any board greater than 3 though :(
it wouldn't even work for 3 though
what about the case
HHT, key = 3
HTH, key = 1
and so many more...
For HTH the key would be 2?@@colecancode
@@colecancodeThought I replied to this but my bad, for HHT and key being 3 it can be solved by flipping the T key (if flipping is mandatory), indicating that since all the coins are the same, the key has to be the one that I flipped. For HTH and the key being one, if I turn the last H to become a tail it becomes HTT indicating that the key is the odd one out, which is the first head, so key = 1
Sounds like a really cool puzzle. Exactly the kind of thing I could spend hours thinking about. Unfortunately I didn’t get far enough into math to know what mod 3 is or to understand how flipping one coin adds or subtracts while flipping another does not.
So by adding the coins, he's saying add their 1 or 0 value (he calls heads 1 and tails 0 in the video, but you could reverse it and the puzzle works the same). Then the sum is the number of the tile which has the key (we're assuming the tiles are numbered from 0, so the first is 0, second is 1, last is 2). e.g. if we had 3 tiles then if they were all 0, that would be 0+0+0=0 which means the coin is under the first tile. 1+0+1=2 would mean the coin is under the last tile. And so on.
Modulus (mod) is pretty simple, it's basically the remainder if you remember that from fractions. So for instance, 5 / 3 is the same as 1 and 2/5, aka 1+2/5. 2 is the remainder/modulus because after you've divided there's still 2 parts left that aren't whole.
I'm definitely interested, especially if you incorporate quantum error correction codes. They have nice topological properties as well.
Okay, I understood the Introduction. Smooth sailing so far.
If i was smart enough to solve this puzzle i wouldn't be in prison.
Love this kinda content!
I'm gonna try to solve it for sure before watching the solution video
Man, the animations are amazing!
The transitions in different dimensions, Even the detail of word colouring in different colours.
grant uploads after a month.
me: click
grant: supposs you are in a room...
me: immersed
As someone who's fairly literate when it comes to mathematics, this was impenetrable. Reminds me of my undergraduate stats courses where the lecturer also liked to break things down into binary concepts; as if this helped with the understanding of the concepts behind DoE. Transforming heads and tails to 1's an 0's is easy to grasp, but then imediately jumping to cooridinates on a unit square requires some mental origami, but before the swan in processed; we're at a 3D unit cube with a colour bar. Add the sneak peak of the neurons that are to be transformed into a 4D cube, then attention is lost.
Wait, I just realized how closely related this is to the hat game I literally just learned this semester in Linear Algebra! That's so cool! Neat to find new ways to think about problems, and I guess new problems to think about those techniques, in this case
I think you should introduce algorithms in one of your videos. Graph coloring is an NP Complete problem, and it's equivalent to all other NP Complete problems such as picking a subset of sets that don't share any members. I would love to see how you visualize that.
2:43 why can't I do meth and math.
Hey :3
bruh
@@NPCooking69 bruh
Papi
3b1b standupmaths and flammable maths collab when
@@non-inertialobserver946 dunno m8
I just want to say your shorts are amazing at doing exactly what I think shorts are best at, getting me to click to the actual video because I'm genuinely curious about the topic. Instead of endlessly scrolling shorts I click off to something more meaningful, and I get to preview the video more than just the thumbnail and title.
I came up with a way: to decode a bitstring: split it in two halves, xor the two halves, decode the xor result recursively, then if the fist half has sum-parity 0, return what we got when decoding the xor result, else add onto it the half bitstring length.
How to flip to any arbitrary target key: split the input string in two halves, xor them. Recursively check how to change the xor result to decode into the key with its first bit removed. Then we know which bit needs to be flipped, but not in which half. Then determine if the input string decodes to the upper or lower half of label space and whether the target key is in the upper or lower. If they both agree, we do the bit flip in the second half, else in the first half.
import math
def parity(code):
return sum(code)%2
def xor(code1, code2):
return [c1^c2 for c1, c2 in zip(code1, code2)]
def flip_which_(code, target_label):
assert 2**len(target_label)==len(code)
n = len(code)
if n==1:
return 0
part1 = code[:n//2]
part2 = code[n//2:]
xored = xor(part1, part2)
sub_flip_pos = flip_which_(xored, target_label[1:])
ishigh = parity(part1)
wanthigh = target_label[0]
if ishigh == wanthigh:
return sub_flip_pos + n//2
else:
return sub_flip_pos
def decode_(code):
n = len(code)
if n==1:
return []
part1 = code[:n//2]
part2 = code[n//2:]
xored = xor(part1, part2)
ishigh = parity(part1)
sub_label = decode_(xored)
if ishigh:
return [1, *sub_label]
else:
return [0, *sub_label]
def decode(code):
return label_to_num(decode_(code))
def adjust(code, target_num):
label_bits = int(math.log2(len(code)))
label = num_to_label(target_num, label_bits)
i = flip_which_(code, label)
new_code = [*code]
new_code[i] = 1-new_code[i]
return new_code
def num_to_label(num, bits):
if bits == 0:
return []
return [*num_to_label(num//2, bits-1), num%2]
def label_to_num(label):
if len(label)==0:
return 0
return label_to_num(label[:-1])*2+label[-1]
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