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.

@wesss9353

4 жыл бұрын

I'm lost without them!

@skakdosmer

4 жыл бұрын

Yeah, hooray for Pete McPartlan

@andytc4840

4 жыл бұрын

And for including the number 4!!!

@pmcpartlan

4 жыл бұрын

@@skakdosmer Yay! Thanks Lau!

@gelgamath_9903

4 жыл бұрын

This is the same reason I like 3 Blue 1 Brown

Fun anecdote: Sam Lloyd was not able to patent the puzzle because he could not submit a solution to the challenge.

@bitcoinweasel9274

4 жыл бұрын

Same thing happened when I tried to patent to my perpetual motion machine.

@Albimar17

4 жыл бұрын

nahhhh! He just resigned as soon as he found out an ODD number of officers would consider his application.

@goldenwarrior1186

2 жыл бұрын

@@bitcoinweasel9274 lol

@shadow_navneet

Жыл бұрын

@@bitcoinweasel9274 hahaha XD

"1, 2, 3, 5, ..." I think he's been working too much with the Fibonacci sequence lol

@europeankid98

4 жыл бұрын

Wouldn't that be the Lucas numbers sequence?

@lumer2b

4 жыл бұрын

@@europeankid98 No, Lucas numbers would be 2, 1, 3, 4, ... Those are his very own numbers.

@maksymisaiev1828

4 жыл бұрын

or looking too much on prime numbers.

@zozzy4630

4 жыл бұрын

@@europeankid98 I mean he didn't go from the beginning, but they're still Fibbonacci numbers in order (0, 1,) 1, 2, 3, 5...

@animikhaduttadhar2284

4 жыл бұрын

@@maksymisaiev1828 Prime numbers would be 2, 3, 5.

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.

Alternate title: Math Professor Forgets The Number 4 4:06

@SuperFpac

4 жыл бұрын

that bothered me more than i care to admit

@nusae2156

4 жыл бұрын

@@SuperFpac i didnt notice xD one part of my brain dif but didnt care and then i saw it again XD

@nanamacapagal8342

4 жыл бұрын

Plot twist: He's Mista in an alternate universe where he became a nerd

@gnarkill32

4 жыл бұрын

Great catch!

@Rakii27

4 жыл бұрын

Saw that right away, and EEEEIIEHHH, it didnt bother me :P

Logic is so cool. Take a complicated looking problem, break it down, then prove all sorts of things in that simplified mental space

@alveolate

4 жыл бұрын

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?

@delta3244

4 жыл бұрын

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

@RedBar3D

4 жыл бұрын

@@alveolate On @Delta 's comment, think of the allowed transpositions as a subset of all possible transpositions.

@Blackreaper777

4 жыл бұрын

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.

@PerfectlyNormalBeast

4 жыл бұрын

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

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.

@pkmath12345

4 жыл бұрын

Wow that is crazy haha

@nymalous3428

4 жыл бұрын

Happy birthday to your cousin!

@mohammadazad8350

4 жыл бұрын

@@MW-tf9dt some people get married in very early age

@hawki52

4 жыл бұрын

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.

@ubertoaster99

4 жыл бұрын

Cousins don't have to be same generation.

The back of the puzzle was clearly designed by Matt Parker

@Playmaker6174

4 жыл бұрын

Maximilian Janisch I see what you did there

@afwaller

4 жыл бұрын

It’s not quite a square, missing a piece.

@AnCoSt1

4 жыл бұрын

@@afwaller that would exactly make it a Parker Square though

@sk8rdman

4 жыл бұрын

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.

@NoOne-wz2ht

3 жыл бұрын

@@sk8rdman im pretty sure this comment is a joke

His way of writing "odd" is rather 1(mod2).

@Dargonhuman

4 жыл бұрын

Bro, I can't even...

@GEM4sta

4 жыл бұрын

Even his way of writing 1 mod 2 is odd to me! 1 % 2

@Kyo_Tran

4 жыл бұрын

