How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle

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/Sir...
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: mindyourdecisio...
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.co...
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...
"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...
"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...
"Math Puzzles Volume 2" is a sequel book with more great problems. (rated 5/5 stars on 3 reviews) www.amazon.com...
"Math Puzzles Volume 3" is the third in the series. (rated 3.8/5 stars on 4 reviews) www.amazon.com...
"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...
"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...
"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...

[@MindYourDecisions]

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.

[@tristanvandervelde3569]

MindYourDecisions How is it possible to have a comment from 5 days ago while your vid has just been posted?

[@hyoura9120]

Tristan van der Velde youtube logic.

[@MindYourDecisions]

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.

[@manobespadhy4044]

MindYourDecisions love all your videos make similar puzzles, especially the one's like Alice and Bob counting trees!!!

[@cjzojan3166]

MindYourDecisions Can the cat move from box 1 to box 5 skipping the others?

[@MWSin1]

Cats playing by logical and consistent rules... You've never owned a cat, have you?

[@SenselessUsername]

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.

[@Pixel3572]

@@SenselessUsername you’ve also never owned a cat. Cats will also run out just by doing “pspspsps”.

[@ARVash]

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.

[@chandukiran13]

You can never 'own' a cat

[@TheFinagle]

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

[@MrVirus9898]

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.

[@srikanthrjois2929]

The 3rd one seems to be the most logical option😂

[@wingracer1614]

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

[@donsurlylyte]

you are hired

[@oooodaxteroooo]

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

[@NovaGirl8]

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

[@hendrilibrata3353]

Unknowingly to you, the cat got bored and left on day 4

[@bryantimothy8616]

It is not bored. It is hungry..

[@AdityaRaj-mu5yi]

🤖

[@megauser8512]

lol

[@God-gi9iu]

O

[@WinstonHope]

HAHA!

[@joeqmix]

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.

[@2ra0]

ive never seen it as numbers ive just checked the possibilities , thought dealing with numbers is more of a headache to me 😮‍💨

[@Black_Metal]

same lol

[@TimeDagar]

If the boxes are arranged in a circle, and not linear, then yes you'd have the overlap issue.

[@soheil5710]

Well then it would be impossible to solve lol

[@gameclips5734]

then you didn't understand the instructions, 1 is not one number away from 5

[@deepghadiyali2397]

I will check wieght of all boxes and open the heaviest box 🙂

[@wumbatron1291]

think outside the box my friend. well done =)

[@biddi7972]

I open every box

[@4AneR]

@@biddi7972 I put on fire every box and see from where the cat jumps away. Burn them all

[@xxfillex]

The cat decided someone would try this so he hid weights in all the other boxes

[@newaccount90356]

xxfillex geodash shake the box

[@jonathanfowler2932]

The cat is in a superposition, existing in all of the boxes at the same time, until you open them. ;)

[@cosmopolitan4598]

Hahahaaha. I don't like this puzzle anyway. But your comment somewhat elevate my mood,

[@BigBrocc]

What happens if I have a camera in all of the boxes?

[@TotalInfluencer]

+JF If you know the rules, he is not! Your knowledge defines the reality, that's how it works!

[@jonathanfowler2932]

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!

[@rmsgrey]

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

[@JohnRandomness105]

Practical answer: wait until he's hungry enough to come back out on his own.

[@ΑνηξεροςΤρικερατοπας]

did you just assume a gender?

[@JohnRandomness105]

@@ΑνηξεροςΤρικερατοπας 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

[@jatloe]

@@ΑνηξεροςΤρικερατοπας he is sometimes used for a random person

[@jorenvanderark3567]

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.

[@Firzj]

Applying to janitor position at Microsoft Microsoft: solve this riddle 🗿🗿🗿

[@oenrn]

To be fair, it's much more likely that a janitor rather than a programmer will need to find hidden cats in the building.

[@aleisterlavey9716]

Chose Box Box = Invert(Box) Insert:Catnip Box Echo " pspspsps" Loop ( check:Box Endif cat:found )

[@Oktokolo]

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.

[@FUGP72]

Another one of those "interview questions" that has never actually been asked on an interview.

[@doctorcrafts]

In

[@FUGP72]

@@doctorcrafts on is perfectly acceptable. People say "I am going on an interview tomorrow."

[@doctorcrafts]

@@FUGP72 incorrect

[@georgiostsakoumakis7754]

@@FUGP72 incorrect, they should say I am going TO an interview

[@FUGP72]

@@georgiostsakoumakis7754 Either one is fine. Have you honestly never herd anyone say on?

[@pentox6692]

Since it's a programmer interview question, indexing starts at 0.

