I’m floored that a video with this high of quality isn’t far more popular

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)

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

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.

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!

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.

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.

That's honestly the best explanation of parity on 15 puzzle, great video!

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.

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.

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 😊

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

Barbarian: _smashes the puzzle board, then puts the pieces back together in a state vaguely resembling the goal state, but significantly damaged_ "There, solved."

'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.

Most focusing on the wrong detail ever, but the Lloyd checkmate problem is solved with: 1. Bc6+ Kd4 2. Rf3+ Be4 3. Bxe4#

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.

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.

You do a great job leading us down the path of logic so that every step makes intuitive sense!

Amazing video, thank you for such a clear and intuitive explanation of a not-so-inutitive concept !

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!

Really good explanations. High quality presentation!

Nice video shot, well done, thank you for sharing it with us :)

thank you! keep up the good work!

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.

Fantastic explanation!

really surprised this doesn’t have a few hundred thousand views, good stuff

Always got to love it when someone mathematically proves something is impossible but people will still try anyway.

I am amazed after seeing the difference between quality of the video and the attention it got

Great explanation! Thank you!

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 😮

This is a really high quality video. Hopefully it hits the algorithm soon.

Super well made video! I learned a lot

Nice! And I think we can all agree that hexagonal channels logos are the best.

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.

Excellent video!

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!

parity is so ubiquitous in many proofs that I never noticed how powerful it is!

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.

My brain is fried at the moment. But want to come back later. Thank you for your effort

Really great video

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)

Great video!!!

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

Underrated !!!

there is also tri-arity on the rubik's cube called the corner twist

I feel like at some point I got my cube in impossible position...

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.

Good stuff.. Thank you.

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.

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.

Can you do more real world examples, for example cryptography, zero-knowledge proofs?

The Rubik's cubes with even side lengths have parity cases. And there are algorithms to simplify them.

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.

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)

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.

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 ?

Logic is the most powerful instrument ever invented!

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

Speaking of the Rubik's cube, a single twisted corner is impossible to solve.

Now i know why those are called parity issues on the 4x4

0:03 *grabs a hammer*

X! permutations is always even so the parity falls on N irreducible strings, so imagine 7 blocks would have odd transitions

I see, permutation groups.

In my childhood every rubic cubic was unsolvable.

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

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?

I know it's long, but it takes me less than 5 minutes to solve the 6 by 6.

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?

How did you make those animations?

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).

8:37 it's funny you used two different meaning for "trillion" in the same sentence.

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?

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)

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?

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.

How is permutation parity an unintuitive concept? It's very natural and has been known for centuries!

11:35 what about 180 degrees, in cube notation it counts as 1 move

You solve it by flipping a corner. ;)

I hate Square1 parity

can't you just cancel arrows in threes?

There's an algorithm to solve the unsolvable cube on a 4x4

... the last Gem Green puzzle is ... unsolvable ...

8:33, 43 Quintillion, not Trillion.

😎

So puzzles which can always be solved, and puzzles which can end up in unsolvable states.

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

Wow... People wrote different in 1880.

You spelled unsolvable wrong

Interesting video but if the puzzle is impossible then it isn't classed as a puzzle

The Rubik’s cube is hard? Say that to max park loolll

43 quintilion

Cuber gang 👇

😂I just solved 😂

You just explained invariants. Good job. But it's not a sophisticated enough topic for me

Ч0З

Great video!!!