How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle
Vložit
- čas přidán 8. 07. 2017
- Tech companies like Google have asked this question during interviews. A cat is hiding in one of five boxes that are lined up in a row. The boxes are numbered 1 to 5. Each night the cat hides in an adjacent box, exactly one number away. Each morning you can open a single box to try to find the cat. Can you win this game of hide and seek? What is your strategy to find the cat? What if there are n boxes? Watch the video for the solution.
My blog post for this video (extensive links for sources of this puzzle):
wp.me/p6aMk-5du
Alexander recreated the puzzle in Python
github.com/SirDrone/Cat_Puzzle
If you like my videos, you can support me at Patreon: / mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisions.com/blog/
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.com/1083366085665...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 3.9/5 stars on 29 reviews) www.amazon.com/gp/product/150...
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 2 reviews) www.amazon.com/gp/product/152...
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.4/5 stars on 13 reviews. www.amazon.com/gp/product/151...
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) www.amazon.com/gp/product/151...
"Math Puzzles Volume 3" is the third in the series. (rated 3.8/5 stars on 4 reviews) www.amazon.com/gp/product/151...
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.3/5 stars on 12 reviews) www.amazon.com/gp/product/151...
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 4 reviews) www.amazon.com/gp/product/150...
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 3 reviews) www.amazon.com/gp/product/150... - Věda a technologie
Editorial note: I started working on this problem 1 month ago. Completely independently Alex Bellos at The Guardian posted the 7 door version, using a cat behind a door (www.theguardian.com/science/2017/jul/03/did-you-solve-it-are-you-smarter-than-a-cat). If you read that, sorry the puzzle is spoiled. It's a coincidence we both used cats; I had already finished my video and post before he posted his puzzle. But hopefully you'll like my video presentation and comprehensive solution of n doors.
MindYourDecisions How is it possible to have a comment from 5 days ago while your vid has just been posted?
Tristan van der Velde youtube logic.
Haha good question. I wrote the comment 5 days ago on my "unlisted" video draft immediately after I saw Alex Bellos posted the same puzzle.
MindYourDecisions love all your videos make similar puzzles, especially the one's like Alice and Bob counting trees!!!
MindYourDecisions Can the cat move from box 1 to box 5 skipping the others?
Cats playing by logical and consistent rules... You've never owned a cat, have you?
I can indeed guarantee you will not find the cat if the cat decides not to be found. For a dog, just call its name and it stupidly gives itself away. The solution would maybe work for a chinchilla or guinea pig.
@@SenselessUsername you’ve also never owned a cat. Cats will also run out just by doing “pspspsps”.
Cats love routine. They always play by logical and consistent rules, they just are absurdly complex logical and consistent rules. You'll feel like a complete wizard when you have a cat figured out and know exactly what they're going to do. Call for a cat and they never come out, draw a circle on the ground and they'll sit in it.
You can never 'own' a cat
@@Pixel3572 I just moved. My timid cat was nowhere to be found for several hours. Not for pspspsps, nor for food, treats, or empty boxes. Wasn't under any furniture when we checked, or anywhere else a cat could fit (yes accounting for cats are liquid logic). If Cat doesn't want to be found then you don't have a cat, even if you know its in here somewhere. (He did eventually come out, but only on HIS time)
Yeah there are three pretty simple solutions to this problem.
1) Get 4 more cats, so that no matter what box you open up, you will find a cat.
2) Lift the box to feel how heavy it is. Then move the heaviest box to the first in the line. The next day, open the second box. You will always find the cat in this way.
3) Get rid of 4 of the boxes so that your house isnt such a darn mess.
The 3rd one seems to be the most logical option😂
1. All 4 cats are in 1 box.
2. Cats are too clever and mischievous for that. It will remember where the box should have been and move to the appropriate original box, confounding your plan.
3. Without it's favorite toys, your now bored cat will chew through all your USB cables and throw up in your shoes
you are hired
I like your second version. Get it out of the second box and tell it off to not be so damn algebraically correct of a cat :D
bring catnip or some crinkly toy to make the cat give away its hiding place. Or open a can of cat food or shake its dry cat food bag
I don't know why, but I originally came away with the impression that Box 5 was also "adjacent" to Box 1. That would totally blow the odd/even thing.
ive never seen it as numbers ive just checked the possibilities , thought dealing with numbers is more of a headache to me 😮💨
same lol
If the boxes are arranged in a circle, and not linear, then yes you'd have the overlap issue.
Well then it would be impossible to solve lol
then you didn't understand the instructions, 1 is not one number away from 5
The way to solve this problem is by shaking all the boxes.
If you hear hissing coming from one of the boxes then that's the one to open.
If there's a hissing cat in it, maybe you don't want to open that one. How important is it to 'win' anyway?
🤣🤣
Ha. Sir Terry Pratchett, in Lords and Ladies, had that a cat in a box is actually in one of three states. 1. Alive. 2. Dead. 3. Bloody Furious.
How do you know it's not just snakes?
@@CrypticCobra would we get that lucky??
Unknowingly to you, the cat got bored and left on day 4
It is not bored. It is hungry..
🤖
lol
O
HAHA!
I will check wieght of all boxes and open the heaviest box 🙂
think outside the box my friend. well done =)
I open every box
@@biddi7972 I put on fire every box and see from where the cat jumps away. Burn them all
The cat decided someone would try this so he hid weights in all the other boxes
xxfillex geodash shake the box
Applying to janitor position at Microsoft
Microsoft: solve this riddle 🗿🗿🗿
To be fair, it's much more likely that a janitor rather than a programmer will need to find hidden cats in the building.
Chose Box
Box = Invert(Box)
Insert:Catnip Box
Echo " pspspsps"
Loop (
check:Box
Endif cat:found
)
Filtering programmers using riddles like this is even worse.
People who can solve this write code so mathematically "elegant" and optimized that no one else can understand it. That's how you end up with unmaintainable software.
I can open 1 box? OK, I'll open a box of cat food. Perfect method for finding cat each day.
Hired!
The cat is in a superposition, existing in all of the boxes at the same time, until you open them. ;)
Hahahaaha.
I don't like this puzzle anyway. But your comment somewhat elevate my mood,
What happens if I have a camera in all of the boxes?
+JF
If you know the rules, he is not! Your knowledge defines the reality, that's how it works!
XD What?
Dude, it was a joke. lol. I was playing on the the Schrödinger's CAT analogy. I didn't think anyone would take it seriously hahah!
And it is actually a sensible analogy of the situation - you have a fraction of a cat in each box, adding to one whole cat. When you open a box, you collapse the local wavefunction to either one cat or no cat, either emptying all the other boxes, or rescaling them proportionally respectively.
Of course, if the cat can quantum tunnel to an otherwise forbidden state, then you've had it...
Practical answer: wait until he's hungry enough to come back out on his own.
did you just assume a gender?
@@user-wb3xw8vo1u No, I just preferred "he" over "it". "She" would have assumed a gender.
@@JohnRandomness105 Im kidding of course :D But that doesnt make sense. He assumes a gender and so does she :P
@@user-wb3xw8vo1u he is sometimes used for a random person
The correct English word for an unknown singular gendered being is "they"
Someone left their keys. I'll wait until they come out of the box.
I got the limitations of where the cat has to move if in an odd box, but couldn't formulate the specific search pattern to exploit it because I got too caught up on trying to make the search consistent for any result rather than narrowing the search based on an assumption and using that to force the cat to fit the assumption. It requires you to put the cart before the horse, or the box before the cat in this instance, which is very unintuitive. Pretty clever
welcome to mathematical proof by cases
Your solution is not correct or is assuming something not in problem explanation. Let's say cat is in 2 and you guess 1. And both you and the cat move right until you get to 5 and them you start moving left. Cat gets to 5 and you on 4. Next night cat's on 4 your on 5. Carry just jumped you. There's no reason why the cat couldn't keep that up. At any point in time the cat and you can change places
@@larman36 Your problem is going to 5. If you are at 4 the cat CANNOT be in 5 the next day because the only way for it to be there is if it was in 4 when you checked it. So instead, you get to 4 and check it two days in a row just in case the cat was in 5 when you checked 4 the first time. This will corner the cat if it was out of sync with you (eg. it moves to an odd when you check an even and vice versa). If the cat is not caught yet, you move backwards this time in sync with the cat because you did an even numbered box two days in a row and as a result you will catch it guaranteed.
I don't know if anyone else thought the same way, but for the even case, I literally thought of the strategy you use to checkmate someone with only a king and a rook. You basically chase them to a corner until they walk into you either by force or by mistake. In order for it to work, you need to make sure to sync up so you never walk into them, you want to make them walk into you. Sure, it's not the exact same problem, but it helped me come up with a solution.
i was thinking about checking box 4 two times, whgich would confirm that the cat isn't in box 5 then check box 3 then box 5 then box 3 but that's an infinite sequence
There's no strategic solution. The cat can jump left or right. Trying to corner it is impossible. Using the chart say day one choosing box 2 no cat. Again day two choose box 2 once more no cat means box 1 is clear right. But what if on day two the cat was on box 3 next day it can move to either box 2 or 4 if you end up choosing box 3. And thats why its impossible to corner or use strategy. It really comes down to random Chance.
@@ravenillusion2596 it doesn't tho?
the solution is literally cornering the cat, assuming that the cat starts on an enven box
then again cornering the cat assuming the cat starts on an odd box
@@user-pl9yq3fc8uthe cat can go back to a box you’ve checked, so it wouldn’t corner the cat
@@ravenillusion2596totally. Each box you check could be the box he was just in the night before. So you never catch him until you get lucky. This video is wrong
Another one of those "interview questions" that has never actually been asked on an interview.
In
@@doctorcrafts on is perfectly acceptable. People say "I am going on an interview tomorrow."
@@FUGP72 incorrect
@@FUGP72 incorrect, they should say I am going TO an interview
@@georgiostsakoumakis7754 Either one is fine. Have you honestly never herd anyone say on?
This solution does give the fewest number of nights in order to be certain of catching the cat, but personally I would pick the boxes in the order 2, 2, 3, 4, 4, 3, 2. This guarantees finding the cat in 7 nights, but with a much higher probability of finding it within the first few nights.
Using the method in the video, assuming an equal probability of the cat being in each box on day 1: (bold indicates box chosen that day, number in brackets is percentage chance of finding the cat by that day)
Day 1: 20% *20%* 20% 20% 20% (20%)
Day 2: 00% 30% *10%* 30% 10% (30%)
Day 3: 15% 00% 30% *10%* 15% (40%)
Day 4: 00% *30%* 00% 30% 00% (70%)
Day 5: 00% 00% *15%* 00% 15% (85%)
Day 6: 00% 00% 00% *15%* 00% (100%)
Whereas using my method:
Day 1: 20% *20%* 20% 20% 20% (20%)
Day 2: 00% *30%* 10% 30% 10% (50%)
Day 3: 00% 05% *15%* 15% 15% (65%)
Day 4: 2.5% 00% 10% *15%* 7.5% (80%)
Day 5: 00% 7.5% 00% *12.5%* 00% (92.5%)
Day 6: 3.75% 00% *3.75%* 00% 00% (96.25%)
Day 7: 00% *3.75%* 00% 00% 00% (100%)
So as you can see, the method in the video only gives an advantage on day 6. Anybody find anything better?
Finally an alternate answer which has some merit.
Okay, Richard, now generalize this to the case of N boxes. xD
@@irrelevant_noob I'd rather not 😆
congrats sir, truly a genius answer. i have been trying to come up with a counter example for about an hour now but it is just perfect.
agreed, by night 4 you've either caught the cat, or you know it started in box 4 and just need to catch a cat in an even box. But you would have caughten every other start location by box 4.
Cool
Thinking this out, I created my own, different solution.
Start off with box 2 twice. This will make you SURE the cat didn't start in box 1 or 2.
Then the cat is in one of 3, 4, or 5.
Use 4 twice to make sure the cat isn't in 4 or 5.
That means the cat started in an odd box, and is in either 1 or 3.
Get number 3, and if there is no cat, it was in box 1 and will be in box 2.
Pick up box 2 and get the cat in 6 turns.
The full order is 2, 2, 4, 4, 3, 2.
that's wrong
@@user-xs1kt5zi4y no
I solved it in a similar way, I had 5 rows and started each with the letter "C", and the only way you can make a C disappear is if all adjacent rows are empty (adjacent rows can be made empty by picking them on a given night). This line of reasoning shows that this is the quickest (and possibly only) method (without redundant steps). It's like a 1D version of Conway's game of life.
*****think outside the box*****
*T H I N K O U T S I D E T H E C A T*
🇹🇭🇮🇳🇰 🇴🇺🇹🇸🇮🇩🇪 🇹🇭🇪 🇳🇺🇲🇧🇪🇷🇸
*T H I N K I N S I D E T H E C A T*
T H I N K O U T S I D E T H E Y O U T U B E
Day 1: Called the cat. He didn't show up but could feel him ignoring me like a jerk.
Day 2: Put catnip on box 3.
Day 3: Check box 3. Just catnip.
Day 4: Check box 3. Still just catnip.
Day 5: Check box 3. Catnip is gone. Feel cat's smug smirk.
Day 6: Jump on box 5. It was empty. Shame.
Day 7: Check box 2. Found some catnip leftovers.
Day 8: Check box 2 again and decide to smoke the catnip.
Day 9: Drench all the boxes with gasoline, set them on fire. No cat.
Night 9: Wake up in my room with the cat looming over my head holding a kitchen knife.
Day 8: Had a bad trip.
Day 9: Sell the boxes, buy dog food, adopt a puppy from a shelter called Nimoy.
Day 10: Nimoy is the best puppy in the world.
Day 11: Nimoy talks to me saying something about kibbles.
Day 8: Still tripping yarn balls.
Day 9: Wished I could remember that youtube video about this exact scenario.
Da
I think i know it
...
Can't sell burnt up boxes
8 and 9 appear more than once
CAT IS STILL ALIVE THOUGH
@@quindexreal You obviously never smoked catnip ;)
Day 10: Nimoy buys 5 boxes and hides in 1 of them
No wonder Microsoft support have failed me so many times when they’ve ran out of scripts to read and I’ve ended up providing the fix as ‘4th line’ if this is the twoddle they get put through.
Every single system in the world is *designed* to achieve exactly the results it *does* achieve
I guess their goal is to make sure they never hire anyone with social confusion/difficulty, or who only solves problems instantly, under pressure, while being watched.
The best strategy is to place a new box on the ground in the evening, since cats always step on new objects, you're guaranteed to find the cat in that box in the mourning.
Since it's a programmer interview question, indexing starts at 0.
Not necessarily.
[sic] how so? indexing starts at zero
It starts from 1 in FORTRAN
Ah I'm not old enough to know that
I'm not actually old either, but once I did a research project for a physics professor who was 70 years old, and I had to learn FORTRAN because he kept using the code that he had written 30+ years earlier.
Tech companies like Google have asked this question during interviews. And then promptly stopped because it was garbage at filtering candidates who can code or manage products.
The most difficult part of this problem is the problem gathering portion of realizing the boxes don't wrap around between 1 and 5.
"The five boxes are lined up in a row"
"The boxes are numbered 1 to 5"
"Each night the cat hides in an adjacent box, exactly one number away"
How did you not notice it doesn't wrap around?
@@israelRaizer actually, the row doesn't have to be straight
@@boguszmakowski2357 even if it's not straight, it still can't be a circle
@VaderxG My problem is they said "adjacent". All the boxes are adjacent to each other lol. If they had said directly adjacent..........then I wouldn't have been as confused but I saw no reason the cat couldn't go from box 5 to box 1.
Either that, or the person doesn't understand constraints and limits before starting a project.
Because they get smart people but doesn't grasp the analytical part of constraining a problem, we have what we call "Google Graveyard". The product exists, works, but unsellable.
Before hearing the answer: I think you need to narrow the available boxes to solve this.
Checking box 2 twice eliminates 1 from the options, unless the cat moves to box 2 on the day you stop checking it. I'm not sure how you can stop the cat from crossing a sequential check, so that's where my issue is.
Alternating between checking 2 three times and then 4 three times is very close to a solution for the 5 box problem, but it allows for a single cat moving pattern to slip through the cracks - if it moves from box 5 to 2 back and forth.
Haven't seen the video yet, here's what I found.
Like you said, check the box(2) twice to eliminate box(1). Then, this would mean that the cat started in either box(3), box(4) or box(5).
Now, if the cat started let's assume at box(3)/box(5). Since we checked box(2) twice, it obviously did two moves. For now, we don't consider box(4).
If it started at box(3) or box(5), it follows that it ends up in either box(3) or box(5). You can check this through brute forcing it(it has to end up at odd after two moves if it started at odd). So if we open box(3) as our turn 3, and it isn't there, we can assume it was at box(5), which would mean it went to box(4) without exception.
Now we check for box(4) and, we find it's not there(say). This means our initial assumption was wrong, so it didn't start at box(1), box(2), box(3) or box(5). and we have wasted 4 turns.
But, we know that it started at box(4), after an even number of turns, it comes back to an even numbered box(assuming we started with an even number box, which we did). This tells us, it's either at 2 or 4.
Finally, we check for let's say box(4), it's not there, which means it was at box(2) and has now moved. It has either moved to box(3) or box(1). We open box(3) and still don't see it there, which means it was at box(1) which means it HAS to be at box(2)
Solved! This took way too long. You can obviously start with another order, doing it by my method, there will be four distinct patterns to get the same result. Might be more but, pretty neat. Hopefully this was understandable.
@@senquidang, i left this problem half way after knowing that I couldn't catch up with the cat assumming it at 4th box, but after reading your solution to keep narrowing down the possibilities, this actually a great way to solve the problem(pinpoint exactly where the cat is at the momment), nice job
@@senquichecking box 3 on turn 3 doesn't actually accomplish anything here. if you start by checking box 2 twice, you know the cat must be in boxes 3, 4, or 5. if you check box 3 on turn 3 and the cat isn't there, then it must be in box 4 or 5, from which it will move to boxes 3, 4, or 5, the same possibilities as before checking box 3. therefore, you can eliminate this step entirely, checking box 2 twice, box 4 twice, then box 3, then box 2.
for example: checking box 2 for the first 2 turns guarantees the cat is in 3, 4, or 5.
checking box 4 on turn 3 and missing means the cat was in 3 or 5, and it moves to 2 or 4. check box 4 again and miss means the cat is in 2 and moves to 1 or 3.
check 3, and if the cat isn't there, it was in 1 and now must be in 2. this solution takes 6 moves rather than your 7 due to your unnecessary check of box 3 on turn 3.
@@mbeno. well yes I think your solution is more efficient and also works. It uses the same principle, I just thought of the solution in this order to make sense of the question and so it came out this way. I knew there could be more efficient solutions from the beginning, just finding one of them was enough for me lol. Good job though I didn't think of that.
Edit : I do have to say while your solution is more efficient, my turn 3 as box(3) is still necessary in the method I presented. It just happens to be that the order I eliminate is slightly more inefficient.
The main purpose is to try and eliminate where the cat started rather than where the cat is, which then leads you to the correct answer, as is the case with your solution as well. So while my solution is inefficient, turn 3 is still necessary in context of the whole solution.
@@mbeno.Your solution is wrong. This sequence will not be caught: 4, 3, 2, 1, 2, 3.
In your example checking box 4 and missing means the cat is in 2, 3 or 5 not just 3 or 5. Which means it can move to 1, 2 or 3 not just 1 and 3.
Three ways to find the cat.
1) Shake the cat treat box and see where the can comes from.
2) Sit in front of the boxes without making a sound and see what box moves when the cat moves inside it.
3) Set up a camera on the boxes before bed and see which box the cat in by review the recording the next morning.
4) if the room is cold, see which box is warm
5) bring some food and call the cat, it will leave the box
Thank you 👌🏻
yeah exactly why are we wasting time with math lol. You could also hear the cat purring so I could guess it in 1 try. Obviously the poster of the video is not a cat person.
6) Use X-ray on each box
Day 1: put sand all over the place
Day 2: follow footprints
🤣🤣
Problem: footprints all over the place! ;)
Another possible problem: the cat actually doesnt put a foot outside of the box, but just hops
Day 3: Build maze around boxes forcing cat to walk on sand and avoid mad Bunny hop skills.
Day 4: No footprints, no visible damage on the maze. Must not have moved, But that can't be...
Day 5: Still no prints, Is this cat Quantum leaping or something?
Day 6: Devise a new plan, Place a wireless camera within every box each day.
Day 7: No cat. Place camera.
Day 8: Check cameras. Oh my God... What the faq is that?
Day 9: I threw all the Boxes away. Whatever I saw in the footage has haunted me in my dreams.
Day 10: .... *Crunching*
@@edwardvilla3228 sounds like a trollge incident
This is a very good puzzle. It tricked me by appearing to have no special asymmetry except at the endpoints. The last thing I suspected was the possibility of dividing it into cases by odd and even.
Brilliant solution. The key is the assumption of even or odd box for the cat to be in initially, and in each case, checking an extreme left or right even and odd box, resp., to isolate the cat to a smaller and smaller subset of boxes away from the extreme 1st check. However, there is another generalization that is missing in your solution, and which makes the n-box problem "proof" slightly incomplete. This generalization has to do with, say, starting w/ the even assumption, whether m_e the max # of checks (that are unsuccessful) you need to do it itself even or odd. If even, after m_e the unsuccessful checks, the cat is back in an odd box, and you can apply the odd box checking sequence starting from an extreme left/right odd box. If m_e is odd, then after the m_e unsuccessful checks, the cat is in an even box (since the checks were unsuccessful, the cat was initially in an odd box, but after odd # of checks, it is now in an even box). So you repeat the m_e checks done w/ the even assumption (but now knowing the the cat is definitely in an even box), and you can catch the cat.
So for the n-box problem, whether m_e is even or odd depends on n. Since m_e = n-2, then if n is even, m_e is even, and after the 1st check seq. of 2, 3, ..., n-1, if unsuccessful, means the cat is in an odd box barring n-1. So the checks need to be n-3, n-4, ...,2. However, if n is odd, then m_e is odd, meaning that after the1st m_e unsuccessful checks, the cat is in an even box barring n-1, and so either the 1st m_e checks 2, .., n-1 can be repeated or the aforementioned checks n-3 [this is even now], n-4,.., 2. can be done, and the cat will be caught either way. Hopefully, you can see that this is a complete proof as it covers the cases of n being even or odd.
The grid representation is ingenious. The cat always moves diagonally, and you have to use blue squares to draw a shape that blocks all possible paths.
Try thinking outside the box. Place a small piece of paper on the lid of each box in the exact same place on each box. In the morning you can just check to see which box has the piece of paper displaced and the cat will be in that box.
Do not make things more difficult than they need to be.
Learn to spell genius correctly before trying to identify it.
@@andybaldman "Lean to spell"? Seriously?
@@Nuoska
The one thing worse than a spelling/grammar nazi is a a spelling/grammar nazi that is bad at spelling and grammar and who eagerly criticizes people who who spell words correctly and uses them grammatically. Sad really, when you think about it. For a couple of seconds anyway.
@@oldtimefarmboy617 I can edit my mistakes. You can't edit stupidity.
I saw a near-identical puzzle on Ted-Ed (“Can you solve the seven planets riddle?”) before, so doing the same thing here is pretty trivial. First, think about the parity of the boxes.
Each night, the cat moves either from an odd box to an even one, or the other way around, so you can consider them separately.
First look at the case where it starts in an even box. On the first night, check box 2; if it isn’t there, it must have been in box 4, and moved to either 3 or 5. Since 3 leaves more possibilities open than 5, check 3. If it isn’t there, it must have been at 5, where it can only move to 4 to be discovered the next night.
Now what if it started in an odd box? If you did the three previous checks and didn’t discover it, it must have started in an odd box. Since you checked the boxes three times, it has moved three times, from odd to even to odd to even again; since you know it’s in an even box, you can just check 2-3-4 again, and are guaranteed to discover it.
Oh, wow.
I thought you'd have to check at most ten times for 5 boxes, I didn't realize you could just start on the 2 and go up to 4. Oh well, I'm still pretty proud of myself for coming up with this on my own.
@@GarryDumblowski This strategy only works if you have an odd number of boxes (eg 5), so your last box checked is even (4 in this case) so you know that the cat is an an odd box and tomorrow the cat will be in an even box.
If you had 6 boxes, last checked is box 5 - so cat is in an even box and tomorrow the cat will be in an ODD box again. Your strategy could by chance go forever, no guarantee :-).
Not quite true, because now you know the cat is in an odd box. Guess a random box, now it’s in an even box. Run the even box strategy again, now you’ve found the cat. This problem should always be solvable.
As long as you don't open a box the cat is in each box. ('Schrödinger's cat')
This was a tricky one. My solution for n boxes is slightly different, but I believe it still works. I solved it by realizing that the cat is stuck in a sort of pattern of two states, between even and odd boxes. You can start by chasing the cat to the end of the row in which case it will have to turn around. Yes, you might miss it on the first go around, but you will catch it on the second one. All you have to do is make sure you take an odd number of steps before restarting, so now you are 'in sync' with the cat's 2 step cadence. So for even instances of n, you just have to repeat n-1 for one more day. For 6 boxes it would be 2,3,4,5,5,2,3,4,5,5
Huh, quite similar to my solution, except I only figured out half of it, and couldn't figure out how to catch the cat if it gave you the slip the first time down the line. 😂
Everyone is thinking of schrodinger's cat, while I can only think about the dark magician and his magical hats
Welp, time for my weekly reaffirmation that I'm too stupid to work at Google.
Nice puzzle though!
at least you could now work at microsoft
There not expecting people to necessarily get the correct answer, there interesting in your thought process, decision making skills and ability to discuss and relay your ideas back to your peers. Also don’t forget you would be sat down with a whiteboard or pen and paper, not glancing at it on a CZcams video while more than likely trying to solve it in your head
This question never appeared in an interview.
I thought of checking the box 1 over from the left for 2 days, then moving to the right and checking that for two days, and repeating that process. Once you get to the second day checking the box 1 over from the right, you are guaranteed to catch the cat. It will catch in the same amount of time as your solution for even and odd numbered cats. Very cool how that worked out.
You can start checking the boxes with the second one, if the cat started in the first box, the next night it can only go into the second box
@@shmel3689 I know...I said the box 1 over from the left...as in the 2nd box.
it won't work. you check 2, 2, 3, 3, 4, 4 but cat move 4, 3, 2, 1, 2, 1
I see we have a programmer here indexing from 0
I understood from this: 1,1,2,2,3,3...
Well that doesn't work
Fyi, love these types of problems for my children to try to get them interested in STEM subjects. Thank you!
interesting side note: if you use the strategy of 2234234 instead of 234234 you have to take one extra step to find the cat for sure, but you're more likely to find it immediately. You'll have found the cat 50% of the time by choice 2, 70% by choice 3, 90% by choice 4, 95% by choice 5, 97.5% by choice 6, and 100% by choice 7. Corresponding values for 234234 are: 30% by choice 2, then 40%, 70%, 85%, 100%. So if you've really, absolutely gotta find that cat fast...
If you really gotta find that cat fast, set the room on fire.
@@NestedQuantifier or just open them all at once
Great solution! There is often a trade off between average speed to solve vs. max required time to solve. Very similarly, there are 2 solved solutions to the game Mastermind, 1 of which solves faster on average and the other of which solves all cases in 5 guesses.
I guessed 4 4 2 2 3 4
@@mihai6400 same. The percentages are
20%, 37.5%, 66%, 75%, 50%, 100%
I'll just go "pspspspsps" and the cat will come to me instead.
Great minds think alike.
i came to the same solution by noticing that checking a box next to an edge box disproves said edge box, and then trying different cases to see if I could disprove multiple boxes on the same step. then I discovered properties of disproven spots, like how any box with two disproven spots on either side of it will be disproven on the next step, ending up with a Conway's game of life-esque set of rules for how disproven spots appear and disappear so that I could basically just play the game that emerged from those rules to narrow it down to only one possible spot, aka "catch the cat"
I did notice the property that the cat would alternate between even and odd spaces, but I didn't actually build any of my logic or rules off of it
Ok so, this problem gets simplified if we think with evens and odds. if the cat starts on an odd box (boxes 1, 3, and 5), the checking orders 3, 2, 3, and 4, will always catch the cat. but if the cat is on an even box, that order will fail. since 3234 always works if the cat is on the same parity as us, we just need to check 4 again and repeat the process, thus flipping our parity and catching the cat.
Proof (with the worst possible luck)
P=box that player checks, C=box that cat is in, commas separating turns and dashes pairing the two different values. for example, P1-C1 means that the player checked box 1, and the cat is in box one, and the player wins.
cat starts at 1 (P3-C1, P2-C2[win])
cat starts at 2 (P3-C2, P2-C1, P3-C2, P4-C3, P4-C2, P3-C1, P2-C2[win])
cat starts at 3 (P3-C3[win])
cat starts at 4 (P3-C4, P2-C3, P3-C4, P4-C5, P4-C4[win])
cat starts at 5 (P3-C5, P2-C4, P3-C5, P4-C4[win])
Ok, just watched the video and saw the solution, I was on point with the explanation ! (though I was 1 turn less efficient). I think I started with the middle because I saw a problem similar to this one except there were three branching paths off of the middle that the cat could've gone to, and solving required a middle check first.
How to find a cat? Just meow, the cat meaw's back. Just simple as that!
har haaaaaaaar
When and where gave you heard a cat meowing back? That's unheard of
@@pabloanapedro2740 ok Mr. Serious
@@factgod5 nice one
Just open the boxes in any order and leave them open, then you will be easily able to find the cat. The instructions say we can open 1 box each morning. It doesn't say anything about closing them. Since we wont be watching the boxes at night when the cat moves, then by definition, the cat is hidden (out of sight, concealed) from us until possibly the next morning. Sounds like a weiner (winner) to me.
If you didn’t have to close the boxes then it wouldn’t matter what order you opened them
What?!
@@alexandrap4475 The boxes will stay open so eventually we will see the cat. Who cares if we miss it on the first few days?
But you have to open the box to find the cat. If you leave it open, technically you find the cat BEFORE opening.
@@davidjames1684 it was just an idea, slow down man. And besides, the like ratio has nothing to do with "truth". Post some communist crap on a leftist video and you will get lots of likes. I just was confused, it say "you can" and was thinking in "you must" (open a box).
If the starting point is random and the movement is random, would the distribution of locations form a bell curve? Would there then be a benefit to starting your search from the center?
Edit: I have gotten several comments on this pointing out a false assumption. They are correct. This will not work if the cat goes from 4-3-2. I have marked the mistake, but will leave the rest of the comment up.
This is a tough one, but let's give it a go. I think this works for the 5 box problem. not sure if it scales up though.
My approach is to try to "corner" the cat, using the end numbers as "walls". If the cat is in box 1, it must go to box 2 on the next turn, likewise with boxes 4 and 5. So I'm going to remove options, and then chase it until all the options are removed.
Step 1: open box number 2
Step 2: open box 2 again
If the cat was in box 1 to begin with, it can only have moved one position from it's starting point, and therefore will be in box 2.
if it is not in box 2 now, then you know it started in 3, 4 or 5
Step 3: now this is the tricky bit - open box 4.
The cat could have moved at most two boxes from it's starting location.
if it started in box 3, it's either in box 3 or box 5
if it started in box 4, it must be in box 4. It cannot be in box 2, because you just opened it (edit: this is an incorrect assumption which dooms the rest of the approach. I forgot that the cat moves AFTER you open the box a second time, which means it would not be caught opening box 2 on step 2)
if it started in box 5, it's either in box 5, or box 3
if that cat is not in box 4, then it is in either box 3 or box 5.
Step 4: this is the trickiest bit - open box 4 again
If it was in box 5, it MUST move to box 4
if it is not in box 4 that means it was in box 3 on step 3, and moved into box 2 when we opened box 4 on step 4.
At this point, I know exactly where the cat is, box 2, but I have used my turn for the day, and it will move before I can open box 2.
Which also means it will NOT be in box 2 the next day.
This narrows the options to box 3 and box 1.
Step 5: Open box 3.
we know that after step 4 the cat was in box 2.
that means it has moved to either box 3 or box 1.
If you pick box 1, and the cat is in box 3, it will move to either 2 or 4, and you'll have to start over.
If you pick box 3, and the cat is not there, it must be in box 1.
the next time the cat moves, it can only move to box 2.
Step 6: open box 2.
you have the cat.
Edit after watching solution:
I didn't consider that by picking box 2 first, I eliminated box 1 on the next step, though it would not change my thought process.
I never considered there being two starting states of Odd or Even. Interesting.
This is exactly the solution I came to using similar logic
I had this solution too, but found a case that breaks it...
If the cat follows the order 4, 3, 2, 1, 2, 1or3, you never find him. Parity didn't occur to me until he mentioned it.
Your solution 2 2 4 4 3 2 doesn't work: the cat can start 4 3 2 and you never find him. If you try to confine the cat to the right, you will be stuck opening 2 all day. You have to combine with the odd/even case to make progress
My first suggestion was exactly this solution, but it doesn't work though. Because you have wrong premise in step 3: " It cannot be in box 2, because you just opened it". The cat started in box 4, than went into 3 and into 2.
The technique: stay in the same box for one step unfortunately doesn't work.
That's one of the most interesting videos i've seen on your channel, and I seen a lot of interesting videos here. Thank you very much!
That grid illustration was excellent.
There is a simpler solution: Suspend each box in approximately 10 liters of concentrated sulfuric acid.
Man, that was hard. Half the day I was thinking (intermittently) about this, but I finally got it.
I considered transitions of the set of possible locations of the cat after each choice, so starting with all possible locations: {1,2,3,4,5} and choosing box 2 at the first step (each choice yields empty box):
2: {1,3,4,5} -> {2,3,4,5}
3: {2,4,5} -> {1,3,4,5}
4: {1,3,5} -> {2,4}
2: {4} -> {3,5}
3: {5} -> {4}
So the cat is finally in box 4.
The representation isn’t doing something special… you’re still guessing the sequence..
@@John-lf3xf Well, you're correct. This is not a general solution. Just a visual way to convince myself that the solution even exists!
Is there a solution if the boxes are in a circle?
Only if you can check more than one box per day
then you would need more conditions to solve it
if there where in a circle it would kind of be like if n was equal to infinity, this would make it impossibile to have a 100%accurate solution
Yes, if the number of boxes is 2 or 1
Yes there is. After you check a box, if it's empty set it on fire.
i got almost this exact same question in an interview last year... the only difference was that the cat also had the option to remain in the same box on any given night OR it could also move 1 adjacent box just as described in the video. my response was that if there was 2 or more boxes and i could only open 1 box each day, then there is no guaranteed solution that will always find the cat.
my reasoning was... even in the simplest case where there are only 2 boxes for the cat to hide in, if i do not guess correctly on the first day, i know where the cat must be as soon as i open the empty box. but unfortunately i have to wait until the next day to open a box again, and the cat will have 2 options to either move or stay in the same box that night, so i cannot eliminate either box on day 2. essentially, every day can never get better than a 50%-50% random guess between the 2 boxes, with no ability to ever eliminate either box as a possible location where the cat is hiding that day.
the interviewer said my answer was good for the case of 2 boxes, but refused to reveal a possible solution he said i missed in a case when there is a particular number of boxes greater than than 2... can anyone think of what it might be? it seems to me like ANY number of boxes greater than 2 would be every bit as hopeless as the 2 boxes case, assuming the cat always has the options to either move 1 box or remain in the same box each night... ?
Your interviewer copied the question from online, got the conditions wrong, and thought there was a genuine solution. 1 year later I hope you got a job by now
Indeed. It's easy to prove: If we have only two boxes, and we have a strategy that works for N > 2 boxes, all we have to do is put out N-2 imaginary boxes. Since now we have N boxes and a cat that is moving according to the rules (plus the additional constraint of not moving into an imaginary box, but it could have been using that constraint with N real boxes so it doesn't matter), we can apply our strategy, and find the cat. Well, almost -- we're not allowed to choose to look in an imaginary box. But we can adapt our strategy -- if the N-box strategy would have us look in an imaginary box, we know the cat isn't really in there, so it can't break the strategy if we don't really look there. Instead, on that night, we can randomly choose a legal choice of looking box 1 or box 2. If we find the cat, we win, and if not, we're in exactly the same place in the N-box algorithm as we would be if we'd looked in the imaginary box.
Be glad you didn't get that job, or you'd be stuck dealing with idiots. And not because they got the cat puzzle setup wrong. They're idiots because they're supposed to be engineers, but they didn't even test their own puzzle solution.
Just saw
I didn't get your 2 box problem.
If you open box A and the cat isn't there, the cat is in Box B. That's not answer enough?
@@drkrishnap : No, because we can only open one box per day, and the goal is to actually catch the cat. We may know the cat is in Box B today, but we don't get to actually open that box today, and tomorrow it could be in either box.
Would checking the second box for n-1 days (with a special exception for n=1, in which you check the only box availible), then checking each box in order until you reach the nth-1 box work as well? I believe it would, though I'm not entirely sure.
I thought the same thing, but it doesn't work. I tried this theory on the 4 box example:
Day 1- cat in 3 you search 2
Day 2-c4 s2
Day 3-c3 s2
Day 4-c4 s3
Day 5-c3 s4
Hope this helps😀
no
Consider the case in which the cat starts in one of the two last boxes and keeps jumping between those two boxes.
If you search the second box n-1 times, you wouldn't find this cat and you wouldn't be sure if it's in an even or odd box either. After all, it could have started in box n or n-1. Suppose it's in an even box after your initial n-1 searches. In this case, searching 1, 2, 3, ... n-1 would never find this cat because for all your odd guesses, the cat would be in an even box and vice versa.
the cat can slip into the box you just checked, making you stuck
You kind of made the case 2 (starts in an odd box) scenario more complicated than necessary. Just start with box 1 on day 1; the cat is in an odd box then, so check box 1. If it’s in the first one - great! If not, then it can only be in box 3 or 5, so the next morning it will be in box 2 or 4 - so check 2 in the morning. If it’s not there then it must be in 4 and will go into either 3 or 5 by the next morning, so check 3 then and keep carrying on like that as you corner the cat. Simple.
An easy way to think about it is that once you have the same parity as the cat, you can sweep the entire row of boxes and the cat can never go past you while you're moving. 1) Start in the first odd box, sweep the row. 2) Reset parity, then start in the first even box and sweep the row. By "reset parity", I mean if there's an odd number of boxes, just check the first box one more time before starting your next sweep, to resync the cat's parity.
It can be done in a single sweep. 1,1,2,3,4,...,n total of n+1 steps to guarantee finding the cat
@@dennisb6194 But it can jump past you. If you check box 4, it could have been in box 5. Next thing you do is check box 5, then it could already be in box 4.
But the sweep is a very good idea. I think you can solve it with that: If you sweep twice, that could work. In the first sweep you assume it started in an even position, so you check 2, 3, 4 ... n-1. Then you know it couldn't have started in an even position, so you go again with 1, 2, ... n-1. That even and oddness prevents the cat from jumping past you, because in one of the sweeps it's an even number of positions away from you, so if you go one by one, it can't jump past you without getting on your box, which you then will be able to spot.
And why I stop at n-1: You don't have to check the last one, because you assume that the cat is on the same parity as you. So if n-1 is odd and you're on it, the cat can't be on n, because n is even. The same applies if n-1 is even and n is odd.
This problem is, at its core, nearly identical to part 3 of the Power Question in the 2012 ARML competition. I was immediately reminded of that question when I saw this one, as it was a practice question our team did recently. I'm wondering, was the problem in this video was based on that one, or were they developed independently?
The solution I found was double searching the boxes starting from the 2nd (223344). Same number of searches, 100% success on the last box and simpler imo.
This will not always work.
@@Username-2 Whoops, you're right! It was a rather simple example, I don't know how I messed it up. Thanks!
If it’s a 50/50 chance going left or right then my algorithm may be an improvement (2,2,3,4,4,3,2). This gives an expected value of
Presh: Pause the video to try work it out.
Me: Lift each box up and see which one's heavier.
I'd go on vacation for two weeks. On my return, it'll take me no more than five tries to find the starved cat.
No five tries, just smell the boxes.
Possibly dead cat
So 19 days in total to find the cat, brilliant.
No more than five tries to find out that the cat has left the room to go hunt.
I'm probably missing something, but the odd-box starting position seems to me to resolve to the first case already on Day 2 (the cat must be in 2 or 4). Why wait until Day 4?
You have to wait for day 4 so you can check if the cat was in an even box or not. By day 2 you can’t know if the cat was in an even or odd box. Not sure if you understand it now? 😁
@@tibodevos9671 but if the cat started on even and we wait four days, now it’s odd!
@@mygills3050 Well, if the cat did start even, you would have found the cat already by day 4. If you don’t find the cat by day 4, that means the cat was originaly in an odd box, and thus, on day 4 she will be in an even box, and you start all over again
@@tibodevos9671 I suppose. I guess what you mean is, that if the cat starts in an odd box, you will have found it by day 3. The fact that you've got to day 4 without finding it means it must have started in an even box. The narrator doesn't make that clear. Thanks for the help!
@@keithmoore5606 yes, exactly 😁
My first thought was to look at one end, search each box twice, then move to the next and repeat. But the cat could still slip past. I wonder if there is a pattern that would allow you to effectively create a barrier and chase the cat into a corner. Or at least a pattern that would make the chance of the cat slipping through extremely small.
I'm a little late but, here's what I found.
Like you said, check the box(2) twice to eliminate box(1). Then, this would mean that the cat started in either box(3), box(4) or box(5).
Now, if the cat started let's assume at box(3)/box(5). Since we checked box(2) twice, it obviously did two moves. For now, we don't consider box(4).
If it started at box(3) or box(5), it follows that it ends up in either box(3) or box(5). You can check this through brute forcing it(it has to end up at odd after two moves if it started at odd). So if we open box(3) as our turn 3, and it isn't there, we can assume it was at box(5), which would mean it went to box(4) without exception.
Now we check for box(4) and, we find it's not there(say). This means our initial assumption was wrong, so it didn't start at box(1), box(2), box(3) or box(5). and we have wasted 4 turns.
But, we know that it started at box(4), after an even number of turns, it comes back to an even numbered box(assuming we started with an even number box, which we did). This tells us, it's either at 2 or 4.
Finally, we check for let's say box(4), it's not there, which means it was at box(2) and has now moved. It has either moved to box(3) or box(1). We open box(3) and still don't see it there, which means it was at box(1) which means it HAS to be at box(2)
Solved! This took way too long. You can obviously start with another order, doing it by my method, there will be four distinct patterns to get the same result. Might be more but, pretty neat. Hopefully this was understandable.
5432
Gathered all boxes at home and put them in one room.
Took both of my cats and left them over night in the box room.
Searched all the boxes the next day, cats were in neither of them but in the kitchen eating my chicken dinner from last night since I needed the freezer to be a box.
Can confirm the system works since my kitchen is the second room of my flat and what are rooms if not giant boxes ...
I did it a different way that still works. I thought my idea was wrong when I saw the answer but i tested it out using the same method of the chart and found my way to also work. FeelsGoodMan
I did it differently.
(Assuming I open an emty box every day)
Day 1: Check 4 -> He didn't start in box 4
Day 2: Check 2 -> He didn't start in box 1
He had to start in either 2, 3 or 5. If he started in 3 or 5 he has to be in box 4, so
Day 3: Check 3
Day 4: Check 4
If he's not there, that means he had to start in box 2, therefore after 4 days he has to be in an even box, and we just checked box 4, so he's in box 2, so
Day 5: Check 3
Day 6: Check 2 and we got him for sure.
I know it wouldn't work for n boxes, but I'm utilizing the fact, that there are only 2 even boxes.
@Marcin Jaroszuk
this method doesn't work. The are many ways for the cat, e.g.:
Day 1: Box 2 (checked: 4)
Day 2: Box 3 (checked: 2)
Day 3: Box 4 (checked: 3)
Day 4: Box 3 (checked: 4)
Day 5: Box 2 (checked: 3)
Day 6: Box 1 (checked: 2)
your mistake was after Day 4: "therefore after 4 days he has to be in an even box"
but 4 days after day 1 is day 5 (not day 4) and you have to check box 4 on day 5 again and then go on with day 6 and 7.
And then it's the same way he did it (starting on day 2: 2-3-4-4-3-2)
I'm very proud of myself; I figured all of this out on my own after just looking at the thumbnail, then I watched the video to check my work.
:)
Did you use pen and paper? Idk how this can be solved without pen and paper, because you would need memory like a computer 😂
@@th3smurf692 Yeah I used paper.
Categorize n boxes into ODD and EVEN. By continuously moving the number you choose can eliminate possibility for one category.
When only one category is left, using the same strategy to eliminate the leftover category.
This is a really good algorithmic question actually... what a nightmare when your search algorithm is looking for something that changes index lol
Using this method, you're guaranteed to find the cat in 2n-4 days. Since we start at day 1, this means that we need a minimum of 3 boxes for this method (2n-4 >= 1).
This bears out because we start at box 2, and increment until we get to n-1. But if n
One should pin this remark. It's so important to note the validity of a statement.
My cat just hide half a day last week and I thought it’s lost until it showed itself so now I’m here to learn how to find a cat.
7:45
I realized you can express this problem in a really formal way:
Start out with a cellular automaton as in Wolfram's one-dimensional universe with 5 (or in general n) white boxes/zeroes and infinitely many black boxes/ones to both sides.
Now repeat the following steps:
1. Change a 0 in the current generation to a 1
2. Calculate the next generation according to rule 160.
Is there a way to change boxes so that after a finite amount of generations, there is only black boxes/ones left?
That is not how cats operate.
Do not EVER let a cat operate, they have not been to med school.
You've obviously never heard of Dr. Cat, MD. doctorcatmd.com/
LOL! OK, I will make an exception for Dr. Cat, M.D., although I suspect his technique is way less than purrfect.
Holy moly someone just made me read.
our cats love hide and peek-a-boo.
is there any generalization of this puzzle but on a grid? like NxM? i would love to see if there could be a solution to that
To trap the cat into having only one (predictable) move, you must have N=1 or M=1. So, the answer is, "no".
For a proper grid, if you "find" the cat, there was always the possibility that the cat could have chosen a different box the previous night. So, it's luck. For the problem in the video, you make use of the fact that the cat only has one choice at the extremes.
I’m getting Princess Bride vibes from this video. INCONCEIVABLE!
Just say "meow", and when the cat meows back, find and open the box.
Great puzzle! Asking for general solution is like a hint that some pattern should exist. Unfortunately, I did not take advantage of this hint.
I pick up each box to check the weight of the box. Then open the heaviest one.
Or, if only allowed to touch a single box a day, I open the middle box. Then I move the box so it is no longer near any of the others and therefore no longer adjacent to any of the others. Then I can check, 2 2 and then 4 4 to eliminate any other possibilities.
My strategy to find the cat = shout "lunch time" 😂
It always work for my cat, no matter where it is hiding.
Hi, Presh! I have been a subscriber of this channel of yours since 2016. I am an Engineering student from the Philippines, and videos like these help me a lot to learn new tricks of solving complex math problems. Thanks.
Which branch? Electrical?
I found a better solution! - well, at least at 5, 6 and 7 boxes. You chase the cat from end to end! Lets take 5 boxes:
Pick box 4 twice, then box 3 once, then box 2 twice. If the cat passed you with its quick moves (which in this case only happens when cat starts in nr. 2), then you continue the other way picking box 3 once and box 4 twice.
In general, it is n-1, n-1, n-2...2, 2, 3...n-1.
Or the other way around of course, your choice.
To compare:
With your method, the sum of maximum possible days, for all 5 boxes, is 22, while mine yields 18 days!
At 6 boxes it is 33 and 31, and at 7 boxes 44 and 43. At 4 it is even.
Then when we get higher, my method kindaaa skyrockets.
A badass answer to the solution though would be "well if you want me to look at this isolated case of 5 boxes, then ¨my method¨ would in average catch your cat the quickest. But if you want a general method for all numbers of boxes, then go for ¨your method¨."
This method is also more fun to imagine in real life, especially with something like 100+ boxes ^_^
Originally my guess was just to use the same box again and again. Then after you said not to do that, I thought “how about moving from one side to another”
Excellent explanation, very detailed and clear.
Schrodinger has a headache.
I have five cats in five boxes but only one of them is real.
Have yet to finish the video, cause I think it's fun to document my thoughts and then compare them afterwards to see how wrong I actually was- 😂
If you start on one end of the row of boxes, and then work your way down said row by one box each day until you reach the other end, you are guarantied to eventually run into the cat, since it can only move to adjacent boxes, and it could not pass you, no matter where it starts at. No matter where the cat starts in relation to you this way, the cat, even if it can move farther away from you, can only move as far away as the other end of the line, and cannot go backwards without running into eventually in the process, making it inevitable to eventually run into the cat.
The only way that I could see this failing is if the boxes are in fact, not in a line, but are in a circle, or if there is a time limit where the number of days you have to find the cat are less than the number of boxes. If they're in a circle, the cat could forever stay one step ahead of you, no matter what you try to do. If there's a time limit, it is no longer guarantied to find the cat before the end of the time limit, however, I believe this still increases your chances than simply picking randomly.
Lol, I thought I was so smart until I realized while watching the video that, the cat could in fact, still get past me if I open the box next to it, and then the next day, it moves to the box I already opened. 🤦♀😂
I haven’t seen the video yet. But I think you can guarentee you find the cat by checking box 2 then box 2 then box 3 then box 3 then box 4 so a total of 5 boxes for this solution. I do not know if I shorter solution is possible but I do believe a symmetrical solution is. If you switch box 2 with box 4 and box 4 with box 2.
Oh Oh Oh ! I know this and I made a variation that is much harder can you hear me out?
Suppose the cat has more possibilities than moving to adjacent boxes. Here are three rules how it can move:
1. It can *move* to an adcacent box OR it can *stay*
2. It MUST *move* the next night if *stayed* last night (the box starts to smell or whatever)
3. It MUST *stay* if it *moved* TWO CONSECUTIVE nights. (it got tired of moving and needs to rest)
(Note that yes that means, after two consecutive nights of moving it not only needs to stay the next night but also needs to move the night after that because it then stayed.)
The interesting part is that you never know whether the cat stayed or moved but the riddle is still solvable with a similiar strategy.
The solution for n=4 is not too hard (I think it was 6 nights) but for bigger n it seems to always have solutions but I was not able to find a pattern. Maybe you can find one, I did solve this with code for bigger n but there seeems to be no better way than guessing and I am not even 100% it will always be solvable for every n.
Yes it is. Start at n-1 and then guess it 3 times in a row. Therefore, the cat must be in boxes 1-(n-2). Then go down to n-2 and guess it 3 times in a row. This narrows it down to 1-(n-3). Thus inductively, you can keep on going and eventually you will find the cat.
Oh wait never mind that doesn't work.
Yeah I had similar approaches for such a "narrowing down" procedure and it seems ti exist but it didn't seem to have a pattern.
Haha the trick's on you! One of the boxes is an empty box from an exceptionally expensive toy we bought for our cat that it will have nothing to do with. But we know that cat's WILL have something to do with the boxes of said expensive thing/toy. So, with this fact of life, we know the cat will be in the box that the toy/thing was packaged in, and we can discard the other four boxes into the meat grinder.
2 possible solutions based on probability.
Case 1: 2-3-4-4-3-2, guaranteed success within 6 moves.
Case 2: 3 until successful. 20% chance of success on first move, 25% on every move thereafter. 50% chance in 2-3 moves. Will probably guess correctly within 4-5 moves, but no guarantee so it could theoretically continue to infinity.
(No, i'm not misapplying the statistical conversion, if you tell me "you don't add percentages" that's not what I did, but I also didn't feel like calculating out exact probability of success within # of iterations so I did the math in my head and rounded.)
I'm not a mathematician, so I'd wait until either the cat gets hungry or bored, and comes out of the box by itself. You see - it pays off to understand how cats operate.
If you have a 2-dimensional set of boxes (say 5x5), and the cat can move to any adjacent box (but not diagonal), can you be certain to find it? My guess is you need to be able to check at least 3 boxes at a time to do it ... haven't solved it yet but thought it was an interesting thought worth sharing.
You can try a 2x2 and immediately realize you need at least 2 guesses a turn to do it or the cat will just dance around your guesses.
A1 = No A2, B1, B2 = Possible but can get to any square next turn anyway. I brute forced 3 and found the same thing. You essentially need to do the same thing in the video, just make a massive column to stop the cat from squeezing out somewhere.
I found a different way, i dont think its any better but i would check box 2 twice then box 3 twice and so on. This would eliminate the previous box from being a possible spot where the cat could be, which then reduces the problem to the exact same but with n-1 and then you can repeat the process until every spot is eliminated. I believe it has the same worst case as the videos method being 2(n-1) days but I think its a more simple method to explain, but it might not have as good of an average case
You can just triple down on 3 and quarantine it to a single side. This results in a 5 day win if it was in box 1 or 5 and a 6 day win if it was in 2 or 4. Although if it was in an even you could technically get a 5 day win by doubling down on 3 rather than triple.
I solved this without odd/even approach. Just use min/max approach. Pick boxes that will give you best result at the start and then pick the ones which give you unseen state. You end up with the same sequence.
Keep in mind that 5 boxes have a lot of mirroring involved so 1/5 and 2/4 give same results in some cases, eliminating possible moves.
For example 2 or 4 is the only good move in the beginning since it creates new state where cat can be in just 4 boxes.
I solved this in 10 minutes or less, not even thinking about parity (admittedly, it's more elegant a solution) i.e. splitting the starting position to even/odd number and working from there - but rather solving it iteratively, trying to see whether the problem gets 'easier' opening a particular box every day.
First, I realized that opening box 1 serves no purpose at all (except if that's the correct box by pure chance). Because, if you open box 1 and it's empty - you know the cat could've been in any of boxes 2-5, which in turn means tomorrow it again can be in any of boxes 1-5. We're no closer to certain solution. By the same token, box 5 serves no purpose either because of symmetry.
Then I realized box 3 also does nothing. If I find box 3 empty, it means the cat was in 1,2,4 or 5. But, over night, from those 4 boxes the cat could've gone to any of the 5 boxes again, so I'm still no closer to finding it certainly.
So, it leaves 2 or 4, which are obviously symmetrical, so it doesn't matter which one I open. Let's say I open 2, and it's empty. That means the cat could've been in boxes 1,3,4 or 5, BUT, since the box 2 was empty, I KNOW that tomorrow morning it can't be in box 1, because it could've gone there only from box 2, which was empty. So, tomorrow I know the cat is in one of boxes 2,3,4 or 5.
Now, I repeat the SAME process again (but with one fewer box); i simply check whether the problem gets easier (or at least different) if I open one of those 4 boxes. For example: if I now open box 4, and it's empty, it would mean that the cat was somewhere in boxes 2,3 or 5; but, from THOSE boxes, over night it could move to any of the boxes 1,2,3 or 4. Which yields nothing since it's just like 2,3,4,5 only from the other side; it's symmetrical. The same is if I open box 2 again, and it's empty: it means it was in 3,4 or 5, but over night, it might AGAIN move to any of 2,3,4 or 5 - which is the same as that very day.
It quickly follows that I need to open box 3. If it's empty, it means the cat could've been in 2,4 or 5, so tomorrow it has to be somewhere in 1,3,4 or 5. Repeat the same thinking and it follows you need to open box 4 (other boxes get you nowhere, or even backwards). If it's empty, the cat could've been in 1,3 or 5; which means tomorrow it HAS to be either 2 or 4. Open either of them, say 2, if it's empty, it had to be in 4 today, so tomorrow it is in 3 or 5. Open 3, if empty, it had to be 5, so tomorrow it's 4.
So, it's 2,3,4,2,3,4. Since I picked one of 2 possible equivalent boxes in 2 different steps, it means there are 4 possible solutions:
2,3,4,2,3,4
2,3,4,4,3,2
4,3,2,2,3,4
4,3,2,4,3,2
Exactly as the video shows. Like I said, the video solution is more elegant, more mathematical - my approach was somewhat of a 'dynamic programming' thing.
I find the simplest solution is to simply try and corner the cat by first just going through the boxes in an ascending sequence, check the second last box twice (so that the cat is not adjacent to the box you chose and will then move 1 box away) and then go back in reverse. So, if it's 5 boxes, then simply go 1-2-3-4-4-3-2 and there's no way for the cat to evade you. If the cat starts at box 5, you'll find it at box 3 or 4 when going thru 1-4. If it starts at box 3, then you'll find it at box 2, 3 or 4. If it starts at box 2 or 4, then you'll corner it when you're going back from box 4-2.
So if 4 boxes would be 1-2-3-3-2, and 6 boxes would be 1-2-3-4-5-5-4-3-2. Simple, but not sure if it's the most efficient.
But if the cat starts in 2 and moves to 1 during the night ur doomed, also if that happens at any point going up it can sneak through, say if when u get to opening 4 the cat is in 5, it can move to 4 during the night and u won't be able to corner it.
I'd like this one better if the behavior at the endpoints was more explicit and it made clear we're concerned w/ adversarial worst case vs random average case. 1 attempting to move left could plausibly either loop to n (modular), remain in place (attempted to move but failed to; position clamped), or move right b/c only legal move is forced. Not immediately obvious the cat is avoiding being caught vs taking a random walk. If the cat is taking a random walk and the boxes don't loop, I think your best average case is just guess the middle box repeatedly.
I love this puzzle, and would love to turn it into a D&D puzzle. Would this solution work practically with a Schrödinger’s cat (ie. for five boxes, after checking your box on the first day (making your measurement) you roll a die to determine which box the cat was actually in, and for every day after the first, the cat moves according to the original puzzle? Would the puzzle still work if it moved randomly every day? Keep up the great content!
If the cat moves randomly (but still according to the rule), it might actually be easier to catch. I would recommend to chose the move of the cat in an adversarial way if you want your party to actually solve the puzzle.
EDIT: Also, you can choose 4 boxes to speed up the solution.
I don't understand your comment. So do cats move randomly or according to the rules?
And what does Schrödinger's cat have anything to do with this?
@@smallone2351 I called the cat in my proposed variation Schrodinger, because like I said, his starting position is randomized by you (the dungeon/game/puzzle master) after your players "look in the first box" on the first day (making your measurement in this analogy). To answer your first question, again like I said, their starting position is chosen randomly, and then they move according to the rules after that. I hope that was a helpful clarification.
@@brennonbrunet6330 So... That's basically the exact same puzzle as the one in the video. Perfect replica without changing anything whatsoever.
Also, I don't think you understand what Schrödinger cat is.
@@smallone2351 Analogous =/= identical. Was the metaphor a stretch? yeah, I was trying to be clever. Also, yes, it is BASICALLY the same, with a small change here or there (Primarily by introducing a element of randomness to the cat's starting position; if you want more information on how I envision this working feel free to ask nicely 🙃). Which means it isn't a "perfect replica without changing anything whatsoever". Which also means that I achieved my goal, which is to use a slightly modified version of the original puzzle in question to create a concrete macro-scale puzzle for my student D&D game, which kinda sorta maybe allows them to dip their toes (and get a little curious about) the ACTUAL Schrödinger's cat thought experiment.
If you would like me to explain how it is analogous to the actual Schrödinger's cat thought experiment, then I would in turn be happy to explain my thought process... but there are less dickish ways to approach that particular situation.
Lastly, I would caution you to maybe not presume to know what other people do or do not understand about a concept. Cause boy would it be embarrassing if you said something that arrogant only to have me demonstrate how well I understand the thought experiment in question. Wouldn't it?
I love your videos so much! I just found them a couple days ago, and solving the puzzles is giving me so many hours of joy during isolation.
I think I found another solution to this one: search 22334455 etc. It's a little slower than your method (5 guesses if the cat starts in box 2 or 4, 6 guesses if the cat starts in box 1, 3, or 5), but I'm pretty sure it still works.
This was the first idea that I thought of, seems really easier. I wanted to start at 1st box but there is no sense of doing that- if he is in box nr.1 you will catch it with 2nd guess. As the cat HAVE to move you will catch it eventually. There is not way for him to escape.
I don't think this would work. If the cat started in box four, then on the first night it could move to box 3. Then, on the second night, before you check box 3, it moves to box 2 and can just jump around behind you checking.
This doesn't work if the cat is in positions (in order): 54543212. There's problem with your answer, what do you mean by "etc"?
I arrived at a similar flawed conclusion of 22345
The crux of this problem is that on any given day, since the cat could either be in the box next to the one you guessed, OR could have just moved into the one next to your guess, until you've logically ruled out the cat's starting positions, the cat could have slipped past you at any point where you switched your guess from one box to another. Combine that with not accepting just guessing the same box endlessly as a solution (the cat cannot slip past you, but you cannot guarantee the cat will eventually be in your box), and you need some way to rule out cat-starting-box possibilities
I’ll just meow until it meows back and hear where it’s from
Solution I found is to realize that if the cat is in the same group of boxes as you, odd or even, there is no way for the cat to ever pass you. So if you just go 1 to X-1, you WILL find the cat if it started in an odd box, since you will "corner it" (or find it earlier). So if you don't find it, you know it must have started in an even box, so now you just go back to box 1 or 2, depending whether the turn is now even or odd (if the cat can't have started in an odd box, she must have started in an even one, so on odd turns, she is always in an even box and on even turns she is always in an odd box) and repeat. So for 5 boxes, the solution is literally just 1-2-3-4-2-3-4-5. For 6 boxes it's 1-2-3-4-5-1-2-3-4-5-6
Two things: in the odd initial condition, why wait until day four? He's in an even box as early as day 2. Second, where are we getting the information on the initial condition? I thought it was random every time.
Oh jeez, disregard the first point, he explains it later in the video.
01:23 _If you search haphazardly, you might keep missing and never find the cat!_
No, that is not true. Given sufficient time, a properly randomised search would be bound to find the cat in the end.
Good video, though. I enjoyed this topic.
except there IS no end.