[@stumbling]

Not necessarily.

[@charleskorndorffer]

[sic] how so? indexing starts at zero

[@brendangolledge8312]

It starts from 1 in FORTRAN

[@charleskorndorffer]

Ah I'm not old enough to know that

[@brendangolledge8312]

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.

[@CostaCostaCosta]

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

[@folbfolb]

I think i know it

[@dominickguntur6136]

...

[@quindexreal]

Can't sell burnt up boxes 8 and 9 appear more than once CAT IS STILL ALIVE THOUGH

[@EaglePicking]

@@quindexreal You obviously never smoked catnip ;)

[@Snejk_Y00]

Day 10: Nimoy buys 5 boxes and hides in 1 of them

[@oatlord]

I can open 1 box? OK, I'll open a box of cat food. Perfect method for finding cat each day.

[@KnakuanaRka]

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.

[@GarryDumblowski]

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.

[@stevekessell9255]

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

[@willscheib6098]

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.

[@posingforanimalcrackers4739]

*****think outside the box*****

[@v6790]

*T H I N K O U T S I D E T H E C A T*

[@todabsolute]

🇹​​​​​🇭​​​​​🇮​​​​​🇳​​​​​🇰​​​​​ 🇴​​​​​🇺​​​​​🇹​​​​​🇸​​​​​🇮​​​​​🇩​​​​​🇪​​​​​ 🇹​​​​​🇭​​​​​🇪​​​​​ 🇳​​​​​🇺​​​​​🇲​​​​​🇧​​​​​🇪​​​​​🇷​​​​​🇸​​​​​

[@iamnotquitesureifiamrightb7423]

*T H I N K I N S I D E T H E C A T*

[@waxyshit9981]

T H I N K O U T S I D E T H E Y O U T U B E

[@Dewald]

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.

[@javabeanz8549]

4) if the room is cold, see which box is warm

[@oldcat1790]

5) bring some food and call the cat, it will leave the box

[@JustMe-ob3nw]

Thank you 👌🏻

[@wdiddy1]

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.

[@ano3661]

6) Use X-ray on each box

[@collinbeal]

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

[@bullpup1337]

welcome to mathematical proof by cases

[@larman36]

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

[@MoonDystopia]

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

[@richardyork2626]

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?

[@tinkerer3399]

Finally an alternate answer which has some merit.

[@irrelevant_noob]

Okay, Richard, now generalize this to the case of N boxes. xD

[@richardyork2626]

@@irrelevant_noob I'd rather not 😆

[@merttosya6391]

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.

[@patttymac]

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.

[@Commenter26]

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.

[@pvt.dicksimmons2225]

If there's a hissing cat in it, maybe you don't want to open that one. How important is it to 'win' anyway?

[@hicknopunk]

🤣🤣

[@verilyheld]

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.

[@CrypticCobra]

How do you know it's not just snakes?

[@hicknopunk]

@@CrypticCobra would we get that lucky??

[@Nuoska]

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.

[@oldtimefarmboy617]

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.

[@andybaldman]

Learn to spell genius correctly before trying to identify it.

[@Nuoska]

@@andybaldman "Lean to spell"? Seriously?

[@oldtimefarmboy617]

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

[@andybaldman]

@@oldtimefarmboy617 I can edit my mistakes. You can't edit stupidity.

[@ejun251]

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.

[@user-pl9yq3fc8u]

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

[@ravenillusion2596]

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.

[@user-pl9yq3fc8u]

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

[@waffiie]

@@user-pl9yq3fc8uthe cat can go back to a box you’ve checked, so it wouldn’t corner the cat

[@TheAnantaSesa]

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

[@matthiasrupp3566]

Day 1: put sand all over the place Day 2: follow footprints

[@saurabh3847]

🤣🤣

[@EaglePicking]

Problem: footprints all over the place! ;)

[@Snejk_Y00]

Another possible problem: the cat actually doesnt put a foot outside of the box, but just hops

[@Rhethardation]

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*

[@pawn1234]

@@Rhethardation sounds like a trollge incident

[@mrmanatee]

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

[@NestedQuantifier]

If you really gotta find that cat fast, set the room on fire.

[@gana7206]

@@NestedQuantifier or just open them all at once

[@michaellautermilch9185]

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.

[@mihai6400]

I guessed 4 4 2 2 3 4

[@abs4008]

@@mihai6400 same. The percentages are 20%, 37.5%, 66%, 75%, 50%, 100%

[@KuroroSama42]

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.

[@senqui]

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.

[@jaam43]

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

[@mbeno.]

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

[@senqui]

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

[@MoonDystopia]

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

