YOU HAVE NO IDEA how much I needed this. Parity becomes very relevant when solving cubes blindfolded, or when trying to come up with methods for different cubes. I had a solid understanding of HOW it works but not WHY it happens. Thanks for this
There is really good sequencing/story-telling throughout this video, from the history of the 15 puzzle, leading into the Rubik's cube, then going into the proof. Not only have you explained the proofs well, but you've given context to an otherwise abstract concept in mathematics. Gj!
After learning how to solve the Rubik's cube when I was 17, I learned about parity/parody such as this, and found that this concept is easier to understand than it is to explain it. Peers would scramble my cube and accidentally twist a corner piece and then halfway through the solve I would notice the problem and often the people watching would think I was cheating by twisting the piece back, thereby causing the issue of it being harder to explain than to understand. People will often be unwilling to listen when they think you're cheating them. Bonus fact: The famous melting cube that's popular on shirts, and is even worn by Sheldon Cooper in "The Big Bang Theory", is also in parity, unsolvable without rearranging pieces or twisting a corner. (Aside from the fact that you can't turn the sides on the melting cube lol)
Great video. Completely explains the 15 puzzle. However, with Rubik's cube the parity is more complex. Interesting fact that most people forget about the exact position of the middle cubicle, which can be observed if you make a little colored dot toward the neighboring four colors on each side of the center cubicle. If you take that into consideration also when solving the cube, it becomes harder to solve. You can prank your speedcuber friend with this trick. The parity rule stands for the middle cubicles as well, although you cannot notice it unless you mark them.
A more interesting example is the corner twists on the rubik's cube. If a single corner is twisted (to either of the other orientations), then the cube is unsolvable. This one can't simply be solved with the parity (sign) of permutations, because the single corner twist actually moves you between 3 separate orbits of the scrambles under the action of the group generated by allowed moves, rather than just 2 orbits (which are solved with the "modulo 2" type of invariant created by the sign of permutations). Instead you need to use some sort of modulo 3 invariant of the rubik's cube. The easiest way to do it that I can think of is to mark the "up" face and "down" face with arrows coming up and down from the 4 corner locations, respectively. Then additionally, mark each corner piece with an arrow, initially in the same place as the arrows fixed to the up and down faces, but these are fixed to the pieces. Then keep track of the total clockwise angle that the corner pieces' arrows make relative to the arrow fixed on the same corner location - this total angle can be thought of as a multiple of 120 degrees, modulo 360 degrees (or divide out the 120 degrees, and get a number modulo 3). If you make a move rotating the up or down face, then the corner pieces' orientations don't change relative to the arrow marking the default orientation in that location, so the total angle is unchanged. If you make a move rotating any of the other 4 faces clockwise by a quarter turn, then from the perspective of looking at this face: the top left corner moves to the top right, and rotates 120 degrees clockwise relative to the default (upwards) orientation at the new location. The top right corner moves to the bottom right, and rotates 240 degrees clockwise relative to the default (downwards) orientation at the new location. Similarly, the bottom right corner goes to the bottom left and rotates 120 degrees clockwise, and the bottom left corner goes to the top left and rotates 240 degrees clockwise. Overall, the total of the angles changes by 1 + 2 + 1 + 2 = 6 = 0 (modulo 3) lots of 120 degrees. Any other rotation of these faces can be made up out of clockwise quarter turns, so this shows that every move fixes the total relative orientation of the corner pieces. As a side note, there is one more parity of rubik's cubes, which is the edge orientations. If you flip one edge, then it becomes unsolvable. This is a sort of modulo 2 parity, but you can solve it even more easily than the corner twists by doing the same sort of orientation colouring as above. It's hard to describe the colouring, but it's a very natural symmetric colouring of edge orientations of a cube: on every face, the default orientation of any edge should be different to (not on the same face as) an adjacent edge. This makes a consistent colouring, which you can try yourself with a cube, but I'm not going to prove that it's consistent. Then any move you can make with a rubiks cube will flip the orientation (relative to the defaults) of all 4 edges that move, and hence preserve the modulo 2 total orientation of the edges.
I'm not entirely sure I understand your edge-orientation invariant. I've discovered my own, but yours sounds more simply stated than mine even if I don't understand it. If you'd be willing to explain further, that would be cool. I put my own invariant below. Mine works the following way (note that I'm using traditional rubik's cube coloring, with opposite color pairs being yellow/white, red/orange, and blue/green): 1) Each edge piece has two stickers, but give each piece a "primary sticker" in the following way: if one of the stickers is yellow or white, that is the primary sticker. If one of the stickers is blue or green, the other sticker is the primary sticker (these rules are compatible with each other when they would both apply, and they cover all edge pieces). 2) Each edge piece is on two sides at any given point, but give each piece a "primary side" in the same way primary stickers were assigned. 3) If the primary sticker is on the primary side, it is in the "correct orientation". Otherwise, it isn't. Turning the yellow, white, green, or blue side does not change the orientation of any of the edge pieces. Turning the red or orange side changes the orientation of all four of them.
@@yf-n7710 this isn't exactly the same as the colouring I had in mind, but of course any colouring will work, it's just that you need extra rules for different faces the less symmetric it is. Let me give a better explanation of my colouring of the "primary" face for each edge. The faces come in 3 opposite pairs, which I'll abbreviate to W-Y, R-O, and B-G. Define a rock-paper-scissors type of "order" on the pairs. The choice doesn't matter, but for example, say W-Y beats R-O, which beats B-G, which beats W-Y. Now any edge has has two colours, which come from two of the above pairs (they can't be opposite colours). The primary face is the one that" wins" the rock paper scissors game. This colours the cube in a much more symmetric fashion. It would be easier to see with images, but I think this is enough information for anyone to construct it.
@@yf-n7710 yes, I was going to add an edit to say that they are basically two different ways of comparing the pairs of opposite faces and choosing one over the other, but rather than having e.g. W-Y be chosen over both others (making all the pairs fundamentally different from each other) it's more symmetrical to have the rock-paper-scissors type of comparison, which makes each pair identical. Overall, it doesn't make the argument very different, but it's just a little bit neater I think, and more for the sake of having a nice colouring.
parity is the bane of my existence when solving a 4x4 rubik's cube. the cube is first reduced so it looks like a 3x3 cube and then solved conventionally. When reducing the cube there's 2 types of parity, either an edge flip or two edges swapped.
I remember running into this issue when I was coding up a "Lights Out" game. If you randomize all the lights, there's a 50/50 chance that the puzzle is unsolveable.
@@anon_y_mousse Right, but that's not done by giving each square an independent 50% chance of being lit/unlit. I couldn't quite work out the math needed to do a parity check, so the way I solved it was to simulate a certain number of random button-presses, guaranteeing that it could be solved by further presses.
Oh my gosh, I love the 15 puzzle. My mom got me a metal version for a stocking stuffer one Christmas and I have loved it ever since. Glad I found this video. Thank you 😊
An even simpler way to explain why the swapped Rubik's cube is unsolvable: The swap is a single transposition, since you are only switching around two pieces. Thus, the swapped state of the Rubik's cube has odd parity. But every Rubik's cube move is six transpositions, so any solvable position must have even parity.
Wow! This 14 15 puzzle brings back memories : I remember getting a this exact problem at a math olympiad a few years ago, quite the fun exercice, though the subject led us on the right path
I think I’ve seen this in a video game before. There is game for the Nintendo DS called Castlevania: Dawn of Sorrow, where you have to explore the many different parts of a large monster infested castle. One of the areas, the Demon Guest House, has a section where the rooms are arranged and numbered the same as the 15-puzzle, but with different placements of pathways. In order to progress further, you have to arrange the rooms from outside before going through them.
Fun fact, every permuration can be represented as a matrix of 1s and 0s. And by taking the determinant of that matrix, you get either +1 or -1 and it corresponds to parity
I first ran into the parity problem as a very young child with the 15 puzzle. The puzzle itself was fine. For days I couldn't figure out why I couldn't put the numbers on the puzzle in reverse order from 15 down to 1 starting with 15 in the top left. I was convinced that there was no reason that it couldn't work. I eventually gave up but suspected it had something to do with the blank space not being able to represent a zero. I never did figure it out until decades later encountering parity on the 3x3 cube while learning blind solving.
'Mien' is prononuced the same as 'mean' and hence that line's ending rhymes with the other 8 line endings. Mien apparently means a person's appearance or manner, especially as an indicator of character or mood.
Barbarian: _smashes the puzzle board, then puts the pieces back together in a state vaguely resembling the goal state, but significantly damaged_ "There, solved."
fascinating. really nice explanation-a good balance of theoretical and practical ideas. I'm still trying to understand why the arrows ought to cancel out in all cases for the last example, but I understand how parity is derived from that fact.
Imagine doing it backwards. To insert any transposition while preserving that the start and end are the same, you have to add a pair of identical arrows. If you only add a single arrow (that wouldn't cancel with another arrow), then the end won't still be the same as the start. After adding pairs, you can shuffle the arrows around each other just like in this video, except to random locations instead of pulling everything to the top. You can make all sorts of sequences of arrows this way, but you can't make any that include introducing arrows that don't cancel. If you remove a piece from its original position, you have to put it back.
Nice video! For the last argument, I hoped that there would be a neat argument where you prove that since all combination of swaps that result in the identity are required to have an even number of swaps, since the identity needs 0 swaps, you cannot have a permutation that can be reached using both even and odd transpositions by contradiction. It seems like there is there might be some argument, where the total number of times each position is referenced in the transpositions must be even, that can bypass "dragging" the arrows to the front. Say the permutation (12)(23), since 1 and 3 only show up once, it is impossible to the first/third element to be in the correct position.But this is not sufficient, as (13)(21)(31) has 3 references to 1, but the permutation has 1 in the correct position.
Parity is a fantastic tool for pen and pencil puzzles that are about drawing a path or loop in a grid. Oftentimes you can rule out passageways that have the wrong parity for what the final solution or nearby segments require.
Beautiful theorem and a beutifully represented video! The end was felt a little bit rushed, and the rubics cube example felt like it wasn't needed. Maybe by focusing solely on 14-15 puzzle more time could be left for the discussion of equivalence. Great work anyway!
I have slight misunderstanding concerning the last implication at 13:09 : "number of moves = 3 • transpositions". If one move requires 3 transpositions, shouldn't it be the number of transpositions that is equal to 3 • number of moves ?
This reminds me of an assignment about 8 puzzle which before start solving we needed to check whether it was possible or not by using parity with involved summing (the pieces out of order, if i recall correctly). Another way of thinking abount it is having a starting position and drawing a graph and the various variations you can reach "playing" the game. At some point, in the 8/15 puzzle you will have two islands in the graph represent one with even parity and the other odd parity. I think its a neat solution 😮
I think a little more explanation about the conversion of swaps at 16:00 would have been useful. It's not TOO complicated to figure out if you pause the video and think, but if you don't get it the first time (like me) it breaks the flow of the intuitive visual proof about re-arranging the transpositions.
in the rubik's cube part there are 2 other indipendant unsolvable positions: edge flip, when an edge flips(example white red to red white) and corner twist(white red blue to red blue white)
The animations at the end of the video remind me of videos on braid theory made by Ester Dalvit. What you have there is basically a braid where the strands can freely pass through each other
This is a great math video! I would have liked to see a more in-depth explanation on why we can transcribe the arrows while moving them with another arrow that has a common target, though. While the rest of the video was very easy to follow, this one step was not really well explained at all, just shortly glossed over and then using it for the rest of the proof.
A simple way of putting it: if you Scramble a Rubik's cube with an even number of moves, then you can only Solve it in an even number of moves (same for odd) (180 deg turns count as 2 moves)
This has a simple explanation. A swap operation is an elemental matrix that is the identity matrix except with 2 diagonal "1" elements going to the cross positions, and has a determinant value of -1. A net permutation will have a determinant value of either +1 or -1, and thus the matrix will be composed of an even or odd, respectively, number swap matrices in some concatenation (i.e., the concatenation of any single swap matrix reverses the sign of the determinant since the determinant of a concatenation of matrices is equal to the product of the determinants of the concatenands). The "solved" permutation is the identity permutation (and thus is the identity matrix), with a determinant of +1, and so the only way that there can be a round trip of swaps to get from the solved state to some unsolved state and then back is to do the swaps in inverse order, and thus there must be an even number of swaps. An initial permutation having a determinant of -1 can only get to the solved state with an off number of swaps, and thus there must exist an uninverted swap somewhere.
Nice vid! Although I would be cautious about calling Sam Loyd a chess 'grandmaster', as that was not an official title during his lifetime (I think the term 'master' would be the most appropriate in this case, as it's not an official title and should be enough to convey that he was indeed a strong player). I have a goal of making my own interactive explainer of this in the future (although it has to wait until after I finish my thesis), and it's nice to see that people still find these things as intriguing and counterintuitive as I do.
Read decades ago, so not sure of the details, that Sam Loyd's 14-15 puzzle sold very well. Also it announced a prize to who solved the puzzle. Many tried to claim the prize but couldn't show the moves needed for a solution. Was it a lie by publishers to sell more puzzles? Loyd showed that the solution was quite simple! Note that his puzzle consisted of blocks that can be lifted, this is important. The original setting is: 1 2 3 4, 5 6 7 8, 9 10 11 12, 13 15 14 x. Pick up 6, rotate 180 degrees, and put it back. It is a 9! Do the same with original 9, it becomes a 6. So the puzzle becomes. 1 2 3 4, 5 9 7 8, 6 10 11 12, 13 15 14 x. Five transpositions to change 9 7 8 6 into 6 7 8 9, plus 1 to swap 15 - 14 gives a total of 6, an even number. So now parity is satisfied. Sam Loyd was very brilliant (and tricky).
but what about a rubics cube, where one cormer piece is twisted 120° around it´s room-diagonal, that it´s colors don´t match the rest any more, while the rest is solved? Or a single edge piece, that is twisted 180° around it´s plane-diegonal with a similar effect? Is this solvable?
This was such a good experience, loved the video. +1 sub for you my friend, really good. Keep up the good work, will be looking forward to more incredible videos of yours!
Great video and explanation. But there is another way that the Rubik's cube can be arranged so that it is impossible to solve. That is, by twisting only one corner either clockwise or counter-clockwise.. Can a parity argument be used to explain this?
It’s more complicated because you have 3-way parity (divisibility by 3 instead of 2), but yes. Here is the proof: Assign every orientation a number ( 0, 1, 2 ). In the solved state, the orientations are all zero ( by definition ). A single turn increments the orientation of 2 corners and decrements the orientation of the other 2 ( can be seen if you imagine moving the corner back by mirroring it instead of rotating ) 1 + 1 - 1 - 1 = 0, and so a turn does not have any effect on the parity of the corner orientations, no matter how many turns you do, the parity will never change, and so changing it by twisting a corner ( +1 or -1 ) will break the cube unless the sum of the twists ( mod 3 ) is 0
I don't know if I misunderstood, but is the video saying solving *any* state of the 15 puzzle requires an even number of moves or is it just for the "13-15-14" case? 'cause I have solved it in an odd number of moves.
8:33 *43 -Trillion- Quintillion 9:20 These hooks are why any Rubiks style puzzle bigger than a 5x5x5 has weird deformations. (such as extra large edge pieces or pillowed faces) It is impossible to make a uniform puzzle larger than 5x5x5 with these hooks. (without using some kind of engineering trick)
So, with the 15 problem, one gets to it from an initally ordered state, right? So, simply reverse all the moves, or play it backwards, and one gets back to it, surely? How does this proof disprove this?
At 7:33 it is said that "this still holds true when we restrict ourselves to only moves that are actually allowed in the game". How can that statement be true if the solution is actually impossible to achieve?
I would love to see one of those "swapped up" impossible Rubik cubes being inadvertently given to one of these cube solving professionals, just to witness the meltdown 😁 Or would they detect the trap immediately?
I feel like something is missing - out of the explaination (until 8:09 ), this position should be possible and have odd numbers of transpositions in both cases: 01 02 03 04 05 06 07 08 09 10 11 12 13 15 ** 14
YOU HAVE NO IDEA how much I needed this. Parity becomes very relevant when solving cubes blindfolded, or when trying to come up with methods for different cubes. I had a solid understanding of HOW it works but not WHY it happens. Thanks for this
I cannot imagine learning 4bld or 5bld huge respect
I’m floored that a video with this high of quality isn’t far more popular
especially the fact that it's made in powerpoint (i think)
17:35 when you have the math test and you try to remember what you studied:
Liked and subscribed, agree
Seems intuitive that a video like this has a small audience, have you ever interacted with humans?
Second that.
There is really good sequencing/story-telling throughout this video, from the history of the 15 puzzle, leading into the Rubik's cube, then going into the proof. Not only have you explained the proofs well, but you've given context to an otherwise abstract concept in mathematics. Gj!
After learning how to solve the Rubik's cube when I was 17, I learned about parity/parody such as this, and found that this concept is easier to understand than it is to explain it.
Peers would scramble my cube and accidentally twist a corner piece and then halfway through the solve I would notice the problem and often the people watching would think I was cheating by twisting the piece back, thereby causing the issue of it being harder to explain than to understand. People will often be unwilling to listen when they think you're cheating them.
Bonus fact: The famous melting cube that's popular on shirts, and is even worn by Sheldon Cooper in "The Big Bang Theory", is also in parity, unsolvable without rearranging pieces or twisting a corner. (Aside from the fact that you can't turn the sides on the melting cube lol)
Great video. Completely explains the 15 puzzle. However, with Rubik's cube the parity is more complex. Interesting fact that most people forget about the exact position of the middle cubicle, which can be observed if you make a little colored dot toward the neighboring four colors on each side of the center cubicle. If you take that into consideration also when solving the cube, it becomes harder to solve. You can prank your speedcuber friend with this trick. The parity rule stands for the middle cubicles as well, although you cannot notice it unless you mark them.
Get a picture cube. It's easier and looks better.
@@anon_y_mousse good point 🙂 (I certainly have a picture cube)
@@anon_y_mousseor a super cube
A more interesting example is the corner twists on the rubik's cube. If a single corner is twisted (to either of the other orientations), then the cube is unsolvable. This one can't simply be solved with the parity (sign) of permutations, because the single corner twist actually moves you between 3 separate orbits of the scrambles under the action of the group generated by allowed moves, rather than just 2 orbits (which are solved with the "modulo 2" type of invariant created by the sign of permutations).
Instead you need to use some sort of modulo 3 invariant of the rubik's cube. The easiest way to do it that I can think of is to mark the "up" face and "down" face with arrows coming up and down from the 4 corner locations, respectively. Then additionally, mark each corner piece with an arrow, initially in the same place as the arrows fixed to the up and down faces, but these are fixed to the pieces. Then keep track of the total clockwise angle that the corner pieces' arrows make relative to the arrow fixed on the same corner location - this total angle can be thought of as a multiple of 120 degrees, modulo 360 degrees (or divide out the 120 degrees, and get a number modulo 3).
If you make a move rotating the up or down face, then the corner pieces' orientations don't change relative to the arrow marking the default orientation in that location, so the total angle is unchanged. If you make a move rotating any of the other 4 faces clockwise by a quarter turn, then from the perspective of looking at this face: the top left corner moves to the top right, and rotates 120 degrees clockwise relative to the default (upwards) orientation at the new location. The top right corner moves to the bottom right, and rotates 240 degrees clockwise relative to the default (downwards) orientation at the new location. Similarly, the bottom right corner goes to the bottom left and rotates 120 degrees clockwise, and the bottom left corner goes to the top left and rotates 240 degrees clockwise. Overall, the total of the angles changes by 1 + 2 + 1 + 2 = 6 = 0 (modulo 3) lots of 120 degrees. Any other rotation of these faces can be made up out of clockwise quarter turns, so this shows that every move fixes the total relative orientation of the corner pieces.
As a side note, there is one more parity of rubik's cubes, which is the edge orientations. If you flip one edge, then it becomes unsolvable. This is a sort of modulo 2 parity, but you can solve it even more easily than the corner twists by doing the same sort of orientation colouring as above. It's hard to describe the colouring, but it's a very natural symmetric colouring of edge orientations of a cube: on every face, the default orientation of any edge should be different to (not on the same face as) an adjacent edge. This makes a consistent colouring, which you can try yourself with a cube, but I'm not going to prove that it's consistent. Then any move you can make with a rubiks cube will flip the orientation (relative to the defaults) of all 4 edges that move, and hence preserve the modulo 2 total orientation of the edges.
I'm not entirely sure I understand your edge-orientation invariant. I've discovered my own, but yours sounds more simply stated than mine even if I don't understand it. If you'd be willing to explain further, that would be cool. I put my own invariant below.
Mine works the following way (note that I'm using traditional rubik's cube coloring, with opposite color pairs being yellow/white, red/orange, and blue/green):
1) Each edge piece has two stickers, but give each piece a "primary sticker" in the following way: if one of the stickers is yellow or white, that is the primary sticker. If one of the stickers is blue or green, the other sticker is the primary sticker (these rules are compatible with each other when they would both apply, and they cover all edge pieces).
2) Each edge piece is on two sides at any given point, but give each piece a "primary side" in the same way primary stickers were assigned.
3) If the primary sticker is on the primary side, it is in the "correct orientation". Otherwise, it isn't.
Turning the yellow, white, green, or blue side does not change the orientation of any of the edge pieces. Turning the red or orange side changes the orientation of all four of them.
@@yf-n7710they are equivalent
@@yf-n7710 this isn't exactly the same as the colouring I had in mind, but of course any colouring will work, it's just that you need extra rules for different faces the less symmetric it is.
Let me give a better explanation of my colouring of the "primary" face for each edge.
The faces come in 3 opposite pairs, which I'll abbreviate to W-Y, R-O, and B-G. Define a rock-paper-scissors type of "order" on the pairs. The choice doesn't matter, but for example, say W-Y beats R-O, which beats B-G, which beats W-Y.
Now any edge has has two colours, which come from two of the above pairs (they can't be opposite colours). The primary face is the one that" wins" the rock paper scissors game. This colours the cube in a much more symmetric fashion. It would be easier to see with images, but I think this is enough information for anyone to construct it.
@@stanleydodds9 Oh, that's almost the same as my thing, that's cool. And I can see how it's more symmetrical.
@@yf-n7710 yes, I was going to add an edit to say that they are basically two different ways of comparing the pairs of opposite faces and choosing one over the other, but rather than having e.g. W-Y be chosen over both others (making all the pairs fundamentally different from each other) it's more symmetrical to have the rock-paper-scissors type of comparison, which makes each pair identical. Overall, it doesn't make the argument very different, but it's just a little bit neater I think, and more for the sake of having a nice colouring.
parity is the bane of my existence when solving a 4x4 rubik's cube.
the cube is first reduced so it looks like a 3x3 cube and then solved conventionally.
When reducing the cube there's 2 types of parity, either an edge flip or two edges swapped.
2 edges swapped is pathetically easy to solve 😂
Flip edges, not so much 😮
I remember running into this issue when I was coding up a "Lights Out" game. If you randomize all the lights, there's a 50/50 chance that the puzzle is unsolveable.
Depends on how you control the lights. There's a version that comes with emacs which is solvable regardless of the randomization.
@@anon_y_mousse Right, but that's not done by giving each square an independent 50% chance of being lit/unlit.
I couldn't quite work out the math needed to do a parity check, so the way I solved it was to simulate a certain number of random button-presses, guaranteeing that it could be solved by further presses.
That's honestly the best explanation of parity on 15 puzzle, great video!
egg
@@effperm egg
egg
yaytso pashot
Argument at 13:09 is slightly incorrect. The number of moves is 1/3 the number of transpositions. But the point is that their parity is identical.
Oh my gosh, I love the 15 puzzle. My mom got me a metal version for a stocking stuffer one Christmas and I have loved it ever since. Glad I found this video. Thank you 😊
An even simpler way to explain why the swapped Rubik's cube is unsolvable: The swap is a single transposition, since you are only switching around two pieces. Thus, the swapped state of the Rubik's cube has odd parity. But every Rubik's cube move is six transpositions, so any solvable position must have even parity.
Nice! And I think we can all agree that hexagonal channels logos are the best.
Wow! This 14 15 puzzle brings back memories : I remember getting a this exact problem at a math olympiad a few years ago, quite the fun exercice, though the subject led us on the right path
I think I’ve seen this in a video game before. There is game for the Nintendo DS called Castlevania: Dawn of Sorrow, where you have to explore the many different parts of a large monster infested castle.
One of the areas, the Demon Guest House, has a section where the rooms are arranged and numbered the same as the 15-puzzle, but with different placements of pathways. In order to progress further, you have to arrange the rooms from outside before going through them.
Fun fact, every permuration can be represented as a matrix of 1s and 0s. And by taking the determinant of that matrix, you get either +1 or -1 and it corresponds to parity
I first ran into the parity problem as a very young child with the 15 puzzle. The puzzle itself was fine. For days I couldn't figure out why I couldn't put the numbers on the puzzle in reverse order from 15 down to 1 starting with 15 in the top left. I was convinced that there was no reason that it couldn't work. I eventually gave up but suspected it had something to do with the blank space not being able to represent a zero. I never did figure it out until decades later encountering parity on the 3x3 cube while learning blind solving.
Most focusing on the wrong detail ever, but the Lloyd checkmate problem is solved with:
1. Bc6+ Kd4
2. Rf3+ Be4
3. Bxe4#
Amazing video, thank you for such a clear and intuitive explanation of a not-so-inutitive concept !
'Mien' is prononuced the same as 'mean' and hence that line's ending rhymes with the other 8 line endings. Mien apparently means a person's appearance or manner, especially as an indicator of character or mood.
This is a really high quality video. Hopefully it hits the algorithm soon.
Barbarian: _smashes the puzzle board, then puts the pieces back together in a state vaguely resembling the goal state, but significantly damaged_ "There, solved."
You do a great job leading us down the path of logic so that every step makes intuitive sense!
Really good explanations. High quality presentation!
fascinating. really nice explanation-a good balance of theoretical and practical ideas. I'm still trying to understand why the arrows ought to cancel out in all cases for the last example, but I understand how parity is derived from that fact.
Imagine doing it backwards. To insert any transposition while preserving that the start and end are the same, you have to add a pair of identical arrows. If you only add a single arrow (that wouldn't cancel with another arrow), then the end won't still be the same as the start. After adding pairs, you can shuffle the arrows around each other just like in this video, except to random locations instead of pulling everything to the top.
You can make all sorts of sequences of arrows this way, but you can't make any that include introducing arrows that don't cancel. If you remove a piece from its original position, you have to put it back.
I am amazed after seeing the difference between quality of the video and the attention it got
really surprised this doesn’t have a few hundred thousand views, good stuff
Nice video! For the last argument, I hoped that there would be a neat argument where you prove that since all combination of swaps that result in the identity are required to have an even number of swaps, since the identity needs 0 swaps, you cannot have a permutation that can be reached using both even and odd transpositions by contradiction.
It seems like there is there might be some argument, where the total number of times each position is referenced in the transpositions must be even, that can bypass "dragging" the arrows to the front. Say the permutation (12)(23), since 1 and 3 only show up once, it is impossible to the first/third element to be in the correct position.But this is not sufficient, as (13)(21)(31) has 3 references to 1, but the permutation has 1 in the correct position.
Parity is a fantastic tool for pen and pencil puzzles that are about drawing a path or loop in a grid. Oftentimes you can rule out passageways that have the wrong parity for what the final solution or nearby segments require.
Beautiful theorem and a beutifully represented video! The end was felt a little bit rushed, and the rubics cube example felt like it wasn't needed. Maybe by focusing solely on 14-15 puzzle more time could be left for the discussion of equivalence. Great work anyway!
I have slight misunderstanding concerning the last implication at 13:09 : "number of moves = 3 • transpositions". If one move requires 3 transpositions, shouldn't it be the number of transpositions that is equal to 3 • number of moves ?
This reminds me of an assignment about 8 puzzle which before start solving we needed to check whether it was possible or not by using parity with involved summing (the pieces out of order, if i recall correctly). Another way of thinking abount it is having a starting position and drawing a graph and the various variations you can reach "playing" the game. At some point, in the 8/15 puzzle you will have two islands in the graph represent one with even parity and the other odd parity. I think its a neat solution 😮
I hate Square1 parity
I think a little more explanation about the conversion of swaps at 16:00 would have been useful. It's not TOO complicated to figure out if you pause the video and think, but if you don't get it the first time (like me) it breaks the flow of the intuitive visual proof about re-arranging the transpositions.
in the rubik's cube part there are 2 other indipendant unsolvable positions:
edge flip, when an edge flips(example white red to red white) and
corner twist(white red blue to red blue white)
Always got to love it when someone mathematically proves something is impossible but people will still try anyway.
Nice video shot, well done, thank you for sharing it with us :)
there is also tri-arity on the rubik's cube called the corner twist
The animations at the end of the video remind me of videos on braid theory made by Ester Dalvit. What you have there is basically a braid where the strands can freely pass through each other
parity is so ubiquitous in many proofs that I never noticed how powerful it is!
thank you! keep up the good work!
Speaking of the Rubik's cube, a single twisted corner is impossible to solve.
Can you do more real world examples, for example cryptography, zero-knowledge proofs?
This is a great math video! I would have liked to see a more in-depth explanation on why we can transcribe the arrows while moving them with another arrow that has a common target, though. While the rest of the video was very easy to follow, this one step was not really well explained at all, just shortly glossed over and then using it for the rest of the proof.
The Rubik's cubes with even side lengths have parity cases. And there are algorithms to simplify them.
A simple way of putting it: if you Scramble a Rubik's cube with an even number of moves, then you can only Solve it in an even number of moves (same for odd) (180 deg turns count as 2 moves)
This has a simple explanation. A swap operation is an elemental matrix that is the identity matrix except with 2 diagonal "1" elements going to the cross positions, and has a determinant value of -1. A net permutation will have a determinant value of either +1 or -1, and thus the matrix will be composed of an even or odd, respectively, number swap matrices in some concatenation (i.e., the concatenation of any single swap matrix reverses the sign of the determinant since the determinant of a concatenation of matrices is equal to the product of the determinants of the concatenands). The "solved" permutation is the identity permutation (and thus is the identity matrix), with a determinant of +1, and so the only way that there can be a round trip of swaps to get from the solved state to some unsolved state and then back is to do the swaps in inverse order, and thus there must be an even number of swaps. An initial permutation having a determinant of -1 can only get to the solved state with an off number of swaps, and thus there must exist an uninverted swap somewhere.
My brain is fried at the moment. But want to come back later. Thank you for your effort
I feel like at some point I got my cube in impossible position...
Nice vid! Although I would be cautious about calling Sam Loyd a chess 'grandmaster', as that was not an official title during his lifetime (I think the term 'master' would be the most appropriate in this case, as it's not an official title and should be enough to convey that he was indeed a strong player). I have a goal of making my own interactive explainer of this in the future (although it has to wait until after I finish my thesis), and it's nice to see that people still find these things as intriguing and counterintuitive as I do.
Read decades ago, so not sure of the details, that Sam Loyd's 14-15 puzzle sold very well. Also it announced a prize to who solved the puzzle. Many tried to claim the prize but couldn't show the moves needed for a solution. Was it a lie by publishers to sell more puzzles? Loyd showed that the solution was quite simple! Note that his puzzle consisted of blocks that can be lifted, this is important. The original setting is:
1 2 3 4, 5 6 7 8, 9 10 11 12, 13 15 14 x. Pick up 6, rotate 180 degrees, and put it back. It is a 9! Do the same with original 9, it becomes a 6. So the puzzle becomes. 1 2 3 4, 5 9 7 8, 6 10 11 12, 13 15 14 x. Five transpositions to change 9 7 8 6 into 6 7 8 9, plus 1 to swap 15 - 14 gives a total of 6, an even number. So now parity is satisfied. Sam Loyd was very brilliant (and tricky).
but what about a rubics cube, where one cormer piece is twisted 120° around it´s room-diagonal, that it´s colors don´t match the rest any more, while the rest is solved?
Or a single edge piece, that is twisted 180° around it´s plane-diegonal with a similar effect?
Is this solvable?
6:18 If I set down a coin and tell you to make it face the other way up, you cannot do that except by using an odd number of flips.
Fantastic explanation!
This was such a good experience, loved the video.
+1 sub for you my friend, really good. Keep up the good work, will be looking forward to more incredible videos of yours!
0:03 *grabs a hammer*
Great video and explanation. But there is another way that the Rubik's cube can be arranged so that it is impossible to solve. That is, by twisting only one corner either clockwise or counter-clockwise.. Can a parity argument be used to explain this?
It’s more complicated because you have 3-way parity (divisibility by 3 instead of 2), but yes.
Here is the proof:
Assign every orientation a number ( 0, 1, 2 ).
In the solved state, the orientations are all zero ( by definition ). A single turn increments the orientation of 2 corners and decrements the orientation of the other 2 ( can be seen if you imagine moving the corner back by mirroring it instead of rotating )
1 + 1 - 1 - 1 = 0, and so a turn does not have any effect on the parity of the corner orientations, no matter how many turns you do, the parity will never change, and so changing it by twisting a corner ( +1 or -1 ) will break the cube unless the sum of the twists ( mod 3 ) is 0
I don't know if I misunderstood, but is the video saying solving *any* state of the 15 puzzle requires an even number of moves or is it just for the "13-15-14" case? 'cause I have solved it in an odd number of moves.
Any state with an odd number of transpositions
8:33
*43 -Trillion- Quintillion
9:20
These hooks are why any Rubiks style puzzle bigger than a 5x5x5 has weird deformations. (such as extra large edge pieces or pillowed faces)
It is impossible to make a uniform puzzle larger than 5x5x5 with these hooks. (without using some kind of engineering trick)
He probably use old convention (long scale) for the trillion, which is 10^18 instead of 10^12.
Great explanation! Thank you!
Super well made video! I learned a lot
Logic is the most powerful instrument ever invented!
So, with the 15 problem, one gets to it from an initally ordered state, right? So, simply reverse all the moves, or play it backwards, and one gets back to it, surely? How does this proof disprove this?
Now i know why those are called parity issues on the 4x4
X! permutations is always even so the parity falls on N irreducible strings, so imagine 7 blocks would have odd transitions
This is incredibly random but do you have a channel where you talk about speedrunning? I swear I recognize your voice. Great video by the way
At 7:33 it is said that "this still holds true when we restrict ourselves to only moves that are actually allowed in the game". How can that statement be true if the solution is actually impossible to achieve?
How did you make those animations?
11:35 what about 180 degrees, in cube notation it counts as 1 move
But still a 180 degree rotation is just doing 6 swap so you can simplify it as 2, 90 degree 3 swaps
Excellent video!
I would love to see one of those "swapped up" impossible Rubik cubes being inadvertently given to one of these cube solving professionals, just to witness the meltdown 😁
Or would they detect the trap immediately?
8:37 it's funny you used two different meaning for "trillion" in the same sentence.
Underrated !!!
Really great video
How is permutation parity an unintuitive concept? It's very natural and has been known for centuries!
In my childhood every rubic cubic was unsolvable.
I see, permutation groups.
So you could also solve the 15 14 puzzle with parity, because for the square to be orange, you need an even number of moves
can't you just cancel arrows in threes?
Great video!!!
I know it's long, but it takes me less than 5 minutes to solve the 6 by 6.
I feel like something is missing - out of the explaination (until 8:09 ), this position should be possible and have odd numbers of transpositions in both cases:
01 02 03 04
05 06 07 08
09 10 11 12
13 15 ** 14
for that, the other way says it requires an odd number of moves.
@@MichaelDarrow-tr1mn I corrected - I meant odd in both cases (as the free case is green now)
... the last Gem Green puzzle is ... unsolvable ...
Good stuff.. Thank you.
You solve it by flipping a corner. ;)
There's an algorithm to solve the unsolvable cube on a 4x4
So puzzles which can always be solved, and puzzles which can end up in unsolvable states.
8:33, 43 Quintillion, not Trillion.
You spelled unsolvable wrong
Interesting video but if the puzzle is impossible then it isn't classed as a puzzle
Wow... People wrote different in 1880.
The Rubik’s cube is hard? Say that to max park loolll
43 quintilion
He probably use old convention (long scale) for the trillion, which is 10^18 instead of 10^12.
😎
You just explained invariants.
Good job. But it's not a sophisticated enough topic for me
Cuber gang
👇
😂I just solved 😂
Ч0З
Great video!!!