About an unintuitive concept that explains unsolvable Puzzles
Vložit
- čas přidán 19. 06. 2023
- What is the reason that certain seemingly simple problems, like some special Rubic's Cubes, can't be solved? We have to investigate the property known as Parity...
Try the 15 Puzzle online: lorecioni.github.io/fifteen-p...
Our parity proof: "The Sign of a Permutation", Keith Conrad, kconrad.math.uconn.edu/blurbs... Theorem 2.1.
Article about the 15 Puzzle: daily.jstor.org/square-space-...
More on parity: en.wikipedia.org/wiki/Parity_...
Chess Tactic Solution: Ke2(!) en.chessbase.com/post/chessba... (bottom of the page) - Věda a technologie
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.
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
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.
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.
That's honestly the best explanation of parity on 15 puzzle, great video!
egg
@@effperm egg
egg
yaytso pashot
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.
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
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.
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.
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 😊
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!
Really good explanations. High quality presentation!
Nice video shot, well done, thank you for sharing it with us :)
Always got to love it when someone mathematically proves something is impossible but people will still try anyway.
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!
thank you! keep up the good work!
really surprised this doesn’t have a few hundred thousand views, good stuff
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.
Super well made video! I learned a lot
Fantastic explanation!
This is a really high quality video. Hopefully it hits the algorithm soon.
Nice! And I think we can all agree that hexagonal channels logos are the best.
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 😮
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 so ubiquitous in many proofs that I never noticed how powerful it is!
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)
Excellent video!
there is also tri-arity on the rubik's cube called the corner twist
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 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.
Underrated !!!
Really 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
Great video!!!
My brain is fried at the moment. But want to come back later. Thank you for your effort
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.
I feel like at some point I got my cube in impossible position...
The Rubik's cubes with even side lengths have parity cases. And there are algorithms to simplify them.
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)
Can you do more real world examples, for example cryptography, zero-knowledge proofs?
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.
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.
Logic is the most powerful instrument ever invented!
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.
Good stuff.. Thank you.
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?
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).
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
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?
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.
X! permutations is always even so the parity falls on N irreducible strings, so imagine 7 blocks would have odd transitions
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
Speaking of the Rubik's cube, a single twisted corner is impossible to solve.
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
Now i know why those are called parity issues on the 4x4
How did you make those animations?
I see, permutation groups.
8:37 it's funny you used two different meaning for "trillion" in the same sentence.
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?
In my childhood every rubic cubic was unsolvable.
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
can't you just cancel arrows in threes?
I know it's long, but it takes me less than 5 minutes to solve the 6 by 6.
How is permutation parity an unintuitive concept? It's very natural and has been known for centuries!
You solve it by flipping a corner. ;)
There's an algorithm to solve the unsolvable cube on a 4x4
0:03 *grabs a hammer*
... the last Gem Green puzzle is ... unsolvable ...
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)
So puzzles which can always be solved, and puzzles which can end up in unsolvable states.
8:33, 43 Quintillion, not Trillion.
😎
Wow... People wrote different in 1880.
I hate Square1 parity
Interesting video but if the puzzle is impossible then it isn't classed as a puzzle
You spelled unsolvable wrong
43 quintilion
He probably use old convention (long scale) for the trillion, which is 10^18 instead of 10^12.
The Rubik’s cube is hard? Say that to max park loolll
Cuber gang
👇
Ч0З
😂I just solved 😂
You just explained invariants.
Good job. But it's not a sophisticated enough topic for me
Great video!!!