[@theaxehandle1]

Everyone is thinking of schrodinger's cat, while I can only think about the dark magician and his magical hats

[@marcinjaroszuk7078]

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.

[@heikoscholz3572]

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

[@FourthDerivative]

Welp, time for my weekly reaffirmation that I'm too stupid to work at Google. Nice puzzle though!

[@chessman88]

at least you could now work at microsoft

[@justgame5508]

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 KZbin video while more than likely trying to solve it in your head

[@mrosskne]

This question never appeared in an interview.

[@Mark-kh1ny]

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.

[@literatemax]

Every single system in the world is *designed* to achieve exactly the results it *does* achieve

[@LiftPizzas]

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.

[@lighthouse6543]

​​@@literatemax "The purpose of a system is what it does"

[@Vcimdarf]

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.

[@dennisb6194]

It can be done in a single sweep. 1,1,2,3,4,...,n total of n+1 steps to guarantee finding the cat

[@IroAppe]

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

[@ElectroNeutrino]

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.

[@davidjames1684]

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.

[@blitzkrieg6076]

If you didn’t have to close the boxes then it wouldn’t matter what order you opened them

[@georgeholloway3981]

What?!

[@davidjames1684]

@@alexandrap4475 The boxes will stay open so eventually we will see the cat. Who cares if we miss it on the first few days?

[@zobook]

But you have to open the box to find the cat. If you leave it open, technically you find the cat BEFORE opening.

[@zobook]

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

[@Wagon_Lord]

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.

[@donjoe7529]

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

[@darrorpsk6148]

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

[@BrooksMoses]

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.

[@TheMisterGuy]

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.

[@drkrishnap]

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?

[@BrooksMoses]

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

[@jcw5288]

Before revealing the solution, I figured out: 1. Pick a smaller set of boxes to keep searching through in an order 2. No need to search corners because the cat has to eventually move out of them

[@TehJimlad]

I'll just go "pspspspsps" and the cat will come to me instead.

[@Nihilous]

Great minds think alike.

[@Sageknot]

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.

[@factgod5]

How to find a cat? Just meow, the cat meaw's back. Just simple as that!

[@sararam7801]

har haaaaaaaar

[@pabloanapedro2740]

When and where gave you heard a cat meowing back? That's unheard of

[@factgod5]

@@pabloanapedro2740 ok Mr. Serious

[@mayankmakadiya2532]

@@factgod5 nice one

[@NotYourAverageNothing]

Is there a solution if the boxes are in a circle?

[@jimmyfoley4634]

Only if you can check more than one box per day

[@heikoscholz3572]

then you would need more conditions to solve it

[@p4xx07]

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

[@ax999]

Yes, if the number of boxes is 2 or 1

[@fredresz7773]

Yes there is. After you check a box, if it's empty set it on fire.

[@kevinfischer4869]

I really struggled with this one! I finally got it after I drew that grid and solved it backwards. I knew 2 or 4 had to be the final box to check, so I started drawing a tree that branched from box 2. It was clear I had to check box 3 as the second to last step, so I wouldn’t have a cat in the 4th box on the last day. The solution came naturally after that.

[@kevinfischer4869]

@VaderxG 3 guesses won’t be enough unfortunately. While solving, it’s best to imagine the worst case scenario; in this case I’d imagine “what if the cat avoided me with perfect strategy?” The only way to guarantee victory, is to cut off every route the cat could take to avoid you, and that will take more than 3 moves to accomplish.

[@mw3579]

It seems like it would be much easier to just shake a treat bag and have the cat come to you😂

[@Ghorda9]

@@kevinfischer4869 not if the cat can only move to adjacent boxes.

[@INeedANewHandle]

@@kevinfischer4869 Best solution i can come up with is O(n)

[@電腦騙徒剋星]

@@INeedANewHandle at first I was driven off instead of finding best strategy , I was finding choosing which position would yield lowest expected number of guess , that runs on n^2

[@notdemomantf2294]

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.

[@escanor-j9d]

that's wrong

[@rosynosyposy]

@@escanor-j9d no

[@tinnderbox3410]

The cat could have been in 4,3,2,3; so in an odd-numbered box after four days.

[@DanXDelion]

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.

[@topneorej]

No five tries, just smell the boxes.

[@ryanlie3270]

Possibly dead cat

[@trevorlambert4226]

So 19 days in total to find the cat, brilliant.

[@irrelevant_noob]

No more than five tries to find out that the cat has left the room to go hunt.

[@manickn6819]

That grid illustration was excellent.

[@lokedemus7184]

That is not how cats operate.

[@ddebenedictis]

Do not EVER let a cat operate, they have not been to med school.

