Here is a somewhat trickier puzzle – Catching a mouse
There are five adjoining rooms – linearly arranged (from left to right). You know there is a mouse in one of those rooms. You also know that the mouse, every night moves to the adjoining room – either left or right. It does not stay in the same room two days in succession – meaning it will definitely move. However, it is completely random whether it will go left or right – unless, of course it is in one of the end rooms in which case, it has to go to the other side.
Now, you are allowed to open any one random room in the morning. If the mouse is there, you can trap it and catch it. But if you do not find it, you are not allowed to go to other rooms. You have to come back the next day and open any room you want again (including the one you opened to today – totally your choice).
What is the strategy you will use (of targeting rooms to open each morning) to eventually catch the mouse?
I think the best strategy is to choose one room and open that room everyday. The room in the middle can be chosen for the heck of choosing.
The probability that the mouse is in a given room is 0.2 everyday.
Works? or no?
What if the mouse oscillates between 1 and 2 ad infinitum?
The same problem if you choose any room. Here, in a probabilistic model, with zero previous knowledge, i think the strategy is to fix on a room is the best because the randomness is on the mouse movement and we reduce the randomness on our choice.
If it were a deterministic model, then the strategy would be entirely different. In a probablistic model, the expectation (E=Probability X occurance) is that the mouse will be caught in 3rd day. Can the mouse oscillate between 1 and 2 (or 4 and 5) till infinity? Sure, it is possible. But not probable.
Ambarish, there’s a way to catch it in all probable cases
Ok, thinking then….need a charminar.
Open door 2 on 2 consecutive mornings. If not found, then definitely the mouse is not in room1. Open door 4 next 2 mornings. If not found, then definitely not in 5. So, remaining rooms, 2, 3 and 4. Room 3 on 2 consecutive mornings will give the catch.
Ambarish not quite. The days might be getting mixed up. By hitting room 2 successively, you made sure that if the mouse was in Room 1 or 2 on DAY 1, you got it. Now doing the same with room 4 on day 3 and 4, you made sure that you caught it if it was in room 4 or 5 in DAY 3. Not DAY 1.
An example to show the algo not working
day 1 room 5 you open 2
Day 2 room 4 you open 2
Day 3 room 3 you open 4
Day 4 room 2 you open 4
Day 5 room 1 you open 3
Day 6 room 2 you open 3
Correct. more to think.
This is too good to pass up.
if I am given very little time to make a decision, Id go with my gut instinct ,and choose the center room and keep opening it until I find the mouse. But the correct answer (and I admit I dont know yet) I think may be deduced by maximizing the probability of encountering the mouse which itself looks like sum of a series of decreasing probabilities. Reminds me that Bayes Theorem needs to be applied and I could never do it right. But this strikes close to home because we have a mice problem and I constantly trying to outsmart mice with various humane traps and strategies which the critters quickly learn to avoid.
Opening the doors in the the sequence of 2-3-4-2-3-4…. I can write up the dry run, am i in the right direction to catch it? 🙂
First I thought it won’t work. But actually it will. In fact, yours is a better solution than the one I had come up with. Yours has one step shorter than mine.
would like to know what is the other solution?
Debajyoti, I will post the generic solution for “n” rooms later. I am still cross-checking after applying your method which cuts out my first step.
Rajib Roy look forward to the results for “n”
Debajyoti, I am pretty sure it is 2,3,4…. n-1 and then repeat that with the possibility of having to have a gap day depending on whether n is odd or even.
Pradeep has come up with an alternate solution. Think about it as a symmetric problem for the second iteration- then there are multiple answers possible. In my case, I started with Room 1 and then 2..3… 4 and then iterate one more time after waiting out a day. Your solution is shorter by that extra step not required.
Open one of the rooms leave a hungry cat and it will take care.
Open room 3 everyday…
In my opinion, there is a chance the mouse is never caught no matter how many times you open the doors. Based on this discussion I see 2 variables that need to be optimized 1. number of days 2. probability of catching the mouse [since it is never going to be 1]. There is no one single solution I think. Thoughts?
I need to make some time to explain the answer that Debajyoti and Pradeep have given
ANSWER:
I had come up with the strategy of 1,2,3,4… n-1 and then start over again (with the possibility of having to wait out one day depending on whether n is odd or even) and by the time you get to n-1 the second time, you would have caught the mouse.
But Debajyoti and Pradeep had a shorter solution. They realized that I do not need to do 1 in the beginning at all. So, I am going to explain their answer.
I will answer in the generic case “n” rooms and then show the specific case here with 5 rooms.
They said if you do 2,3,4,2,3,4 you will catch the mouse. (worst case scenario 6 days to catch the mouse). So, why does this solution work?
Realize that there is very little you can say about the mouse’s movement. We do not know where it started and which direction it would take any given day.
The ONLY KNOWN FACT is this – if it is in a ODD room today, tomorrow it will be in an EVEN room and vice versa. And actually, that is enough knowledge to outwit the mouse!!
On Day 1, the mouse can either be in an ODD room {1,3,5,7,9….} or in an EVEN room {2,4,6,8…}. (In our problem of course this is {1,3,5} and {2,4} )
EVEN CASE. Let’s start with the assumption the mouse was in an EVEN room. (We will do the ODD CASE later; there are no other cases possible)
On Day 1, we opened “2”. The mouse could have been in 2 or 4 or 6 or 8 (remember we have assumed it was in an even room). Well, if it was in 2 to begin with, we got it. If not, it is obviously in 4, 6, 8 …. .
On Day 2, the mouse has to be in one of the odd rooms 3, 5, 7, … (but not 1 since it cannot jump to 1 from any of the possible rooms 4, 6, 8 …..). On that day, we opened Room 3. If it was there, we got it. If not, obviously it was hiding in one of the rooms 5,7,9….
Day 3: If we did not get it on Day 2, where could the mouse go the next day? Remember, it was in 5 or 7 or 9…. So, it can go to one of the even rooms 4,6,8,…. Guess where we are scheduled to go on Day 3? Room 4. If it was there, we got it. If not…. it means it is in 6,8,10….
Next day it can go to 5,7,9…. And that is the day we attack room 5…
You see how every single day, we are flushing the mouse to the right till we reach room n-1 (which would be 4 in our specific problem).
On that day we either got the mouse or we conclude that our original assumption that it was in an EVEN room was WRONG.
ODD CASE: The mouse was on in an ODD room on day 1
So, what do we have now. We have a fool proof way to catch the mouse if the mouse was in an even room on Day 1. But now, we know that it was actually in an odd room.
Do we know where the mouse is today – even room or odd room? We do!! On day 1 it was in an odd room (or else by now we would have caught it) and we know how many days have passed from that day to today. So we know for sure whether the mouse is in an odd room or even room TODAY.
If TODAY is EVEN, guess what – you do what you did in EVEN CASE above because you have a foolproof way of catching it once you know it is in an EVEN room.
If TODAY is ODD? We wait for a day. Perhaps smoke a Charminar like Ambarish suggested. Tomorrow you are guaranteed that the mouse will be in an even room. So you run your EVEN CASE as above now 2,3,4…. By the time you reach n-1 you are guaranteed to catch it!!!!
Absolutely foolproof.
Now, you probably realize that the original problem and also after the first flush, it is a symmetrical case (which end you start from never matters)
Therefore, you can extend the original solution 2,3,4,2,3,4 to the following solutions too:
2,3,4,4,3,2
4,3,2,4,3,2
4,3,2,2,3,4
So the answer is… you go 2,3,4,5… to n-1. If you still do not have it, if “n” is odd, then do 2,3,4,5… to n-1 again. If “n” is even, wait a day and then do 2,3,4,5… to n-1. The well laid plans of mice will be undone by those laid by men. Shakespeare be darned!!
nicely elaborated! Rajib Roy
very detailed explanation but I am seeing an issue in your logic above.. flushing is not possible because mouse can evade capture forever [hypothetically: if it knows which door you are opening in advance] This means, we cannot with certainty ever catch the mouse (key word being “certainty”). For example.. as you move 3 to 4.. the mouse can move from 4 to 3 and oscillate as you try to flush it at 5,6,7..n. Thoughts?
No he cannot. Let’s take the example you cite. I was in 3.
In EVEN CASE, it was on an even room on the first day when I hit 2. But now I am in 3. The mouse got one day to move. So, it is in an odd room. It CANNOT be in room 4 as you have suggested.
But of course, you can say that maybe it was not EVEN CASE. Which means it was the ODD CASE (one day 1 it was in an odd room) Indeed, then, I will miss the mouse in this round and go all the way to 4.
So on day 1, it was in an odd room, I hit 2
day 2, it was in an even room, I hit 3
day 3, it was in an odd room, I hit 4. (I did not find it. I realize it is the ODD CASE)
Note that on the next day – day 4, the mouse HAS to be in an even room (prev day it was in an odd room).
So, I simply do the EVEN CASE – 2,3,4 again.
Makes sense?
Yes, given the key assumption “It does not stay in the same room two days in succession”.
ANSWER:
I had come up with the strategy of 1,2,3,4… n-1 and then start over again (with the possibility of having to wait out one day depending on whether n is odd or even) and by the time you get to n-1 the second time, you would have caught the mouse.
But Debajyoti and Pradeep had a shorter solution. They realized that I do not need to do 1 in the beginning at all. So, I am going to explain their answer.
I will answer in the generic case “n” rooms and then show the specific case here with 5 rooms.
They said if you do 2,3,4,2,3,4 you will catch the mouse. (worst case scenario 6 days to catch the mouse). So, why does this solution work?
Realize that there is very little you can say about the mouse’s movement. We do not know where it started and which direction it would take any given day.
The ONLY KNOWN FACT is this – if it is in a ODD room today, tomorrow it will be in an EVEN room and vice versa. And actually, that is enough knowledge to outwit the mouse!!
On Day 1, the mouse can either be in an ODD room {1,3,5,7,9….} or in an EVEN room {2,4,6,8…}. (In our problem of course this is {1,3,5} and {2,4} )
EVEN CASE. Let’s start with the assumption the mouse was in an EVEN room. (We will do the ODD CASE later; there are no other cases possible)
On Day 1, we opened “2”. The mouse could have been in 2 or 4 or 6 or 8 (remember we have assumed it was in an even room). Well, if it was in 2 to begin with, we got it. If not, it is obviously in 4, 6, 8 …. .
On Day 2, the mouse has to be in one of the odd rooms 3, 5, 7, … (but not 1 since it cannot jump to 1 from any of the possible rooms 4, 6, 8 …..). On that day, we opened Room 3. If it was there, we got it. If not, obviously it was hiding in one of the rooms 5,7,9….
Day 3: If we did not get it on Day 2, where could the mouse go the next day? Remember, it was in 5 or 7 or 9…. So, it can go to one of the even rooms 4,6,8,…. Guess where we are scheduled to go on Day 3? Room 4. If it was there, we got it. If not…. it means it is in 6,8,10….
Next day it can go to 5,7,9…. And that is the day we attack room 5…
You see how every single day, we are flushing the mouse to the right till we reach room n-1 (which would be 4 in our specific problem).
On that day we either got the mouse or we conclude that our original assumption that it was in an EVEN room was WRONG.
ODD CASE: The mouse was on in an ODD room on day 1
So, what do we have now. We have a fool proof way to catch the mouse if the mouse was in an even room on Day 1. But now, we know that it was actually in an odd room.
Do we know where the mouse is today – even room or odd room? We do!! On day 1 it was in an odd room (or else by now we would have caught it) and we know how many days have passed from that day to today. So we know for sure whether the mouse is in an odd room or even room TODAY.
If TODAY is EVEN, guess what – you do what you did in EVEN CASE above because you have a foolproof way of catching it once you know it is in an EVEN room.
If TODAY is ODD? We wait for a day. Perhaps smoke a Charminar Ambarish suggested. Tomorrow you are guaranteed that the mouse will be in an even room. So you run your EVEN CASE as above now 2,3,4…. By the time you reach n-1 you are guaranteed to catch it!!!!
Absolutely foolproof.
Now, you probably realize that the original problem and also after the first flush, it is a symmetrical case (which end you start from never matters)
Therefore, you can extend the original solution 2,3,4,2,3,4 to the following solutions too:
2,3,4,4,3,2
4,3,2,4,3,2
4,3,2,2,3,4
So the answer is… you go 2,3,4,5… to n-1. If you still do not have it, if “n” is odd, then do 2,3,4,5… to n-1 again. If “n” is even, wait a day and then do 2,3,4,5… to n-1. The well laid plans of mice will be undone by those laid by men. Shakespeare be darned!!