That's quite odd

@8bit_pineapple

3 жыл бұрын

@Shawnaldo75 But you can though.

@dagan5698

3 жыл бұрын

Dargonhuman bro i cant 0(mod2).

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!

@elektrolyte

Жыл бұрын

I would take a guess and say that he is originally from South Africa!!

wait this is my professor?? I saw the cover and was like "oh he looks familiar..."

@hubert6943

4 жыл бұрын

hahahahah that must have been a weird surprise

@SR-kd4wi

4 жыл бұрын

which University?

@pkmath12345

4 жыл бұрын

Haha yeah that must have been a weird surprise lol

@Maazin5

4 жыл бұрын

I-L-L

@horacio6537

4 жыл бұрын

You can make a new friend :)

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

@JNCressey

4 жыл бұрын

*turns puzzle 90 degrees

@alephnull4044

4 жыл бұрын

Any chess player would also view it like this instinctively :)

@naphackDT

4 жыл бұрын

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.

@noahlawler8042

3 жыл бұрын

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.

@julbarrier

2 жыл бұрын

@@noahlawler8042 that's what i was thinking as well :)

“I just take the tiles out” is the 15 puzzle version of “I just peel the stickers off” for Rubik’s Cubes

@sk8rdman

4 жыл бұрын

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.

@drkuuljulian

4 жыл бұрын

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

@m1nus1623

4 жыл бұрын

Everything can be solved by breaking them all put it back

@malcolmw513

4 жыл бұрын

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

@goldenwarrior1186

4 жыл бұрын

Dan Yeah, that’s true. Also, I didn’t know the stuff about scramble generators! I guess I learned something new today.

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

4 жыл бұрын

@Ron Maimon the video doesn't proof it but it also doesn't assume it. It already has been proven by others...

@boghag

4 жыл бұрын

An easier proof would be inductive

@rickstevens1167

4 жыл бұрын

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

@rickstevens1167

4 жыл бұрын

@@boghag I thought all finite/discreet maths was inductive?

@jaymalby

4 жыл бұрын

Rick Stevens perhaps, but an “inductive proof” is a specific kind of argument used when proving a specific theorem.

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. ❤️

It took this video to make me finally understand where the word "parity" comes from - it's whether things are all "paired" up!

@NoriMori1992

4 жыл бұрын

More precisely, "pair" and "parity" both come from the same root, a word meaning "equal".

@ClawedAsh

4 жыл бұрын

I always heard that word in cubing and now I associate it with "The annoying thing that happens when using the reduction method"

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

@chetrshah

4 жыл бұрын

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!

@kathrynneuman1079

4 жыл бұрын

I agree, that IS genius! You're awesome.

@cbnewham5633

3 жыл бұрын

@@chetrshah It can be earlier than 1983. If it was Integer Basic then 1977. If it was Applesoft Basic then 1978.

Beautiful solution!

Whenever someone comments: “I take the tiles out” you have just either made Brady’s prediction come true or messed it up.

@karlboud88

4 жыл бұрын

Does your comment count as one of those comments or not? You've made his prediction kind of a philosophical one now

@davidfinch7418

4 жыл бұрын

Schrodinger's Tile Puzzle Comment Analysis

@JM-us3fr

4 жыл бұрын

Those are the two options

@acruzp

4 жыл бұрын

@@JM-us3fr Yeah this is tautological .

@NortheastGamer

4 жыл бұрын

@@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"?

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!

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

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.

On a historical note: do we know if Lloyd was aware of the mathematics, or was he actually risking losing $1000?

@asdasd-ho3mm

4 жыл бұрын

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.

@GreenLyfe00

4 жыл бұрын

I believe he made more money

@Albimar17

4 жыл бұрын

He was the world's first troll ;)

@SimonTiger

3 жыл бұрын

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.

@blazarchzagnatz7506

3 жыл бұрын

@@Albimar17 Trolls don't offer something of value.

I just love how well-made that puzzle is. It looks beautiful.

