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

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

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

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

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

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

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

[@oatlord]

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

[@ZaHandle]

Hired!

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

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

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

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

[@JohnRandomness105]

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

[@user-wb3xw8vo1u]

did you just assume a gender?

[@JohnRandomness105]

@@user-wb3xw8vo1u No, I just preferred "he" over "it". "She" would have assumed a gender.

[@user-wb3xw8vo1u]

@@JohnRandomness105 Im kidding of course :D But that doesnt make sense. He assumes a gender and so does she :P

[@jatloe]

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

[@posingforanimalcrackers4739]

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

[@v6790]

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

[@user-mz7cn9hq8v]

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

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

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

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

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

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

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

[@user-xs1kt5zi4y]

that's wrong

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

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

[@AdelaeR]

@@quindexreal You obviously never smoked catnip ;)

[@Snejk_Y00]

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

[@_PJW_]

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

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

[@matthiasrupp3566]

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

[@saurabh3847]

🤣🤣

[@AdelaeR]

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

[@edwardvilla3228]

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]

@@edwardvilla3228 sounds like a trollge incident

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

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

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

[@derekrocco4344]

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.

[@israelRaizer]

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

[@boguszmakowski2357]

@@israelRaizer actually, the row doesn't have to be straight

[@israelRaizer]

@@boguszmakowski2357 even if it's not straight, it still can't be a circle

[@MrBottlecapBill]

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

[@defaulted9485]

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.

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

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

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

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

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

[@wolven122]

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.

[@josefernandez-xe7cn]

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😀

[@lockheart4425]

no

[@AlfaToTheOmega]

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.

[@GReznov]

the cat can slip into the box you just checked, making you stuck

[@theaxehandle1]

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

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

[@AlexjW3]

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?

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

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

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

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

[@ingang8817]

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.

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

[@manickn6819]

That grid illustration was excellent.

[@RigoVids]

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”

[@Lefty7788tinkatolli]

Presh: Pause the video to try work it out. Me: Lift each box up and see which one's heavier.

[@TehJimlad]

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

[@Nihilous]

Great minds think alike.

[@ygazgge1356]

Schrodinger has a headache.

[@stumbling]

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

[@carbonunit4141]

Fyi, love these types of problems for my children to try to get them interested in STEM subjects. Thank you!

[@Justajawnie]

You can also start at box 1 or n then check that twice then move to the next box. This accounts for the shifting. Is this not a valid solution?

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

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

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

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

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

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

[@Milano972]

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

[@faithhellman402]

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

[@SAL-9000]

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

[@RoyalCryophoenix]

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.

[@mar_sze]

This will not always work.

[@RoyalCryophoenix]

@@Username-2 Whoops, you're right! It was a rather simple example, I don't know how I messed it up. Thanks!

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

[@charlieinabox1164]

Wasn’t clear that one box move was just one to the side and not to ANY one random box. Makes this much easier.

[@charliez6243]

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

[@geoffreymak000]

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

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

[@Bobster536]

Mostly done in my head, read one comment that hinted about even/odd numbers that helped me. 1. Check 2. 2. I know cat cannot be on 1, since he wasnt on 2. Check 3. 3. I know cat isnt on 2, since he wasnt on 1 and 3. I check 4. 4. I know cat is on any of the odd numbered boxes, since he wasnt on 2 and 4. Next round he will be on 2 or 4. Next steppes you check 2 or 4 with assumptions you picked wrong and cat was in the other, then its quick process of elimination. Edit: just read my comment after watching the video and realised its the same solution, just more brute force logic

[@generalcatkaa5864]

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

[@th3smurf692]

Did you use pen and paper? Idk how this can be solved without pen and paper, because you would need memory like a computer 😂

[@generalcatkaa5864]

@@th3smurf692 Yeah I used paper.

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

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

[@topofsm]

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

[@vanpheonix1276]

I just thought, "don't close the box once you open it. That way you can just keep opening each box each morning and once you have opened the second to last box you know where the cat is. Since you left all the other boxes open if you can't see it in the other open boxes it can only be in the second to last box, or the last box, open either of them and if it's not in there then you know it was in the other which means the next morning it will go inside an open 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

[@markmark63]

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

[@kiryls1207]

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

[@icystrangers5482]

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.

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

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

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

[@user-ig8pd9qn5h]

One should pin this remark. It's so important to note the validity of a statement.

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

[@Disblee]

I’ll just meow until it meows back and hear where it’s from

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

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

[@monkaeyes3417]

Is there a solution which checks odd numbers first? There’s more odd numbered boxes than even numbered boxes, so if there’s a solution with another step but it checks odd numbers first then on average it might be faster?

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

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

[@1729andres]

Excellent explanation, very detailed and clear.

[@lawsofminecraft6303]

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.

[@yoyohayli]

Before watching the whole video: I would start one box in from either edge. If the cat is in the single box on the edge, depending on how the rules work if the cat moves IMMEDIATELY or AFTER you close the lid, the cat has no choice BUT to move to that just opened box. So if it moves immediately, you find the cat as it moves because it HAS to move into the opened box. If not, check that box the second night and find it, since it was the only option. In all other cases where that doesn't work and the cat wasn't in that far isolated box, you move one box in toward the other end each night and will find the cat soon.

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

[@OJoMB]

Is it possible to find an equation for this in 2-Dimensions? Instead of the boxes being in a line, they could be on a 2-D plane.

[@zacharymaxwell88]

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.

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

[@frankcastle4814]

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.

[@HackedPC]

Which branch? Electrical?

[@J_PIK]

David Copperfield does a magic trick using this method. You can find it on KZbin. It lets you, the viewer, be in control. He puts shapes on the screen and has you move a certain about of spaces away and lets you pick how many times you move. But in the end David finds where you moved last, making you think it’s magic.

[@SagaEf]

Oh well I wish I knew it could apparently only travel forward, that’s be pretty nice to know

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

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

[@Verklunkenzwiebel]

The best answer from Microsoft's perspective: Open a random box. Note that behaviour and sell it to Stanley, maker of boxcutters.MS isn't interested in the answer, but IS interested in selling your behaviour to advertisers. Since windows 98. And they still do, that's why windows is kinda free.

[@jakemartin4305]

Ok but what happens when the cat just cycles back and forth betwee 2 boxes and like you said your startagy only work if you know of or even starting point

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

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