[@BradySteed]

You've obviously never heard of Dr. Cat, MD. doctorcatmd.com/

[@ddebenedictis]

LOL! OK, I will make an exception for Dr. Cat, M.D., although I suspect his technique is way less than purrfect.

[@DerFunkeDesLebens]

Holy moly someone just made me read.

[@cgamejewels]

our cats love hide and peek-a-boo.

[@A.T.-89]

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.

[@John-lf3xf]

The representation isn’t doing something special… you’re still guessing the sequence..

[@A.T.-89]

@@John-lf3xf Well, you're correct. This is not a general solution. Just a visual way to convince myself that the solution even exists!

[@binkythecat457]

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.

[@patrickwienhoft7987]

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?

[@jimmyfoley4634]

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?

[@wendywhaliums]

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.

[@shmel3689]

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

[@wendywhaliums]

@@shmel3689 I know...I said the box 1 over from the left...as in the 2nd box.

[@pascha9141]

it won't work. you check 2, 2, 3, 3, 4, 4 but cat move 4, 3, 2, 1, 2, 1

[@joaosevero4168]

I see we have a programmer here indexing from 0

[@youssefchihab1613]

I understood from this: 1,1,2,2,3,3... Well that doesn't work

[@keithmoore5606]

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?

[@tibodevos9671]

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? 😁

[@mygills3050]

@@tibodevos9671 but if the cat started on even and we wait four days, now it’s odd!

[@tibodevos9671]

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

[@keithmoore5606]

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

[@tibodevos9671]

@@keithmoore5606 yes, exactly 😁

[@geoffreymak000]

This is a really good algorithmic question actually... what a nightmare when your search algorithm is looking for something that changes index lol

[@SAL-9000]

Just say "meow", and when the cat meows back, find and open the box.

[@_PJW_]

As long as you don't open a box the cat is in each box. ('Schrödinger's cat')

[@Supremebubble]

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.

[@hailmary7283]

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.

[@hailmary7283]

Oh wait never mind that doesn't work.

[@Supremebubble]

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.

[@antebagaric1970]

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.

[@jackroby9291]

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

[@gammaknife167]