23 minutes of utter joy and happiness! Thank mathematics. Thanks KZread. Thanks world!

Nothing is impossible until you add rules

@WatchingMyLifeFlashB

4 жыл бұрын

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!

@martinpaar775

4 жыл бұрын

@@WatchingMyLifeFlashB wise words!

@MushookieMan

4 жыл бұрын

If my theory is correct, I should be able to fly.

@reedmorris6559

4 жыл бұрын

Can an elephant fly...there are an infinite number of impossibilities

@00wolfer00

4 жыл бұрын

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

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

@SpaghettiRuin

4 жыл бұрын

A cuber would be able to tell when they get an unrecognizable OLL case

@NortheastGamer

4 жыл бұрын

@darthvader_alex I get the feeling you've been waiting to tell people that you're a cuber ever since you became a cuber.

@Kalobi

4 жыл бұрын

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.

@djapa9453

3 жыл бұрын

You monster

@Giyga

3 жыл бұрын

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

"Let's call this blank square 16" Programmers: *angery noises*

@Omar-bi9zn

3 жыл бұрын

I was really expecting him to call it 0

@MrTridac

3 жыл бұрын

I actually did make a little growl.

@petrkubena

3 жыл бұрын

At least it was round number :)

@fxnoob

3 жыл бұрын

at least it was not √-1

@doggo7567

3 жыл бұрын

I made a disapproving sigh

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.

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!

Great video as always, and the animations are incredible, it makes very easier to follow the mathematician.

Genuinely interesting from start to finish.

That was an awesome proof explained very well, thank you Professor!

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!

This is one of the best numberphile videos ever published. Well done!

James 'singingbanana' Grime also tackled this a long time ago.

@leadnitrate2194

4 жыл бұрын

I believe it was also mentioned in Simon Singh's book, although not in detail.

@corpsiecorpsie_the_original

4 жыл бұрын

Is that why this felt like a reupload to me?

@jimi02468

4 жыл бұрын

Now when you mention it I remember too

@anticorncob6

3 жыл бұрын

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.

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

@vinlebo88

4 жыл бұрын

This happens on twisty puzzles too and is usually called "orbits". What a fitting name to your description. :)

@kilroy1964

4 жыл бұрын

@@vinlebo88 I thought they were called orbitals. Are you sure?

This is a great video. Has a great balance of some actual mathematical insight but also being accessible.

I had also played the the picture version of the puzzle. Nice to recall those memories.

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.

@Dargonhuman

4 жыл бұрын

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.

Bought the puzzle with your link. I love little things like that. Great video btw!

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.

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

I love hearing a fellow South African out in the wild!

@wadepotts4062

4 жыл бұрын

A wild Saffa appears

@UncoveredTruths

4 жыл бұрын

you love to see it!

@yuvalperry6688

4 жыл бұрын

Right Heee

@ratandmonkey2982

4 жыл бұрын

I was wondering what that accent was.

@18booma

4 жыл бұрын

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

This thing has always been my bane of existence among numerous things, including but not limited to Rubik's cube series.

@SgtSupaman

4 жыл бұрын

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

@ianmoore5502

4 жыл бұрын

@Ranjit Tyagi naaahhh, he knows. Lol.

@MrSquirrelsMan

4 жыл бұрын

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

@Royvan7

4 жыл бұрын

@@SgtSupaman i would argue it is a 2D cube

@chessbitz6846

4 жыл бұрын

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

Loved the animation on this video, as well as the cool explanation!

I still have one of these with the original manual and red leather case, mint condition! Just as fun now as it was when it was given to me perhaps 20 years ago now. Impossible combinations quickly become obvious as such when you play with it, but it's awesome to finally see a mathematical explanation WHY they can't be done. Also, certainly these theorems have plenty of applications besides the 15 puzzle! Great video, thank you, keep doing what you're doing! :)

Odd squares go to left, even squares go to right. Seven and eight are whelp squares.

@dirtdart81

