From The Guardian's Mathematics column today:
A straight corridor has 7 doors along one side. Behind one of the doors sits a cat. Your mission is to find the cat by opening the correct door. Each day you can open only one door. If the cat is there, you win. You are officially smarter than a cat. If the cat is not there, the door closes, and you must wait until the next day before you can open a door again.Clarifications at the link. The answer will be posted at The Guardian later today. Some reader here may be able to solve this.
If the cat was always to sit behind the same door, you would be able to find it in at most seven days, by opening each door in turn. But this mischievous moggy is restless. Every night it moves one door either to the left or to the right.
How many days do you now need to make sure you can catch the cat?
Cat photo for those who don't like maths:
That is intriguing. It seems impossible, but I'm going to chew on it a while before looking at the answer.
ReplyDeleteI wonder if it's easier to figure out if you mentally flip the problem - pretend you are the cat, and then try to find the search pattern that you can't dodge. (Intelligent choices on the cat's part could also happen randomly, so any solution to the puzzle must also cover that scenario.)
Hah, got it! Well, got close. I had an extra move in setting up my solution that turned out not to be necessary. But I found the same pattern that the author did.
ReplyDeleteI've been fighting with a medical condition that has lopped a chunk off of my problem solving abilities. It's a big deal for me to be able to do this again.
Wow, this one disturbed my sleep. Yesterday night I tried something round 2, 4, 6 but cat always could defeat me forever. This morning woke up at 5 and found that as the cat is always on an even, odd pattern, I could squeeze it... finally... Let's see if I am right when solution is given.
ReplyDeleteA link to the solution has been added to the original source article.
DeleteIt was too hard for me ... or at least, too much for the investment I was willing to put into it ... but having seen the solution I can examine how it works from a different angle. (To me, understanding a solution is more interesting than finding it.)
ReplyDeleteLet phase = parity (door + day), where door is the door number, day is the day number, and parity of course means whether a number is even or odd.
The cat's phase is constant. If it's even it stays even, and if it's odd it stays odd. Your phase can change, but on any given day you will be in or out of phase with the cat. Your phase will be constant if you choose to follow the same rules as the cat for a while, but you can change it at any time.
If you are in phase with the cat and you do a sweep of all the doors, then you and the cat must cross paths at some point. But if you are out of phase then the cat will pass you by unseen.
Therefore, you are guaranteed to find the cat if you first sweep all the doors keeping your phase even and then sweep all the doors again keeping your phase odd. In the first sweep, you are looking for an even-phased cat, and in the second sweep, you are looking for an odd-phased cat.
That would be good enough if all we cared about was finding the cat eventually, but we are asked to find it in as few days as possible.
To make the solution efficient, we observe that if the cat is behind an even-numbered door on Day 1 (i.e. its phase is odd), then you are guaranteed to cross paths if you sweep from Door Two to Door Six, with no need to check the first door or the last.
Now all you need to do is sweep all the doors from 2 to 6 keeping your phase odd, and then sweep all the doors from 2 to 6 again (or from 6 to 2 as in the official solution; it makes no difference) keeping your phase even.
That's five doors in the first sweep and five again in the second sweep, for a total of ten doors.
I hope this way of looking at it is helpful for readers who want to understand the solution a little more deeply.