I couldn't help but wonder whether or not this solution was optimal, and I believe it is. For n=2, this discussion completely fails but it's a trivial case anyway, so take n>2. The strategy in the video succeeds in 2(n-2) moves so we want to show there's absolutely no way we can find the cat always in 2(n-2)-1 moves. In other words, we want to show that for any sequence of 2(n-2)-1 boxes we pick, there's a possible sequence of 2(n-2)-1 cat moves which evades all the picks. I think there's one key idea needed to do this, which is the pigeonhole principle - if you only look inside 2(n-2)-1 boxes then one of the boxes labelled with a number that isn't 1 or n (i.e. one of boxes 2,3,4,...,n-1) is only looked inside at most once (we can't look inside all of those boxes at least twice). Crucially, the cat can reach this box from the right or from the left, since the box doesn't have an extremal label. Label this box as box k. If the human NEVER looks inside box k, as the cat, start in box k, and repeatedly move to k+1 or k-1 and then back to k. Due to the human never picking box k and only being able to pick 1 box each move, the cat can pick boxes to move to such that the human never picks their box. If the human picks box k with their 1st guess, start in box k-1, and use the same strategy as above after. Again, the human can never find the cat. If the human picks box k with their i-th guess where i>1, start in box k-1,k or k+1 such that on the human's i-th guess, the cat is in position k-1 or k+1 (i.e. get the parity right) and such that the cat initial position isn't the human's first pick (i>1 so can hide in box k if necessary). Again, because the human only picks box k once, and in such a way that the cat isn't there when they do so, and since he can only pick one box at a time, the cat always has a choice of boxes that avoid the human. TL;DR find a box only picked once, there's always a way to move back and forth between that box and it's neighbours such that the human never finds you.

[@timwoodhams217]

While this method works to ensure you catch the cat, however it doesn't result in lowest average time. Always searching the box with the highest probability of having the cat, which are not equal due to ends of the boxes and your picks. While I've done enough simulations to convince myself of this has anyone done a mathematical proof?

[@lockheart4425]

you must not have studied greedy and approx. algos.

[@YoutubeModeratorsSuckMyBalls]

Wait why does it fail for case n=2? We open the box 1, either we win, or we know that cat is in box 2. In Day 2, we know that cat is in box 1, so we open box 1 again, so we win

[@Leastmachine]

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.

[@Leeki85]

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.

[@williamthewizard7477]

I would open a can of tuna...

[@jadsaad6608]

4:45 I didn’t understand why should I wait 4 days? By the day 2, the cat would go to an even number (box 2 or 4). If I open box 2 and don’t find her, then on day 4, it will surely be in box 4

[@mrosskne]

you don't know if it started in an even or odd box.

[@petar1401]

This is over a year late, but will make myself feel better by replying. You don't just sit on your ass for 4 days, waiting for the cat to jump around. You follow the steps of the first case: assume the cat is in an even numbered box. Day 1. check box 2 Day 2. check box 3 Day 3. check box 4 If you have not found the cat by now, it means the cat started in an odd number box. So you start the process of finding it on day 4, because you already spend 3 days searching for it.

[@ygazgge1356]

Schrodinger has a headache.

[@stumbling]

I have five cats in five boxes but only one of them is real.

[@fulcrum8583]

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.

[@benr77]

the solution does not work. he already explained that the cat can move to a box you have already checked. So if on day 1 you check box 2 and the cat is in box 3, then at night the cat can move to box 2. in the morning of day 2, he checks box 3 but that cat may have moved from 3 to 2. Also, the cat may have started in box 1, so checking box 2 does not eliminate box 1. good grief. the only way I can see doing it, since the cat alternates even/odd numbered boxes every night, is to start at 1 and check in order to 5. if the cat started on an odd number (3 or 5), you will have found it this way. if the cat started on an even number, you will have missed it. In this case, recheck box 1. this will force the cat to jump onto an odd number as well. then recheck the boxes in order until you find the cat. This would require checking 9 boxes, assuming you could not find the cat until the last possible box.

[@herumuharman6305]

For the 4 box, after day 2 and you figured the cat start in an odd box, you could mirror the boxes and show that you could solve it using the same previous 2 steps.

[@TheCyntos]

No, beacause with two boxes, mirroring switches evens and odds (4 becomes 1, 2 becomes 3)

[@herumuharman6305]

@@TheCyntos That's the point. You started with guessing the cat in an even box. After not finding the cat on the second day, the cat would have started in an odd box. By mirroring the position on the third day, the cat would've been in an even box, so you could just repeat the previous 2 days steps, pick no. 2 and then no. 3.

[@TearTheRoof0ff]

@@herumuharman6305 Well, provided you still do 2,3,3,2, you're golden. I suppose mirroring the boxes illustrates it's the same concept in reverse in another way.

[@JohannFelipeVoigt]

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!

[@MicroYeti]

Who thought of Schrödinger's cat when they saw the video

[@icefreezer7]

I thought of schrödingers box

[@ddebenedictis]

Sure, that's a pretty clear connection, and I would not be surprised if Presh intended it. I think a lot of his math geek audience is also interested in quantum mechanics.

[@TotalInfluencer]

If you know the rules, the transitions of the cat are defined. So, it is not that case!

[@sarpkaplan4449]

Jamie Read exactly

[@ddebenedictis]

When I hear the words "box" and "cat" I think of scooping feces out of litter.

[@JackPullen-Paradox]

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.

[@foxtemple1952]

First, I want you to notice that, independently of the number of turns that have passed, two optimal games will always develop in the same way, given that they start with the same cat position and box opened. So, if an optimal game develops with a series of coordinates and the box checker still wins, than all of those coordinates that appeared throughout the game are winning initial coordinates as well. With that in mind, I will explain my solution to this problem. I will be writing cat and box opened positions with coordinates (box, cat). Please, note that (a, b) = (6 - a, 6 - b) and that the game is won when box = cat. 2 -> 3 -> 4 -> 2 -> repeat We always start with the coordinate "box" equal to 2. The cat can start in any of the remaining 4 boxes. First case: (2, 1) -> (3, 2). Now, the cat has two options: a) -> (4, 1) -> (2, 2). b) -> (4, 3) -> (2, 4) -> (3, 5) -> (4, 4). Second case: (2, 3). This is equal to (4, 3), which, from the first case (b), we know is a winning condition. Third case: (2, 4). From the first case (b), we also know that this is a winning condition. Fourth case: (2, 5). This is equal to (4, 1), which, from the first case (a), we know is a winning condition. Therefore, 2 -> 3 -> 4 repeating is a winning strategy. Please, correct me if I'm wrong!

[@Smouv]

2 years late, you're correct in the assumption that your solution (2-3-4 2-3-4) is as optimal a strategy as the one explained in the video (2-3-4 4-3-2). However, it comes with a big caveat. Your method of 2-3-4 2-3-4 doesn't scale to situations where you have even numbered boxes. If you have 6 boxes to choose from, you'll notice that 2-3-4-5 2-3-4-5 will not actually guarantee that you catch the cat while 2-3-4-5 5-4-3-2 *does* guarantee you catch the cat. This is because if the cat started out in an uneven box, after going through 4 boxes the cat will still be in an uneven numbered box rather than an even numbered box, so your first number of the 2nd sequence would also need to be uneven to compensate. This only happens when you walk the same sequence backwards the 2nd time around.

