No video
Princess in the Castle | A puzzle with a visual solution | 3blue1brown SoME1 submission
A math puzzle made easy with a fantastic visualization!
This video was uploaded as part of the 3Blue1Brown Summer of Math Exposition (SoME1) Contest. Link to contest:
www.3blue1brow...
For discussion on extensions, see:
checkmyworking...
Music was composed, played, recorded, and mixed by me.
Social media and web presence:
/ shudiptoamin
Пікірлер: 60
I've seen this puzzle before, solved it using polarity (princess must move from odd to even or even to odd room every night) but this 2d visualisation just makes that concept so easy see. Amazing video
@9thlife308
2 жыл бұрын
Thanks! yeah, that's what I tried at first, but couldn't wrap my head around it until I stumbled upon the grid representation.
This problem is an excellent reminder of the utility of *invariants* in problem solving. In this case, the fact that the color of the princess's square is always the same as that of her original position. It essentially cuts the problem in half, and now one can make some headway by considering each subcase one by one.
@9thlife308
2 жыл бұрын
True! Invariants seem to be a pretty common theme not only in fun logic puzzles, but also in math/science research problems.
@Gna-rn7zx
Жыл бұрын
Could also be called "parity" in this two-state case.
plot twist: the princess is in another castle
In this puzzle, the princess is actually a bishop in disguise!
The price should just try and find another princess. She doesn't seem all that into him, and she got some weird issues
@fgvcosmic6752
2 жыл бұрын
She's got issues? Nah, *he's* got issues, trying to break into a girls room who has neither invited him nor shown interest, instead of just meeting her in the day
@franckdebank
Жыл бұрын
Nope actually the Prince is respectfully playing by the Princess own rules. And not by any paranoid disorder affected brain.
I like it! The main takeaway ("think in 2d") is well worth watching. And I like the music very much, simple but very appropriate - I'd say there's something medieval about it.
@9thlife308
2 жыл бұрын
Thanks!
What a fun puzzle! Fantastic explanation with appropriate visualization. I would love to see another video on extensions.
She's trying to avoid an alien abduction, but has difficulty moving all her luggage.
If the Princess were allowed to loop back around and move from one end to the other on one night, would the strategy change? Would it even be possible?
@9thlife308
2 жыл бұрын
Great question, actually it would be impossible with the current rules, as you wouldnt be able to eliminate any room the first day.
Awesome, I did not expect this to be so interesting
With a small number of rooms there is a high probability that she starts in either Room 1, 2 or 3, so if he starts in Room 2 but doesn't get lucky and catch her at the first attempt if she started there then if he stays there for the second night he isn't "wasting" a night so much as using that second stay to not only start eliminating future rooms but also to catch the Princess if she started in Room 1 or on average half the time if she was in Room 3. This then saves potentially having to go forward and then back through the entire algorithm on average one and a half out of n times just by adding one extra move.
Nice, the insight @ 3:51 then a clear exposition of the algorithm.
@9thlife308
2 жыл бұрын
Glad you liked it, thanks for the feedback!
I got Mathologer vibes at the end!
@9thlife308
2 жыл бұрын
I'll take that as a huge compliment, thanks!
SPOILER: Am I correct in saying that the maximum nights comes out to be (N-2)*2? Where N is the number of rooms. my reasoning is, by starting on a white corner square we've effectively cut off one piece, same goes for when we shift into the black square, meaning we can cut 2 from the starting value and because of the diagonal movement, we're constructing two right triangle, identical apart from being flipped, which is where I'm getting the *2 in my solution.
@01k
2 жыл бұрын
note, N > 2
@9thlife308
2 жыл бұрын
Yes, your reasoning is correct! For all N > 2, it is the case.
@9thlife308
2 жыл бұрын
It should be true for N=4 too, right?
@01k
2 жыл бұрын
@@9thlife308 Oh! I made an error
@ComputerRouter
2 жыл бұрын
Where N is the number of rooms, the Prince can be gaurentteed to find the Princess in at least: N=3, 2 nights N=4, 4 nights N=5, 6 nights N=6, 8 nights N=7,10 nights N=8, 12 nights I thinks this is 2N-4 The Prince never starts in a corner, nor visits the edge of the 2D board, representing the he never need visit the first nor last room
The fact that there is no shorter solution is not proved.
@9thlife308
2 жыл бұрын
I wasn't very clear about this - but the main idea is that on each night, if you don't make the optimal choice, which eliminates the maximum number of rooms in future, then you are either staying at the same state as you are in today, or you were on some previous night. So the shortest number of nights REMAINING for the following night would either stay the same or increase, instead of decreasing. It's not a proof, but hopefully convincing upon reflection.
I tried solving tjis and came up with the grid idea as my first thought. After some attempts at doing 4/5 i saw the parttern and sure enough i was able to figure it out. Did i do trial and error? Kinda but i still thought about making the move that would eliminate the most rooms and this pattern emerged, so id still count that.
u gain subscriber
Random recommendation but I like it
Can you explain the room elimination part in more detail? I kinda got lost there, awesome video nonetheless!
@9thlife308
2 жыл бұрын
Thanks for watching! I guess you are referring to 5:50. I guess the best way to go about it is to think backwards, how the princess could get to any given room. Obviously, on the previous night she would have to be either to the left or right of the room in question, in order to be able to move to that room. This is true for all rooms except the side rooms, which only have one adjacent room. So the prince only needs to visit that one room, to eliminate the possibility for the NEXT night. And the following night, you can the "side room" becomes the one adjacent to the room the prince eliminated. So you just repeat the same principle, shifting one room over. Hope that clears it up!
Nice one.
very good
Sweet
I was thinking about a different solution. If the prince starts with the left most room and moves one room to the right after spending two nights in each room, wouldn't he eventually meet the princes, because the roomtime graph she draws would cross his?
@9thlife308
2 жыл бұрын
no, because it is possible for the graphs to cross without them meeting each other. Imagine that the prince and princess are currently in adjacent rooms, and the night after, they simply swap places. Their paths would cross, but they wouldn't meet.
@nikitaarts2561
11 ай бұрын
@@9thlife308 I also thought in the direction of double-night crossing but it seems it works perfectly half of times. So it seems the whole 2(n-1) crossing still just eliminates one half of rooms just as your single crossing did with (n-2) nights. I'll make some graphs to prove it later.
@nikitaarts2561
11 ай бұрын
@@9thlife308 checked my version accurately. This arrogant princess would surely escape double cross, and we can't eliminate enough oprions. You were right.
"for some reason"
she get around
How about this riddle, but with countably infinite rooms, next? 😀 (Arranged like the natural numbers, I'd say.)
Nice one
The prince wants a taste of her peach! 🍑
I don’t wanna be the buzzkill here but the anthropomorphization of this puzzle is kind of creepy…..
plot twist... the prince has two hands... he decides to knock on all the doors until the princess answers double plot twist... it doesn't really sound like the princess is too consenting in this whole endeavor lol
@9thlife308
2 жыл бұрын
true!
@DennepeerRelaxation
2 жыл бұрын
She did tell him the rules and consents to the game 😊😊 I assume you were only joking though 😄
Would have made sense to show the solution with the original 6 rooms. Not 5 or 8
2N. I got this answer in 30 seconds let’s see if it’s right Edit: yep, and your explanation was awful :P sorry dude
@ryanbrunelle704
2 жыл бұрын
You are wrong
@worker-wf2em
2 жыл бұрын
To your credit, what you lack in maths skills you make up for in sheer hubris
@mathisalwaysright4048
2 жыл бұрын
LOL let X represent the number of nights required and N represent the number of rooms. Now if N=1 then X=1 if N=2 then X=2 if X=3 then N=2.
@nikitaarts2561
11 ай бұрын
Yay, guys, look at him! He is smart, so that means everyone else is stupid! So good for him! We are so glad to be the only validation of his high self esteem!