4 жыл бұрын

Theres a loose 16! Handle it!

@runeboas6421

4 жыл бұрын

No more hops! MORE HOPS!

@SeriousMoh

4 жыл бұрын

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!

@NoriMori1992

4 жыл бұрын

What are you referencing?

@SearinoxNavras

4 жыл бұрын

@@NoriMori1992 WoW Onyxia raid meme.

"I'm waiting for someone to comment 'I just take the tiles out'" *Laughs in peels the stickers

@MatthewLiuCube

4 жыл бұрын

Only Cubers will understand

@SenshiSunPower

4 жыл бұрын

A high quality version of the toy should prevent you from vertical movements. So the real solution is to cheap out.

@demonsheadshot8086

4 жыл бұрын

Imagine trying to peel stickers omegalul

@mingming9604

4 жыл бұрын

@@MatthewLiuCube an expert cuber will be able to rearrange the cube back a lot faster than you can peel and repaste stickers.....lol

@MatthewLiuCube

4 жыл бұрын

@@mingming9604 lol you realize im a cuber. What is your average? Mine is 20.

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!

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.

22:32 solution to spiral arrangement

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!

@marzipancutter8144

4 жыл бұрын

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

@Johnof1000Suns

3 жыл бұрын

But then that’s just an odd number of moves...

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.

brilliant & thank you Numberphile, my fav KZread channel without doubt

this is lovely! I'd like to see this done to prove some Rubicks cube patterns are not possible.

@rmidthun

4 жыл бұрын

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.

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

@cassidydude

4 жыл бұрын

Not quicksort, straight selection sort.

@dimitrijat

3 жыл бұрын

Bogo sort

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!

Hey Numberphile! Love your videos, thank you for existing! Interesting idea for the next one: the strange properties of the infinite power tower :) my mind was blown recently by this problem.

I love this puzzle. This is my favorite puzzle ever

@Brunoenribeiro

4 жыл бұрын

same here!

@sahilbaori9052

4 жыл бұрын

OK.

@ianmoore5502

4 жыл бұрын

Slidysim might be for you then!

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.

@sonayyalim

4 жыл бұрын

I think you meant to say "... not proven ... parities are same".

@danno1111

4 жыл бұрын

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

4 жыл бұрын

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

@BedrockBlocker

4 жыл бұрын

@@marzipancutter8144 I van relate: If one year of studying maths taucht ne anything, it is that destructive proofs are mostly easier than constructive ones.

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

WOW! The brilliancy in modeling the problem! WOW!

The fact that the blank is 16 rather than zero bothers me much, much more than it ought to.

@peacefroglorax875

4 жыл бұрын

Yeah, why not order the numbers 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0

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?

@kut52

4 жыл бұрын

Unless the open square is also at the start

@alephnull4044

4 жыл бұрын

That is correct, because every permutation is invertible.

@xue1379

4 жыл бұрын

@@alephnull4044 haha baby infinity

@Dargonhuman

4 жыл бұрын

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.

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!

Awesome video. I took the time to check if the Vertical Odd/Even configuration was possible, and it is.

I love his handwriting

4:17 He forgot number 4 Mista is pleased Edit: also 4:07

@oliverolsen1120

4 жыл бұрын

Technically he only forgot to write it once

@mike65535

4 жыл бұрын

I spotted that right away and hit rewind!

@ilyxad6121

4 жыл бұрын

My eyes were bleeding cuz of that

@sanatanmeaning

4 жыл бұрын

You are now a *Mathemate-chinas*

@stormbreaker_101

4 жыл бұрын

I had to reply to this comment because otherwise there'd pnly be 4 replies

I love the groups theory even if I'm not an expert in this field. I always wanted to learn model algebra when I was a student but unfortunately I couldn't even though I've tried to teach myself reading many books. Great video, you remind me of how much I love this theory.

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

We want to see a proof of Fact 2. Inquiring minds must know.

@weibingchen4183

4 жыл бұрын