[@irrelevant_noob]

@@Smouv fwiw, because of parity, we can expand this approach to the "even total number of boxes" case by adding a 1 before the second sweep. So 2-3-1-2-3 for 4, and 2-3-4-5-1-2-3-4-5 for 6, and so forth.

[@Devastish]

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.

[@SomeGoogleUser]

This is exactly the solution I came to using similar logic

[@Madkangaroo]

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.

[@speedstyle.]

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

[@dmitrikonnov922]

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.

[@kruksog]

I think some initial examples would help with understanding the rules. My initial solution was to always pick the same box, but I didn't realize the cat could loop. The rules obviously do allow for it, I'm just saying it would have been nice to give some example cat-movement first. Also, what happens when the cat gets to box n? Are the boxes in a circle - i.e. can the cat go from n to 1? Anyway, nice video.

[@musicexams5258]

It can't loop Because if it could loop, it would become literally impossible

[@viperhd70]

4:20 I don't understand why you continue until the 4th day, at the 2nd day, the cat will also be in an even numbered box. EDIT: ok, the reason is actually only explained later, as you will only reach day 4 if you missed catching the cat in the first 3 days and therefore know it started in an even box.

[@Solkefra]

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.

[@makokx7063]

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.

[@Tehom1]

0:32 Thanks for a good puzzle, Presh! I'm assuming that you require a perfect strategy, so that even if the cat anticipates your moves perfectly, it still gets found. Here's a sequence that will work. For each step I'll say what box you open and which boxes it can be in if you haven't found it. As you did, I will start with box 4. 4: {1,2,3,5} 4: {1,2,3} 2: {1,4} 2: {3,5} 4: {2} 3: {1} 2: {} -- the empty set. We have found the cat by this time. With that in hand, we can see a more regular approach: 4: {1,2,3,5} 4: {1,2,3} -- here we are moving one step each time 3: {1,2,4} 2: {3,5} -- Now every other box is empty. Left alone, it will just alternate between {1,3,5} and {2,4} forever. We now walk from one end to the other end. 4: {2} 3: {1} 2: {} A more general strategy for N boxes labelled 1 thru n-1: 2: {1,3,...n} 2: {3,...n} 3: {2,5,...n} 4: {1,3,5,...n} 5: {2,4,6,...n} 6: {1,3,5,7,...n} 7: {2,4,6,8,...n} After you do that, every other box is eliminated. Let's say only the even boxes are potential cat boxes. (If it's the odds, the strategy is the same, just we start one turn ahead because 1 is already empty). Now at each step we're going to eliminate the lowest box. Since we eliminated every other box, we can move twice as fast as the possible cat can move. 1: {3,5,7,9,...n} 2: {4,6,8,10,...n} 3: {5,7,9,...n} Continue this procedure and there will be zero potential cat boxes left.

[@jordanliu9747]

Tehom Doesn't work (the one he showed in the video is the only one that does) 1.2.3.4.3.2.3 would beat you The cat can move from box 2 to 3 on day 3

[@Tehom1]

You are right. That is, my first solution doesn't work. Second one does.

[@johnnyllooddte3415]

2,2 ,4,4

[@irrelevant_noob]

@@Tehom1 The issue was at Day 3, where you say 2: {1,4} but the cat can also be in box 3 (coming from 2). > N boxes labelled 1 thru n-1: That's an oxymoron. You either have N boxes which can't be 1 through n-1, or you have boxes labeled 1 through n-1 which are N-1 in total. But enough nitpicking, i think it's time to acknowledge you're right that the second solution does work. :-) Although imo it might help to include a bit more of the options: 2: {1,3,4,...n} 2: {3,4,5,...n} 3: {2,4,5,6,...n} 4: {1,3,5,6,7,...n} 5: {2,4,6,7,8,...n} 6: {1,3,5,7,8,9,...n} 7: {2,4,6,8,9,10,...n} Also, you don't need the first check ( don't need to start with checking box 2 _twice_ ), we can go directly to: 2: {1,3,4,5,...n} 3: {2,4,5,6,...n} Which is exactly the solution i came up with. Sadly, for even Ns we both perform an extra check since we go left-to-right both times and thus we have to add an extra check on box 1 to fix the parity.

[@zubetto85]

