The animation of the puzzle is very well done, as usual the animations are always great and help us to follow along with what the mathematician is saying.
As a teen, I had a larger (7x7) version of the puzzle. It featured a picture of the Leonardo da Vinci's Vitruvian Man as the image. It turned out that there were two completely blank tiles which just happened to have opposite parity. So if you put the wrong identical tile into position, it was impossible to finish. It took me days to work that out.
When I was a kid I was one who was taught that these puzzles are called “Sam Loyd puzzles” because he invented them, but (quite recently!) I learned the truth that the puzzles predate the man, so I thank you, Numberphile, for reinforcing (confirming?) that information for me. As an aside, when I was a little boy my cousin, who was in her early 50’s at the time, would impress me by solving 15 puzzles in the fewest moves and fastest times, and even now when she is a few days shy of her 96th birthday and suffering with dementia she can still solve these puzzles.
i mean it would've been cool if we were shown how the parity thing was proven, and why he gets to do transpositions that are clearly impossible given the rules/physical limitations of the game. wouldn't some of the "1 step transpositions" he did when he swapped numbers actually take an even number of steps in the game? wouldn't that actually change the overall parity?
@@alveolate the allowed transpositions are still transpositions, and therefore must have the same parity as a set of not allowed transpositions that get from a to b.
Yeah, it's fascinating. If somebody gave me that puzzle and told to figure out if it's possible configuration or not, I wouldn't have a slightest clue where to even begin. Yet the solution is so simple and elegant when explained.
I was sort of thinking the same thing about allowed transpositions before he got to his proof: What if you played this in a 3D cube?, ND cube? A torus? Those loosen the constraints of the 2D square, but his proof is more generic than any extra constraints you want to impose
Instead of explicitly counting the lefts/rights/ups/downs for the blank space, I prefer giving the tray a checkerboard colouring. The blank space then changes colour every move, so must do an even number of moves to get back to the same colour (or same location).
Was my first instinct after trying to figure out if there was some weird rule about even and odd numbers. That rule probably exists in 5x5 and 3x3 fields, but not in 4x4 ones.
Actually, the simplest way to think of it is that 0 is the fewest number of moves, because it is already in the correct position . 0 is even, so all are even.
I graduated with a math degree about five years ago and don’t get to do math everyday like I did in school. The COVID-19 pandemic and shelter in place has given me an opportunity to pull out my old textbooks and think about things I love so much again. I had my abstract algebra book out last weekend and was reading and thinking about permutations and parity. Thanks for sharing this. Made my heart pitter patter. ❤️
We had one when I was young where the reverse order was labeled "unmöglich". (Presumably the puzzle was from Germany. :) ) I always wondered why, back then.
@@squeakybunny2776 that's flat out wrong. For his argument, YES, it was assumed. A statement without proof is by definition an assumption, axiom, postulate, premise, or condition.
There's a more devious version -- instead of 1-15, the tiles say "RATE YOUR MIND PAL" in horizontal rows. What you can do is show someone what it says and scramble the letters while they watch and challenge them to unscramble them. But what you do is put the "R" in YOUR into the upper left corner where the "R" in RATE should be. But you can't unscramble it that way -- the best you can do is RATE YOUR MIND PLA until you swap the Rs back.
That was amazing. I had such a puzzle as a kid and soon found out, that you can't have every configuration, but didn't know why. Now I know, i'm so happy :)
I actually discovered this and wrote a proof myself in high school. The assignment was actually to write a computer program to find the best next step in the puzzle. This was the early 1980s and we were learning Apple Basic. I fiddled with the example arrangement given and realized it couldn't be solved. So my immediate question was: which arrangements can be solved ash's which can't? I wrote a proof of why the given arrangement could not be solved and of which arrangements in general could and could not. (I had to invent my own language, bear in mind, because I was in high school and hadn't been exposed to most of the math involved yet.) And for my computer program, I wrote an algorithm to test whether the given arrangement was solvable at all, since setting your computer on an unsolvable problem would only serve to waste a lot of computing time until you gave up and aborted the program. :)
That is truly a genius! Apple Basic so can't be earlier than 1983! 37 years ago! It makes you proud today! Did you go on to do lot in maths? Btw, I was thinking on the same lines that such problems need to be given at the school level for children to realise some of the difficult mathematical concepts!
Clearly not, because if it were designed by Matt Parker then he would have given it a go first and realized it was impossible. Or if he were to put it there, then it would be to encourage the user to try it themselves and realize as he had that it was impossible.
Just read a book called "Tales of Impossibility", the puzzle from Sam Loyd was also discussed on Chapter 2. I am amazed of this kind of mathematical proof for its impossibility. Thanks Numberphile!
It's more like "I take it apart and put it back together" but you're on to something. Ruibk's Cubes have parity cases as well. The 15 puzzle has 2 universes of possible combinations of its pieces, only one of which includes possible permutations given legal moves. The Rubik's Cube has 12 universes of possible combinations of its pieces, so there are 11 ways to reconstruct it that are impossible to solve! If you were to take it apart and put the pieces back together randomly, then there's only a 1 in 12 chance that it would be solvable using legal moves! In fact, this is how some scramble algorithm generators work. They reconstruct the cube with a random configuration, check for parity, and repeat until they get a legal permutation. Then they use an algorithm that finds the most efficient solution for that scramble, and give that to the user in reverse. This ensures that every possible legal permutation is equally likely to occur, and that the scramble is not affected by any bias that might result from just trying to make random turns until it "seems" scrambled.
The people who say "I just take the stickers off" wouldn't be so bad if they didn't think they were so special. Yeah, everyone takes the stickers off. 🙄
After a bit of playing around (physically and mathematically), it seems like every “unreachable” simplifies to being the 14 swap 15 problem (possibly with different values needing to swap, but that’s equivalent). So if we allow that move by some means, everything should be reachable! Makes me curious to think what states would be reachable on a Rubik’s cube if there existed a move to fix edge parity or corner parity.
I was terrible at math in school, and I haven't gotten any better as I've gotten older. And yet I find math absolutely fascinating. I love this channel...I find your videos mesmerizing. And I feel so proud of myself when I have my aha moment during a video and understand what is being explained. 😀😀
@@karlboud88 Even more vexing is that he predicted people would say "_I_ take the tiles out" but, what if I referenced another person, for example: "My cousin used to take the tiles out"?
YES! This is exactly my thoughts on the puzzle but written out. I didn't know how to prove it, but this explained it all so clearly. You can use a similar idea to prove that you can't switch only two pieces on a Rubik's cube!
To mess with a friend, I took one corner piece out of his Rubic's Cube and rotated it and put it back. Rubic's Cubes have a similar parity and by doing this, it became unsolvable. lol
The proof follows easily from an understanding of the symmetric group and the alternating group within it, which had been understood for decades before. I imagine he didn't understand the proof, but knew the result.
Another interesting way to look at this is to imagine (or draw) a puzzle with the numbers from 1 to 3 and a blank square. The '1' is in the top left position, '2' in the top right position and '3' in the bottom left position. Now imagine you want to reverse the puzzle so that '3' is in the top left, '2' in the top right and '1 in the bottom left. As you move the pieces around, you can see that it is impossible to move the numbers so that they are no longer clockwise, but the solution you are trying to achieve has the numbers in an anti-clockwise formation. The same principle can be applied to the 4 x 4 puzzle, although its application is not as easy to see. This video does a great job of explaining it.
My brother and I had a couple of these things. I pretty quickly realized that some combinations were impossible ... and also that you could pry out the plastic tiles and pop them back in, so as to get at the impossible ones. I did this to my brother's puzzle, and he could never get back to the original 1->15 arrangement. Drove him nuts for a week!
It's facinating that when you just switch two tiles, you will never be able to go to a setting that was previously possible. Like two universes existing next to each other, whose fabrics are intertwined without a possibility to transition from one to the other
This is why I love mathematics so much! You get deep insight into the problem by proving not just a single instance of a problem, but for ALL possible instances regardless of who you are. An alien from a different galaxy would still agree with us of the correctness, and they would come to the same conclusion IF they share or agree with our axioms.
This is basically a 4x4x0 Rubik's cube, heh. ("Rubik's cube", of course, being a misnomer for similar puzzles because most of them are neither cubes nor Rubik's brand.)
It's way easier than a Rubik's cube. You only need 1 strategy. 124X > 1234 XX3X > XXXX After the first 2 rows you do the same starting on the left. 13 9 X X > 9 X X X X X X X > 13 X X X
@@SgtSupaman yeah true. Idk if you are a cuber or not but if you know how the Rubik's cubes work then you know this puzzle actually works in the same way. There are odd/even parity and there are impossible permutations like flipped edge without moving any other edge.
What I love about this proof is that it simply never bothers properly translating the board into a mathematical form. It simply treats the reality of how you need to swap tiles as an implementation detail. So elegant!
Yeah, but he didn't explain why it would require an odd number of moves to swap the 14 and 15 around. The explanation in this video is still incomplete as they didn't prove parity of permutations, but at least they mentioned it and they showed how it would imply that swapping the 14 and 15 would require an odd number of moves.
I am currently learning about Ring Theory and Group Theory in my Algebraic Structures class. In the class, we just talked about transpositions and permutations, so this video was absolutely fascinating!
@@ratandmonkey2982 You can always tell an Afrikaans accent by the use of the word "ja" (pronounced "yaw"). He doesn't have a very strong accent, but the "ja" gives it away.
All moves must include swapping 16 with something else. Moving any other tile is optional, but moving 16 is compulsory. I didn't do math in high school (aside from what was basically required as part of the curriculum) yet these videos make numbers interesting!
Hello to all. So, if it is necessary to make even time of changes, then arrangement 1, 2, 3, 4,... 15, 16, 14 is possible! After that we make one move more!
I like how the definition of odd is transcended and generalized in the generalization of the solution to the point it becomes mod2 and not anymore "odd". So mathematically genuine
So true, to solve a Rubik's cube is relatively simple until the rule prohibiting the disassembly of the cube is instituted. Yet, even the solution of such a cube would seem to again become impossible, unless the disassembly rule doesn't actually include the peeling/removal of the colored stickers. But again, applying one's own stickers wouldn't be under the disassembly rule, now would it? It's the rules which are the problem, not accomplishing the task requested. Coloring within the lines most assuredly stunts the creativity of humanity. Toss the rule books already! Don't worry, pop out those numbered tiles, make whatever configuration you want, & be happy!
@@WatchingMyLifeFlashB Rules are very important for creativity. For example if your painting is just blotches of colour that's pretty boring. Giving yourself rules to follow like using only these colours, only these shapes or that it must be as realistic as possible can lead to something a lot more interesting.
Very nice video, with beautiful animations! However, I feel that the permutation parity should deserve a proof. It's not that hard; one of the easiest I can think of is counting the number of inversions of a permutation, and prove that for switching any two numbers in the permutation, the number of inversions changes its parity. Let me share the proof with you; sorry if it's a bit technical, but you know - math is math! Besides, I'm sure it can be explained with animations more easily. Let's say we have a permutation of n numbers: p1, p2, ..., pi, ..., pj, ..., pn where pk is the number at the k-th position. Let's use the notation of {i,j} for positions with fixed order i pj, with i odd permutation. THEOREM A: The parity of the number of inversions equals to the parity of the permutation. THEOREM B we will prove: swap any two numbers in a permutation changes the parity of the number of inversions. Since the solved state has 0 number of inversions, which is even, and the solved state is an even permutation, this implies Theorem A. PROOF: Let be our permutation: p1, p2, ..., pi, ..., pj, ..., pn The second permutation is: p'1, p'2, ..., p'i, ..., p'j, ..., p'n Where pk = p'k except for positions i and j: p'i = pj and p'j = pi (we swapped pi and pj, and nothing else). How does the number of inversion changes? Let's see how the inversion-ness of the individual pairs changes after the swap. Each pair falls into one of three categories: A, B and C, described below. We will split B into further sub-categories B1, B2 and B3. A) A pair is not affected by the swap. That is, if k!=i,j and l!=i,j with k
That is *one* possible permutation, but it doesn't prove that every possible permutation has to be even. You get to do as many shuffles as you want. We want to see if, by following the rules of the puzzle, it is possible to get 16 back to where it was in an odd number of steps. It turns out it isn't.
I don't think a "do nothing" permutation exists/is valid, considering you could just do something like 123->312 with (1,3); (1,1); (2,3) and get an odd result if it was a thing.
@@zatherz2498 'Do nothing' is the identity permutation and is the composition of 0 transpositions (or 2,4,6, ...). But you're right that it is not a transposition because it does not switch two (distinct) elements.
@@zatherz2498 Actually your example only proves that the "do nothing" permutation is valid. The "do nothing" permutation would be 0 steps, therefore putting a (1,1) in would NOT make that 3 steps, because that swap is literally doing nothing, ie 0 steps, so you did 1 step, then 0 steps, then 1 step, that's a total of 2 steps, not 3.
As a thought experiment, consider the fact that at some point you need to solve the last 2x2 section of the puzzle. Let's just pretend that's its own little puzzle that's numbered 1 through 3 with a space that I'll choose to call X. The correct arrangement would then be {1, 2, 3, X}. Your only moves in this case would move the space around the puzzle in clockwise or counterclockwise circles, and you could always return to the proper solved order. Now, picture the same 2x2 puzzle but this time starting with the numbers in the top row switched, so the arrangement is {2, 1, 3, X}. Moving the space around the puzzle to get the 1 in the top left corner, you would only ever be able to get to {1, X, 2, 3}, {1, 3, 2, X}, or {1, 3, X, 2}. The tiles can keep going around in circles, but they'll never be in the right order with the 1 in the correct position! You can see the limitation here pretty easily. Each position can swap with its 2 neighbors, but not the remaining position, which is its opposite corner.
Oh man. Never thought I'd see a reference like that these days. Thanks, that made my day. And remember, whatever you do, do not stand next to other people!
Based on the theorems provided, it looks like top row of 15, 14, 13, 16 then counting down normally is theoretically possible. 1) Counting down requires an odd parity. 2) Moving the 16 up one space at a time takes 12 moves, which maintains parity (19, odd). 3) Moving the square to the top-right space takes three singular-square movements, meaning solutions that put the square in the top-right all use an odd parity to solve them.
I figured it out two years ago while creating a sliding puzzle game in JavaScript which actually is available in my youtube channel too. There I was creating initial setup randomly and then recognised, not every permutation gives correct Answer
The other interesting thing is how universal this puzzle is. Whether discussing seating plans, rearranging furniture, ordering choir robes, the phrase "it's one of those 15 square puzzles" is instantly understood by everyone. Whether that understanding brings hope or despair is less universal.
Most likely, yes. My guess is the graphic artist had to fill the space, thought "Hm, reversing the order would be aesthetically pleasing" then just moved the tiles around in Photoshop without checking to see if the solution was even possible. I have a copy of the metal one (which is soooooo satisfying to play with if you like the sound of steel sliding on steel...) and it came with a booklet of something like 20 or 30 different permutations to try, and the one they were testing was literally the second suggestion.
And the thing I like about these types of puzzles is that the algorithm scales as it gets bigger. It's pretty much the same even on a 5x5 or 6x6 or even bigger. Also it works on rectangular puzzles but I'm not sure if there's a way to know if a certain rectangular layout is solvable.
This seems wierdly incomplete. It reduced the problem to proving that permutations have a parity. But it doesn't even try to give an intuition of why that is the case. Also it seems to make the statement that with the allowed moves every configuration with correct parity is possible, but it doesn't make any argument why that follows from the rules.
@@demonsheadshot8086 Not the metal one; I own one and took some tiles off just to see how it worked. Each spot on the tray has a square protrusion on it that looks something like a mushroom head (I'm sure there's a technical term for it but I'm not an engineer so I have no idea what it is...) in the middle. Each tile has a grip arm on the corner that hooks underneath the top of the mushroom head and the sides are hollow so the hooks will always be under a protrusion. In honesty, it's so well designed that I nearly broke mine trying to get one of the tiles off to see how it worked - as it stands, the protrusion for the blank "16" spot wiggles a bit where I had to bend it. EDIT: I incorrectly described the design of the tiles; I was thinking of a completely different puzzle when I wrote that.
Okay I gotta admit that although Numberphile videos are quite easy to understand, this one I actually actually feel like I understood (taking the facts as granted, that is). Great video with both entertainment and educational value, once again! Bravo!
Basically, yes. If you start with the normal order and try to do the reverse as shown on the packaging, 14 and 15 will always be inverted. If you were to take it apart and start with 15 in the upper left and tried to solve it back to normal, 14 and 15 would still be inverted simply because the parity is wrong - the only way to truly reverse the tiles is to move the blank 16 spot from the lower right to the upper left and rearrange the tiles around it. In other words, it doesn't matter what the starting arrangement is, it will be impossible to reverse their order and keep the blank 16 in the same spot.
We have proven, that it's always an impossible task when the parities are different, but we have not proven that it's always possible when the parities are different.
Yes taking the 15-16 swapped configuration and then making just one more move will balance out the parity, but doesn't make it any more possible. It'd be nice to know if/how a configuration could be proven to be impossible even if the parities don't match.
@@marzipancutter8144 I van relate: If one year of studying maths taucht ne anything, it is that destructive proofs are mostly easier than constructive ones.
My 11 year old and I have been racking our brains trying to figure out this new puzzle and why we could not do it backwards. Finally I googled my issue and this immediately appears with the title saying it’s not possible. Saved me much time in throwing in the towel. Funny, because we just assumed any combination was possible.
Switching two edges on the cube is an odd permutation of the edges. Leaving all the corner pieces the same is an even permutation (namely 0 moves). A single rotation of a cube edge works out to be an odd cycle of corners and edges (1 2 3 4) -> (4 1 2 3) is an odd permutation. Therefore, a single move on the cube does an odd parity move on both edges and corners. So there is no way to make a single edge swap while leaving the corners the same, since that would require an odd number of moves for the edge, but even for the corners. Similar arguments work for flipping edges, swapping corners and rotating a single corner.
I actually wrote a paper on this in college and the math is actually way deeper than is shown. For instance, if you rotate the board 90 degrees the puzzle that was solvable becomes unsolveable, and vice-versa. If you go to a different size board, things can get really strange, where rotating 90 degrees could make it solveable, but rotating the other direction makes it unsolveable.
Insertion sort for the win!! It may not give the most efficient path from start to target sequence, but it will always get to the target in at most n-squared time.
I had such a puzzle about 45 years ago and on the rear side were a couple of examples for solutions given. The option from 15 down to 1 was also shown, but clearly labelled as "Impossible".
The spiral works because 16 gets displaced by three places, which makes the parity odd. The reverse sequence is actually possible, if you end with the blank spot in the lower left
I know some of this intuitively from working with Rubik's cubes. If you took a 15 puzzle apart and changed it so tiles were in a different arrangement, you could probably get some of those impossible permutations. Changing your starting parameters can change your parity for the desired end state. An easier way to understand is that you can reach any permutation if the puzzle starts with it, then it's scrambled before attempting. You can always solve it if legal moves were used to arrange the starting arrangement. This is true of Rubik's cubes too. Mean trick: pop a piece off a cube and rotate it 180°, then put it back. Instant impossible cube.
I don't get why at 20:40 you can't just permutate the 12 with the 5. Then the 13 with the 6, and so on, it would be I think 11 permutations at most off the top of my head.
For anyone who may come across this looking for additional closure on the reverse sequence - As the video framed the problem, we should think of the blank space as square "16". In which case the reverse sequence puts the blank space at the top left; not the bottom right. Obviously that's not what they printed on the puzzle's package, but the sequence "16",15,14,13,...,4,3,2,1 is a possible permutation!
Seems that by this logic the sequence 15,14,13,12,10,9,8,7,6,5,4,3,2,16,1 would be possible, which is trivially the same as the desired permutation (just with the 1 shifted over to the corner)
Thanks, that answers an option question from my high school days. We were given the problem of programming this puzzle and creating a random starting position. I was aware of the problem of unsolvable configurations, so I could side step the issue by randomizing the starting position by starting from a valid configuration and permutating it with valid puzzle moves, but this creates a somewhat simple criterion.
What if you took the tiles out and cheated and achieved that impossible solution, and then attempted to use the puzzle and solve any of the other solutions? Are all the 'good' ones no longer possible? are the 'bad' ones possible now?
I found it very interesting that there was only two kinds of steps that could be made in the permutations . It reminded me of the music scale and chords that can be made of them.
When I was at University one of the Computer Science professors set us a task of writing a program to solve this puzzle - he was not happy when I (with the support of a Maths professor) pointer out that this was an impossible task! The reason as I remember it is to do with the alternating subgroup.
![[DRAGON BALL LEGENDS REVEALS ＆ STUFF] LEGENDS FESTIVAL 2024 Special Edition Part 1](http://i.ytimg.com/vi/mV5bGIswTtQ/mqdefault.jpg)
The animation of the puzzle is very well done, as usual the animations are always great and help us to follow along with what the mathematician is saying.
I'm lost without them!
Yeah, hooray for Pete McPartlan
And for including the number 4!!!
@@skakdosmer Yay! Thanks Lau!
This is the same reason I like 3 Blue 1 Brown
As a teen, I had a larger (7x7) version of the puzzle. It featured a picture of the Leonardo da Vinci's Vitruvian Man as the image. It turned out that there were two completely blank tiles which just happened to have opposite parity. So if you put the wrong identical tile into position, it was impossible to finish. It took me days to work that out.
When I was a kid I was one who was taught that these puzzles are called “Sam Loyd puzzles” because he invented them, but (quite recently!) I learned the truth that the puzzles predate the man, so I thank you, Numberphile, for reinforcing (confirming?) that information for me.
As an aside, when I was a little boy my cousin, who was in her early 50’s at the time, would impress me by solving 15 puzzles in the fewest moves and fastest times, and even now when she is a few days shy of her 96th birthday and suffering with dementia she can still solve these puzzles.
Wow that is crazy haha
Happy birthday to your cousin!
@@MW-tf9dt some people get married in very early age
Lots of aunts/uncles. There is a 30 year gap between me and my youngest cousin, 35 year gap between my oldest and youngest cousins.
Cousins don't have to be same generation.
Logic is so cool. Take a complicated looking problem, break it down, then prove all sorts of things in that simplified mental space
i mean it would've been cool if we were shown how the parity thing was proven, and why he gets to do transpositions that are clearly impossible given the rules/physical limitations of the game. wouldn't some of the "1 step transpositions" he did when he swapped numbers actually take an even number of steps in the game? wouldn't that actually change the overall parity?
@@alveolate the allowed transpositions are still transpositions, and therefore must have the same parity as a set of not allowed transpositions that get from a to b.
@@alveolate On @Delta 's comment, think of the allowed transpositions as a subset of all possible transpositions.
Yeah, it's fascinating. If somebody gave me that puzzle and told to figure out if it's possible configuration or not, I wouldn't have a slightest clue where to even begin. Yet the solution is so simple and elegant when explained.
I was sort of thinking the same thing about allowed transpositions before he got to his proof:
What if you played this in a 3D cube?, ND cube? A torus?
Those loosen the constraints of the 2D square, but his proof is more generic than any extra constraints you want to impose
This professor is amazingly easy to understand and listen to. Seems like a calm dude as well and can take his time to explain something. Nice vid!
I would take a guess and say that he is originally from South Africa!!
Fun anecdote: Sam Lloyd was not able to patent the puzzle because he could not submit a solution to the challenge.
Same thing happened when I tried to patent to my perpetual motion machine.
nahhhh! He just resigned as soon as he found out an ODD number of officers would consider his application.
@@bitcoinweasel9274 lol
@@bitcoinweasel9274 hahaha XD
Alternate title: Math Professor Forgets The Number 4
4:06
that bothered me more than i care to admit
@@SuperFpac i didnt notice xD one part of my brain dif but didnt care and then i saw it again XD
Plot twist: He's Mista in an alternate universe where he became a nerd
Great catch!
Saw that right away, and EEEEIIEHHH, it didnt bother me :P
"1, 2, 3, 5, ..." I think he's been working too much with the Fibonacci sequence lol
Wouldn't that be the Lucas numbers sequence?
@@europeankid98 No, Lucas numbers would be 2, 1, 3, 4, ...
Those are his very own numbers.
or looking too much on prime numbers.
@@europeankid98 I mean he didn't go from the beginning, but they're still Fibbonacci numbers in order
(0, 1,) 1, 2, 3, 5...
@@maksymisaiev1828 Prime numbers would be 2, 3, 5.
Instead of explicitly counting the lefts/rights/ups/downs for the blank space, I prefer giving the tray a checkerboard colouring. The blank space then changes colour every move, so must do an even number of moves to get back to the same colour (or same location).
*turns puzzle 90 degrees
Any chess player would also view it like this instinctively :)
Was my first instinct after trying to figure out if there was some weird rule about even and odd numbers.
That rule probably exists in 5x5 and 3x3 fields, but not in 4x4 ones.
Actually, the simplest way to think of it is that 0 is the fewest number of moves, because it is already in the correct position . 0 is even, so all are even.
@@noahlawler8042 that's what i was thinking as well :)
His way of writing "odd" is rather 1(mod2).
Bro, I can't even...
Even his way of writing 1 mod 2 is odd to me! 1 % 2
That's quite odd
@Shawnaldo75 But you can though.
Dargonhuman bro i cant 0(mod2).
I graduated with a math degree about five years ago and don’t get to do math everyday like I did in school. The COVID-19 pandemic and shelter in place has given me an opportunity to pull out my old textbooks and think about things I love so much again.
I had my abstract algebra book out last weekend and was reading and thinking about permutations and parity.
Thanks for sharing this. Made my heart pitter patter. ❤️
We had one when I was young where the reverse order was labeled "unmöglich". (Presumably the puzzle was from Germany. :) ) I always wondered why, back then.
@Ron Maimon the video doesn't proof it but it also doesn't assume it. It already has been proven by others...
An easier proof would be inductive
@@squeakybunny2776 that's flat out wrong. For his argument, YES, it was assumed.
A statement without proof is by definition an assumption, axiom, postulate, premise, or condition.
@@boghag I thought all finite/discreet maths was inductive?
Rick Stevens perhaps, but an “inductive proof” is a specific kind of argument used when proving a specific theorem.
It took this video to make me finally understand where the word "parity" comes from - it's whether things are all "paired" up!
More precisely, "pair" and "parity" both come from the same root, a word meaning "equal".
I always heard that word in cubing and now I associate it with "The annoying thing that happens when using the reduction method"
There's a more devious version -- instead of 1-15, the tiles say "RATE YOUR MIND PAL" in horizontal rows. What you can do is show someone what it says and scramble the letters while they watch and challenge them to unscramble them. But what you do is put the "R" in YOUR into the upper left corner where the "R" in RATE should be. But you can't unscramble it that way -- the best you can do is RATE YOUR MIND PLA until you swap the Rs back.
That was amazing. I had such a puzzle as a kid and soon found out, that you can't have every configuration, but didn't know why. Now I know, i'm so happy :)
I actually discovered this and wrote a proof myself in high school. The assignment was actually to write a computer program to find the best next step in the puzzle. This was the early 1980s and we were learning Apple Basic. I fiddled with the example arrangement given and realized it couldn't be solved. So my immediate question was: which arrangements can be solved ash's which can't? I wrote a proof of why the given arrangement could not be solved and of which arrangements in general could and could not. (I had to invent my own language, bear in mind, because I was in high school and hadn't been exposed to most of the math involved yet.) And for my computer program, I wrote an algorithm to test whether the given arrangement was solvable at all, since setting your computer on an unsolvable problem would only serve to waste a lot of computing time until you gave up and aborted the program. :)
That is truly a genius! Apple Basic so can't be earlier than 1983! 37 years ago! It makes you proud today! Did you go on to do lot in maths? Btw, I was thinking on the same lines that such problems need to be given at the school level for children to realise some of the difficult mathematical concepts!
I agree, that IS genius! You're awesome.
@@chetrshah It can be earlier than 1983. If it was Integer Basic then 1977. If it was Applesoft Basic then 1978.
23 minutes of utter joy and happiness!
Thank mathematics.
Thanks RUclips.
Thanks world!
The back of the puzzle was clearly designed by Matt Parker
Maximilian Janisch I see what you did there
It’s not quite a square, missing a piece.
@@afwaller that would exactly make it a Parker Square though
Clearly not, because if it were designed by Matt Parker then he would have given it a go first and realized it was impossible.
Or if he were to put it there, then it would be to encourage the user to try it themselves and realize as he had that it was impossible.
@@sk8rdman im pretty sure this comment is a joke
wait this is my professor?? I saw the cover and was like "oh he looks familiar..."
hahahahah that must have been a weird surprise
which University?
Haha yeah that must have been a weird surprise lol
I-L-L
You can make a new friend :)
Beautiful solution!
Just read a book called "Tales of Impossibility", the puzzle from Sam Loyd was also discussed on Chapter 2. I am amazed of this kind of mathematical proof for its impossibility. Thanks Numberphile!
“I just take the tiles out” is the 15 puzzle version of “I just peel the stickers off” for Rubik’s Cubes
It's more like "I take it apart and put it back together" but you're on to something.
Ruibk's Cubes have parity cases as well. The 15 puzzle has 2 universes of possible combinations of its pieces, only one of which includes possible permutations given legal moves.
The Rubik's Cube has 12 universes of possible combinations of its pieces, so there are 11 ways to reconstruct it that are impossible to solve! If you were to take it apart and put the pieces back together randomly, then there's only a 1 in 12 chance that it would be solvable using legal moves!
In fact, this is how some scramble algorithm generators work. They reconstruct the cube with a random configuration, check for parity, and repeat until they get a legal permutation. Then they use an algorithm that finds the most efficient solution for that scramble, and give that to the user in reverse. This ensures that every possible legal permutation is equally likely to occur, and that the scramble is not affected by any bias that might result from just trying to make random turns until it "seems" scrambled.
@@sk8rdman But parity only exist on 4x4 or higher, On 3x3 there is no parity, except if you take it apart and you put it false together.
Everything can be solved by breaking them all put it back
The people who say "I just take the stickers off" wouldn't be so bad if they didn't think they were so special. Yeah, everyone takes the stickers off. 🙄
Dan Yeah, that’s true. Also, I didn’t know the stuff about scramble generators! I guess I learned something new today.
After a bit of playing around (physically and mathematically), it seems like every “unreachable” simplifies to being the 14 swap 15 problem (possibly with different values needing to swap, but that’s equivalent). So if we allow that move by some means, everything should be reachable! Makes me curious to think what states would be reachable on a Rubik’s cube if there existed a move to fix edge parity or corner parity.
I was terrible at math in school, and I haven't gotten any better as I've gotten older. And yet I find math absolutely fascinating. I love this channel...I find your videos mesmerizing.
And I feel so proud of myself when I have my aha moment during a video and understand what is being explained. 😀😀
Whenever someone comments: “I take the tiles out” you have just either made Brady’s prediction come true or messed it up.
Does your comment count as one of those comments or not? You've made his prediction kind of a philosophical one now
Schrodinger's Tile Puzzle Comment Analysis
Those are the two options
@@JM-us3fr Yeah this is tautological .
@@karlboud88 Even more vexing is that he predicted people would say "_I_ take the tiles out" but, what if I referenced another person, for example: "My cousin used to take the tiles out"?
YES! This is exactly my thoughts on the puzzle but written out. I didn't know how to prove it, but this explained it all so clearly. You can use a similar idea to prove that you can't switch only two pieces on a Rubik's cube!
To mess with a friend, I took one corner piece out of his Rubic's Cube and rotated it and put it back. Rubic's Cubes have a similar parity and by doing this, it became unsolvable. lol
A cuber would be able to tell when they get an unrecognizable OLL case
@darthvader_alex I get the feeling you've been waiting to tell people that you're a cuber ever since you became a cuber.
IIRC, Rubik's Cubes actually have 8 different orbits between which you can switch by removing and rotating pieces, as opposed to the 2 here.
You monster
We can tell you know....
But basically there isn't an OLL case to just rotate a corner alone, that's why we can see.
I just love how well-made that puzzle is. It looks beautiful.
On a historical note: do we know if Lloyd was aware of the mathematics, or was he actually risking losing $1000?
The proof follows easily from an understanding of the symmetric group and the alternating group within it, which had been understood for decades before. I imagine he didn't understand the proof, but knew the result.
I believe he made more money
He was the world's first troll ;)
I think he was aware of the math, and he trolled everyone into saying you can get $1000 if you solve it. But I might be wrong.
@@Albimar17 Trolls don't offer something of value.
Another interesting way to look at this is to imagine (or draw) a puzzle with the numbers from 1 to 3 and a blank square. The '1' is in the top left position, '2' in the top right position and '3' in the bottom left position. Now imagine you want to reverse the puzzle so that '3' is in the top left, '2' in the top right and '1 in the bottom left. As you move the pieces around, you can see that it is impossible to move the numbers so that they are no longer clockwise, but the solution you are trying to achieve has the numbers in an anti-clockwise formation. The same principle can be applied to the 4 x 4 puzzle, although its application is not as easy to see. This video does a great job of explaining it.
I remember this thing and hearing about how it couldn't be done lol. Of course this channel would dig into the minutiae of it. Love it.
My brother and I had a couple of these things. I pretty quickly realized that some combinations were impossible ... and also that you could pry out the plastic tiles and pop them back in, so as to get at the impossible ones. I did this to my brother's puzzle, and he could never get back to the original 1->15 arrangement. Drove him nuts for a week!
It's facinating that when you just switch two tiles, you will never be able to go to a setting that was previously possible. Like two universes existing next to each other, whose fabrics are intertwined without a possibility to transition from one to the other
This happens on twisty puzzles too and is usually called "orbits". What a fitting name to your description. :)
@@vinlebo88 I thought they were called orbitals. Are you sure?
This is why I love mathematics so much! You get deep insight into the problem by proving not just a single instance of a problem, but for ALL possible instances regardless of who you are. An alien from a different galaxy would still agree with us of the correctness, and they would come to the same conclusion IF they share or agree with our axioms.
This thing has always been my bane of existence among numerous things, including but not limited to Rubik's cube series.
This is basically a 4x4x0 Rubik's cube, heh. ("Rubik's cube", of course, being a misnomer for similar puzzles because most of them are neither cubes nor Rubik's brand.)
@Ranjit Tyagi naaahhh, he knows. Lol.
It's way easier than a Rubik's cube. You only need 1 strategy.
124X > 1234
XX3X > XXXX
After the first 2 rows you do the same starting on the left.
13 9 X X > 9 X X X
X X X X > 13 X X X
@@SgtSupaman i would argue it is a 2D cube
@@SgtSupaman yeah true. Idk if you are a cuber or not but if you know how the Rubik's cubes work then you know this puzzle actually works in the same way. There are odd/even parity and there are impossible permutations like flipped edge without moving any other edge.
What I love about this proof is that it simply never bothers properly translating the board into a mathematical form. It simply treats the reality of how you need to swap tiles as an implementation detail. So elegant!
James 'singingbanana' Grime also tackled this a long time ago.
I believe it was also mentioned in Simon Singh's book, although not in detail.
Is that why this felt like a reupload to me?
Now when you mention it I remember too
Yeah, but he didn't explain why it would require an odd number of moves to swap the 14 and 15 around. The explanation in this video is still incomplete as they didn't prove parity of permutations, but at least they mentioned it and they showed how it would imply that swapping the 14 and 15 would require an odd number of moves.
I am currently learning about Ring Theory and Group Theory in my Algebraic Structures class. In the class, we just talked about transpositions and permutations, so this video was absolutely fascinating!
I love hearing a fellow South African out in the wild!
A wild Saffa appears
you love to see it!
Right Heee
I was wondering what that accent was.
@@ratandmonkey2982 You can always tell an Afrikaans accent by the use of the word "ja" (pronounced "yaw"). He doesn't have a very strong accent, but the "ja" gives it away.
All moves must include swapping 16 with something else. Moving any other tile is optional, but moving 16 is compulsory. I didn't do math in high school (aside from what was basically required as part of the curriculum) yet these videos make numbers interesting!
Hello to all. So, if it is necessary to make even time of changes, then arrangement 1, 2, 3, 4,... 15, 16, 14 is possible!
After that we make one move more!
If 16 is one space away from it's original position then you need to have an odd number of changes.
1, 2, 3, 4,... 15, 16, 14 is not possible
But then that’s just an odd number of moves...
I like how the definition of odd is transcended and generalized in the generalization of the solution to the point it becomes mod2 and not anymore "odd". So mathematically genuine
Nothing is impossible until you add rules
So true, to solve a Rubik's cube is relatively simple until the rule prohibiting the disassembly of the cube is instituted.
Yet, even the solution of such a cube would seem to again become impossible, unless the disassembly rule doesn't actually include the peeling/removal of the colored stickers. But again, applying one's own stickers wouldn't be under the disassembly rule, now would it?
It's the rules which are the problem, not accomplishing the task requested.
Coloring within the lines most assuredly stunts the creativity of humanity.
Toss the rule books already! Don't worry, pop out those numbered tiles, make whatever configuration you want, & be happy!
@@WatchingMyLifeFlashB wise words!
If my theory is correct, I should be able to fly.
Can an elephant fly...there are an infinite number of impossibilities
@@WatchingMyLifeFlashB Rules are very important for creativity. For example if your painting is just blotches of colour that's pretty boring. Giving yourself rules to follow like using only these colours, only these shapes or that it must be as realistic as possible can lead to something a lot more interesting.
Very nice video, with beautiful animations!
However, I feel that the permutation parity should deserve a proof. It's not that hard; one of the easiest I can think of is counting the number of inversions of a permutation, and prove that for switching any two numbers in the permutation, the number of inversions changes its parity.
Let me share the proof with you; sorry if it's a bit technical, but you know - math is math! Besides, I'm sure it can be explained with animations more easily.
Let's say we have a permutation of n numbers:
p1, p2, ..., pi, ..., pj, ..., pn
where pk is the number at the k-th position.
Let's use the notation of {i,j} for positions with fixed order i pj, with i odd permutation.
THEOREM A: The parity of the number of inversions equals to the parity of the permutation.
THEOREM B we will prove: swap any two numbers in a permutation changes the parity of the number of inversions. Since the solved state has 0 number of inversions, which is even, and the solved state is an even permutation, this implies Theorem A.
PROOF:
Let be our permutation:
p1, p2, ..., pi, ..., pj, ..., pn
The second permutation is:
p'1, p'2, ..., p'i, ..., p'j, ..., p'n
Where pk = p'k except for positions i and j: p'i = pj and p'j = pi (we swapped pi and pj, and nothing else).
How does the number of inversion changes?
Let's see how the inversion-ness of the individual pairs changes after the swap. Each pair falls into one of three categories: A, B and C, described below. We will split B into further sub-categories B1, B2 and B3.
A) A pair is not affected by the swap. That is, if k!=i,j and l!=i,j with k
Surely you can prove that to get the 16 back where it starts simply by observing that zero is even? And thus the "do nothing" permutation is even.
That is *one* possible permutation, but it doesn't prove that every possible permutation has to be even. You get to do as many shuffles as you want. We want to see if, by following the rules of the puzzle, it is possible to get 16 back to where it was in an odd number of steps. It turns out it isn't.
I don't think a "do nothing" permutation exists/is valid, considering you could just do something like 123->312 with (1,3); (1,1); (2,3) and get an odd result if it was a thing.
@@zatherz2498 'Do nothing' is the identity permutation and is the composition of 0 transpositions (or 2,4,6, ...). But you're right that it is not a transposition because it does not switch two (distinct) elements.
@@zatherz2498 Actually your example only proves that the "do nothing" permutation is valid. The "do nothing" permutation would be 0 steps, therefore putting a (1,1) in would NOT make that 3 steps, because that swap is literally doing nothing, ie 0 steps, so you did 1 step, then 0 steps, then 1 step, that's a total of 2 steps, not 3.
@@phiefer3 i would say that swapping 1 with 1 is 1 definite step.
As a thought experiment, consider the fact that at some point you need to solve the last 2x2 section of the puzzle. Let's just pretend that's its own little puzzle that's numbered 1 through 3 with a space that I'll choose to call X. The correct arrangement would then be {1, 2, 3, X}. Your only moves in this case would move the space around the puzzle in clockwise or counterclockwise circles, and you could always return to the proper solved order.
Now, picture the same 2x2 puzzle but this time starting with the numbers in the top row switched, so the arrangement is {2, 1, 3, X}. Moving the space around the puzzle to get the 1 in the top left corner, you would only ever be able to get to {1, X, 2, 3}, {1, 3, 2, X}, or {1, 3, X, 2}. The tiles can keep going around in circles, but they'll never be in the right order with the 1 in the correct position!
You can see the limitation here pretty easily. Each position can swap with its 2 neighbors, but not the remaining position, which is its opposite corner.
Step 1: Take the new configuration
Step 2: Run quick sort on it
Step 3: Count the steps
Step 4: Check that the parity is right
Not quicksort, straight selection sort.
Bogo sort
I used to have one of these when I was a kid, got extremely good at it, and that metal one was sooooooo satisfying to use
Odd squares go to left, even squares go to right. Seven and eight are whelp squares.
Theres a loose 16! Handle it!
No more hops! MORE HOPS!
Oh man. Never thought I'd see a reference like that these days. Thanks, that made my day. And remember, whatever you do, do not stand next to other people!
What are you referencing?
@@NoriMori1992 WoW Onyxia raid meme.
When I played this at about 12, I suspected there were two groups of incompatible permutations. I am 57 now and you finally proved me right. :-)
Bought the puzzle with your link. I love little things like that. Great video btw!
This is a great video. Has a great balance of some actual mathematical insight but also being accessible.
That was an awesome proof explained very well, thank you Professor!
I had also played the the picture version of the puzzle. Nice to recall those memories.
22:32 solution to spiral arrangement
Based on the theorems provided, it looks like top row of 15, 14, 13, 16 then counting down normally is theoretically possible.
1) Counting down requires an odd parity.
2) Moving the 16 up one space at a time takes 12 moves, which maintains parity (19, odd).
3) Moving the square to the top-right space takes three singular-square movements, meaning solutions that put the square in the top-right all use an odd parity to solve them.
We want to see a proof of Fact 2. Inquiring minds must know.
Just check the parity of a permutation on wiki, and you will get it. It is pretty straightforward
I figured it out two years ago while creating a sliding puzzle game in JavaScript which actually is available in my youtube channel too. There I was creating initial setup randomly and then recognised, not every permutation gives correct Answer
"Let's call this blank square 16"
Programmers: *angery noises*
I was really expecting him to call it 0
I actually did make a little growl.
At least it was round number :)
at least it was not √-1
I made a disapproving sigh
The other interesting thing is how universal this puzzle is. Whether discussing seating plans, rearranging furniture, ordering choir robes, the phrase "it's one of those 15 square puzzles" is instantly understood by everyone. Whether that understanding brings hope or despair is less universal.
What they were thinking? You’re giving them too much credit. Odds are, they weren’t even thinking, because it was marketing that put it in there.
Most likely, yes. My guess is the graphic artist had to fill the space, thought "Hm, reversing the order would be aesthetically pleasing" then just moved the tiles around in Photoshop without checking to see if the solution was even possible.
I have a copy of the metal one (which is soooooo satisfying to play with if you like the sound of steel sliding on steel...) and it came with a booklet of something like 20 or 30 different permutations to try, and the one they were testing was literally the second suggestion.
It took me years of my life to figure out to get it in certain layouts or even just solve it, but I'm proud that I taught myself to solve this puzzle.
And the thing I like about these types of puzzles is that the algorithm scales as it gets bigger. It's pretty much the same even on a 5x5 or 6x6 or even bigger. Also it works on rectangular puzzles but I'm not sure if there's a way to know if a certain rectangular layout is solvable.
I love his handwriting
WOW! The brilliancy in modeling the problem! WOW!
This seems wierdly incomplete. It reduced the problem to proving that permutations have a parity. But it doesn't even try to give an intuition of why that is the case. Also it seems to make the statement that with the allowed moves every configuration with correct parity is possible, but it doesn't make any argument why that follows from the rules.
YES. Missed that too. It's probably a fact, but why?
You can see S. Muralidharan (2017) The Fifteen Puzzle-A New Approach, Mathematics
Magazine, 90:1, 48-57, DOI: 10.4169/math.mag.90.1.48
@@muralidharansomasundaram1509 Actually I can't see, it's paywalled... but thanks
@@StefanReich i can send it to you. What is your email?
Kudos to the *graphics designer* on this video as well
I always thought that the clever thing about this puzzle was constructing it so the tiles don't just fall out. (I'm an engineer.)
an engineer?
pi = e = 3
pi^2 = g
Tbf isnt that complex, isnt it just slots in each piece?
Rubik's cubes blew my mind as a child for this reason. Genius engineering
@@demonsheadshot8086 Not the metal one; I own one and took some tiles off just to see how it worked. Each spot on the tray has a square protrusion on it that looks something like a mushroom head (I'm sure there's a technical term for it but I'm not an engineer so I have no idea what it is...) in the middle. Each tile has a grip arm on the corner that hooks underneath the top of the mushroom head and the sides are hollow so the hooks will always be under a protrusion.
In honesty, it's so well designed that I nearly broke mine trying to get one of the tiles off to see how it worked - as it stands, the protrusion for the blank "16" spot wiggles a bit where I had to bend it.
EDIT: I incorrectly described the design of the tiles; I was thinking of a completely different puzzle when I wrote that.
Okay I gotta admit that although Numberphile videos are quite easy to understand, this one I actually actually feel like I understood (taking the facts as granted, that is). Great video with both entertainment and educational value, once again! Bravo!
So if you create one with the numbers in reverse order you can't make it so that the numbers are in the correct order?
Unless the open square is also at the start
That is correct, because every permutation is invertible.
@@alephnull4044 haha baby infinity
Basically, yes. If you start with the normal order and try to do the reverse as shown on the packaging, 14 and 15 will always be inverted. If you were to take it apart and start with 15 in the upper left and tried to solve it back to normal, 14 and 15 would still be inverted simply because the parity is wrong - the only way to truly reverse the tiles is to move the blank 16 spot from the lower right to the upper left and rearrange the tiles around it.
In other words, it doesn't matter what the starting arrangement is, it will be impossible to reverse their order and keep the blank 16 in the same spot.
I loved that puzzle when I was a kid but never thought about it this deeply.
We have proven, that it's always an impossible task when the parities are different, but we have not proven that it's always possible when the parities are different.
I think you meant to say "... not proven ... parities are same".
Yes taking the 15-16 swapped configuration and then making just one more move will balance out the parity, but doesn't make it any more possible. It'd be nice to know if/how a configuration could be proven to be impossible even if the parities don't match.
"If it hasn't been done that just means you haven't proven it to be impossible yet."
I think I just found my new life motto.
@@marzipancutter8144 I van relate: If one year of studying maths taucht ne anything, it is that destructive proofs are mostly easier than constructive ones.
My 11 year old and I have been racking our brains trying to figure out this new puzzle and why we could not do it backwards. Finally I googled my issue and this immediately appears with the title saying it’s not possible. Saved me much time in throwing in the towel. Funny, because we just assumed any combination was possible.
this is lovely!
I'd like to see this done to prove some Rubicks cube patterns are not possible.
Switching two edges on the cube is an odd permutation of the edges. Leaving all the corner pieces the same is an even permutation (namely 0 moves). A single rotation of a cube edge works out to be an odd cycle of corners and edges (1 2 3 4) -> (4 1 2 3) is an odd permutation. Therefore, a single move on the cube does an odd parity move on both edges and corners. So there is no way to make a single edge swap while leaving the corners the same, since that would require an odd number of moves for the edge, but even for the corners. Similar arguments work for flipping edges, swapping corners and rotating a single corner.
Thanks numberphile, I keep wondering about this puzzle and found this video on youtube, now I know why I can't get the arrangement of 15 to 1
4:17 He forgot number 4
Mista is pleased
Edit: also 4:07
Technically he only forgot to write it once
I spotted that right away and hit rewind!
My eyes were bleeding cuz of that
You are now a *Mathemate-chinas*
I had to reply to this comment because otherwise there'd pnly be 4 replies
I actually wrote a paper on this in college and the math is actually way deeper than is shown. For instance, if you rotate the board 90 degrees the puzzle that was solvable becomes unsolveable, and vice-versa. If you go to a different size board, things can get really strange, where rotating 90 degrees could make it solveable, but rotating the other direction makes it unsolveable.
.il
I remember the first time seeing this puzzle was in Super Mario 64 in the Lethal Lava Land course!
That was the Voice Of Puzzles! If all Puzzles had a Narrator, 'Professor Steven Bradlow' would be that voice.
Interesting way to prove zero is even!
@kozi0404 because doing zero transpositions is an even permutation
Insertion sort for the win!!
It may not give the most efficient path from start to target sequence, but it will always get to the target in at most n-squared time.
Is that a South African I hear??
Certainly sounds it. Been in the US for a while from the bio information.
yeah he is, he has a link to the south africans abroad website in his bio.
This is useful for understanding how certain arrangements of a Rubiks cube arent possible
4:08 some people just dont like number 4
I had such a puzzle about 45 years ago and on the rear side were a couple of examples for solutions given. The option from 15 down to 1 was also shown, but clearly labelled as "Impossible".
I love this puzzle. This is my favorite puzzle ever
same here!
OK.
Slidysim might be for you then!
The spiral works because 16 gets displaced by three places, which makes the parity odd.
The reverse sequence is actually possible, if you end with the blank spot in the lower left
Thank you cause I just did it twice and I can do it again it's actually super simple
"I'm waiting for someone to comment 'I just take the tiles out'"
*Laughs in peels the stickers
Only Cubers will understand
A high quality version of the toy should prevent you from vertical movements. So the real solution is to cheap out.
Imagine trying to peel stickers omegalul
@@MatthewLiuCube an expert cuber will be able to rearrange the cube back a lot faster than you can peel and repaste stickers.....lol
@@mingming9604 lol you realize im a cuber. What is your average? Mine is 20.
This is one of the best numberphile videos ever published. Well done!
*An impossible arrangement of numbers in a square?*
(Matt Parker left the chat)
I read too many comments like this before I realized people weren't talking about a South Park creator
I know some of this intuitively from working with Rubik's cubes. If you took a 15 puzzle apart and changed it so tiles were in a different arrangement, you could probably get some of those impossible permutations. Changing your starting parameters can change your parity for the desired end state. An easier way to understand is that you can reach any permutation if the puzzle starts with it, then it's scrambled before attempting. You can always solve it if legal moves were used to arrange the starting arrangement. This is true of Rubik's cubes too. Mean trick: pop a piece off a cube and rotate it 180°, then put it back. Instant impossible cube.
I don't get why at 20:40 you can't just permutate the 12 with the 5. Then the 13 with the 6, and so on, it would be I think 11 permutations at most off the top of my head.
That part was confusing, but I belive you can just permutate from a distance indeed since we're just evaluating the parity.
For anyone who may come across this looking for additional closure on the reverse sequence - As the video framed the problem, we should think of the blank space as square "16". In which case the reverse sequence puts the blank space at the top left; not the bottom right. Obviously that's not what they printed on the puzzle's package, but the sequence "16",15,14,13,...,4,3,2,1 is a possible permutation!
I think I once tried to do it backwards but I thought I was just too dumb to figure it out, lol
Seems that by this logic the sequence 15,14,13,12,10,9,8,7,6,5,4,3,2,16,1 would be possible, which is trivially the same as the desired permutation (just with the 1 shifted over to the corner)
Already a dislike? Hater has their notifications on
Kasa Jizo M I S C L I C K
or the creators follows the channel
@@sammy-tj7br oh so *you're* the culprit?! Jk
I love to think that
Thanks, that answers an option question from my high school days. We were given the problem of programming this puzzle and creating a random starting position. I was aware of the problem of unsolvable configurations, so I could side step the issue by randomizing the starting position by starting from a valid configuration and permutating it with valid puzzle moves, but this creates a somewhat simple criterion.
What if you took the tiles out and cheated and achieved that impossible solution, and then attempted to use the puzzle and solve any of the other solutions? Are all the 'good' ones no longer possible? are the 'bad' ones possible now?
yeah
I found it very interesting that there was only two kinds of steps that could be made in the permutations . It reminded me of the music scale and chords that can be made of them.
The fact that the blank is 16 rather than zero bothers me much, much more than it ought to.
Yeah, why not order the numbers 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0
When I was at University one of the Computer Science professors set us a task of writing a program to solve this puzzle - he was not happy when I (with the support of a Maths professor) pointer out that this was an impossible task! The reason as I remember it is to do with the alternating subgroup.