Just check the parity of a permutation on wiki, and you will get it. It is pretty straightforward

I think I once tried to do it backwards but I thought I was just too dumb to figure it out, lol

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.

great explanation thank you so much and please we need more

I remember the first time seeing this puzzle was in Super Mario 64 in the Lethal Lava Land course!

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.

@StefanReich

4 жыл бұрын

YES. Missed that too. It's probably a fact, but why?

@muralidharansomasundaram1509

4 жыл бұрын

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

@StefanReich

4 жыл бұрын

@@muralidharansomasundaram1509 Actually I can't see, it's paywalled... but thanks

@muralidharansomasundaram1509

4 жыл бұрын

@@StefanReich i can send it to you. What is your email?

reminds me of the bridge problem, isn't that pretty much the same? it's the one with the klein bottle loving ol' dude. pure gold.

Excellent explanation. Thank you!

*An impossible arrangement of numbers in a square?* (Matt Parker left the chat)

@CrackedDota

4 жыл бұрын

I read too many comments like this before I realized people weren't talking about a South Park creator

Another awesome video! Always great content. Amazing channel. You’ve inspired me to start my own math channel.

I loved that puzzle when I was a kid but never thought about it this deeply.

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.

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.

@hyreonk

4 жыл бұрын

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.

@zatherz2498

4 жыл бұрын

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.

@alephnull4044

4 жыл бұрын

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

@phiefer3

4 жыл бұрын

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

@RodelIturalde

4 жыл бұрын

@@phiefer3 i would say that swapping 1 with 1 is 1 definite step.

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

@Ethan-mj6wy

4 жыл бұрын

an engineer? pi = e = 3 pi^2 = g

@demonsheadshot8086

4 жыл бұрын

Tbf isnt that complex, isnt it just slots in each piece?

@digama0

4 жыл бұрын

Rubik's cubes blew my mind as a child for this reason. Genius engineering

@Dargonhuman

4 жыл бұрын

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

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.

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

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?

@dphdmn

4 жыл бұрын

yeah

Is that a South African I hear??

@jfa849

4 жыл бұрын

Certainly sounds it. Been in the US for a while from the bio information.

@theuniechamberlain7643

3 жыл бұрын

yeah he is, he has a link to the south africans abroad website in his bio.

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!

thx for the video. It was very entertaining. I had this game as a kid and I loved it. As a kid, I of course didn't understand why some combinations are not possible. After studying computer science, I have the knowledge to understand this now, but I was never thinking about this game since 40 years. It's nice to be remembered about these little things in the daily life and how you can explain them with math :). I really tend to forget this.

@Numberphile Now I am curious about the "God's number" of this puzzle, or rather the maximum number of transpositions necessary to get from any given possible configuration to any other configuration.

@MarcRidders

4 жыл бұрын

I think you mean the "minimum number of transpositions"?

@lucianoosinaga2980

4 жыл бұрын

@@MarcRidders no i think he means the maximum number of moves you could ever need to solve. That is, how many moves would it take to unscramble a maximally scrambled configuration

@chaoticoli09

4 жыл бұрын

Luciano Osinaga yes Luciano has what I had in mind .

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.

@ghislainbugnicourt3709

4 жыл бұрын

That part was confusing, but I belive you can just permutate from a distance indeed since we're just evaluating the parity.

Great video! I love the editing! And hilarious joke at the end!

I remember the windows vista/7 desktop gadget that had this puzzle, but it was shuffled randomly and sometimes when you tried solving it ended up in the 15,14 configuration. Through trying again and again to swap 15 and 14 i eventually figured it had to be impossible to do so. Now i know that maths has confirmed this

Me, a Runescape clue scroll expert: HAH

@Atlasm2p

4 жыл бұрын

I see you are a man of grind a man of monkey fcking madness

@SSDragon19

4 жыл бұрын

same, i miss those days

4:08 some people just dont like number 4

Kudos to the *graphics designer* on this video as well

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.