Great puzzle! Asking for general solution is like a hint that some pattern should exist. Unfortunately, I did not take advantage of this hint.

[@thphgamer3455]

the problem said that each morning you can open but didn't say that you need to close the box, so just open every single box

[@markmark63]

Question 2: Calculate the probability that the cat is in your neighbor's box.

[@justdoitlater9507]

is this solveable if the cat can jump from box 5 to box 1 (or in the general case from box n to box 1)

[@pengin6035]

Impossible.

[@pengin6035]

Look at it like this. The cat has always the possibility to move into two boxes, never just into one, so you can never know for sure in which the cat will move in. In the case shown the video it's just possible because it has to move from 5 to 4 or from 1 to 2, so if we know the cat was there in the last night we can predict where it will be in the next night. But here it could also move to the other end so we can not know the answer.

[@rmsgrey]

Another way of looking at it is to consider what you know on day 2, depending on where you checked on day 1. If you checked box 1, then on day 2 the cat could have moved to any box. If you checked box 3, 4, 5, etc - any box except box 2 or box n-1 - then the cat could be in any box for day 2 because the boxes it could have moved to from the one you checked also have other boxes they could have moved there from. It's only if you check box 2 (or box n-1) on day 1 that you eliminate a possibility on day 2 because a cat in box 1 (n) on day 2 can only have come from box 2 (n-1) on day 1. If the cat could also have come from box n (1), then you can't eliminate box 1 (n) after all, so you can never learn anything to start you off.

[@bobbyv369]

If you jump 2 boxes each night you will find it and catch it

[@BigDBrian]

It's not. The ends are essential to the method. Also, just to make matters worse, making it cyclical can break the even-odd situation. (going from 5 to 1 goes odd -> odd)

[@Atoll-ok1zm]

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.

[@senqui]

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.

[@rappingtrex579]

5432

[@shan79a]

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.

[@ZomgLolPants]

Is it just that the cat can move, or that the cat must move? Something as simple as that can completely reframe the problem

[@Lodinn]

It must. Otherwise it's not solvable really.

[@carletonharkins805]

The question itself fails to address the following: After opening a box, don't put the cover back on or take the box away. The cat can't hide in a open box or a removed box, just the remaining closed boxes. The question statement did not indicate that all boxes are to remain 'in play', after one or more are opened.

[@lordsorcerer3885]

Yes, this was an oversight since it's the simplest solution. Remove the middle box and the cat's options are divided and reduced. This was my solution and then after the pause I didn't understand why the cat moved into a non-existent box. This is just sloppy and should have been specified as a rule.

[@bruhbro1181]

You have to take the box away, if its open the cat may escape

[@tinkerer3399]

@@lordsorcerer3885 Not at all sloppy. One big reason why these questions use real world terms rather than programming terms is to test both the subjects basic reading comprehension and attitude. As a programmer you are often required to work with an incomplete set of specifications. So this test is also determining your ability to figure out the real question being asked. Anyone who responds like you did would probably require more hand holding to comprehend instructions since without the caveat of the boxes being closed again the question makes much less sense (as in the equivalent situation being described you cannot generally "leave a box open"). Additionally even if that were the case your solution is still the wrong one, the real right answer in that case is to open the 2nd box and then the 4th box (or the 4th then the 2nd). Opening the 3rd box first is literally the worst possible first option. And for attitude anyone who responds with something like "shake a bag of cat treats" is essentially flipping off the interviewer. Very punk rock, but unfortunately not a great way to get hired.

[@Zbyhonj]

So this took me a long time (probably over 2 hours). Most of this time was spent searching for mistakes I made while adding fractions and correcting them. I did all that in order to calculate the probability of the cat being in each individual box on each individual day. ...and while that certainly can be done, imagine my tremendous excitement when I solved the puzzle and realized IT WAS NOT NEEDED. Moral of the story: you can brute force a math problem through a sub-optimal method... but you shouldn't. Anyway, if you open the boxes in the order 2-2-3-4-4-3-2, you are guaranteed to find the cat by day 7. Your chance to find it on day 1 is 20%, on day 2 it's 37.5%, on day 3 it's 30%, on day 4 it's 42.86-ish, on day 5 it's 62.5%, on day 6 it's 50% and on day 7 it's 100%. ...I really hope this is not wrong.

[@charlesd.4403]

it's correct! but you can be faster! if you do 2-3-4-4-3-2 you are also guaranteed to catch the cat unless I overlooked something

[@hicknopunk]

@@charlesd.4403 you might be right. I figured my 2,4 2,4,2,4 etc method was the best brute force.

[@Padilla1]

@@charlesd.4403 cat starts 1, goes back and forth between one and two, doesn't catch him :(

[@charlesd.4403]

@@Padilla1 yes! The cat would be in box two at the end ;)

[@bruhmoment748]

There is a simpler solution: Suspend each box in approximately 10 liters of concentrated sulfuric acid.

[@randymillhouse791]

Run the electric can opener. The cat will reveal itself.

[@kevomtb6882]

I would have installed security cameras recording the boxes, and next day I check the recording

[@ddebenedictis]

But to your rudimentary camera, the quantum cat would appear to have entered all five boxes simultaneously.

[@rayid4027]

Lame dude😂

[@justinwhite2725]

I'm usually good at these, but this one has me stumped. I can only get as far as opening box two twice in a row to rule out the fat being in box 1 or 2. After that if I look somewhere else the box might be in 2 again.

[@gregbroyles3240]

not if you then check box 3 twice

[@birdlegscass]

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

[@KineticManiac]

I've yet to watch the full video, but I believe the pattern 2234432 will always catch the cat in 7 moves or less. Other similar patterns such as 4432234 are also likely to work. Now onto the video. EDIT: So it is possible to win in 6 days only. Dang it, I can't brag. And it's not even a huge trick, I just didn't need that first 2 in the beginning. Well, honestly I have once seen a problem very similar to this one before, so I can't really brag anyway. Anyway I have only watched part of the video, I'll try to solve the bonus.

[@janlinden7332]

224432 was my answer

[@junj1023]

224432 solves too

[@junj1023]

@@janlinden7332 Yeah!!! Mine too!

[@monrealis]

Random guessing method is quite good too: 1-0.8^50~=.9999857276.

[@silasprins3861]

what are you calculating

[@monrealis]

A probability to catch the cat in 50 attempts by guessing randomly.

[@hyrekandragon2665]

That stat is skewed is because you can change the number of attempts to give you a higher probability. Besides 50 attempts is actually pretty bad for 5 boxes when you can guanratee you will find the cat in a lot less attempts.

[@fisheatsyourhead]

This is more of an optimisation problem than a solution problem. It's like a computer program, you want it to be as fast as possible

[@kfftfuftur]

Vytenis Bivainis you know that after 6 random trys there is still more then a 25% chance that you might not have found the cat.

[@brennonbrunet6330]

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!

[@cmilkau]

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.

[@smallone2351]

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?

[@brennonbrunet6330]

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

[@smallone2351]

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

[@brennonbrunet6330]

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

[@00metta00]

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.

[@jacksainthill8974]

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.

[@irrelevant_noob]

except there IS no end.

[@daniel-hp4ue]

just go out at night and watch what box it goes into talk about thinking outside the box....

[@Mobin92]

You should mention that the boxes get closed again. I thought that the cat can't go into an already opened box.

[@nil-8026]

Why would you assume that?

[@charliez6243]

I’m getting Princess Bride vibes from this video. INCONCEIVABLE!

[@faithhellman402]

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.

[@faithhellman402]

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. 🤦‍♀😂

[@unclenegan6694]

or you just open all of them at one so you can go eat breakfast

[@_Vengeance_]

It's easier to eat breakfast if you just keep the cat in the box

[@HAL-mv2cw]

First thing that came to my mind when seeing cat and boxes : Schrödinger

[@cg0825]

The cat is simultaneously dead and alive until you open the box--

[@FireStormOOO_]

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.

[@kelvincabrera4517]

Thanks for this. I'm genuinely curious about how the cat could be found if the five boxes were arranged in a circle. Would we ever reach a point of absolute certainty then?

[@JerusalemStrayCat]

I tend to doubt it, at least with methods that use the logic in this video. These methods rely on the cat only being able to move to one box if it is at the end.

[@kappalol4780]

No

[@crackwitz]

Someone proved that you can just keep going around in the same direction and you will eventually catch it... IF it's not just doing the same thing. The dude called it the "always-go-left" algorithm.

[@seansean1728]

No because this system has hysteresis: the system has positions which “remember” where the cat was the previous turn. (The right most and left most box implies cat was in second or fourth respectively, and will also be there next turn.) A circle of boxes has no hysteresis.

[@dernett]

There is no deterministic strategy because with a circle the cat always has 2 choices for where to go. Let's say I wrote my strategy down as list of boxes to check: B1, B2, B3, etc. The cat will choose a starting box different from B1, which is possible since there are 4 boxes to choose from. At step k, the cat can always avoid going into box Bk+1 since there are two choices and at least one of them will be different from Bk+1. Instead of having boxes arranged in a circle you can generalize to any directed graph. Then a strategy does not exist if there is a subgraph with the property that each vertex has 2 edges.