6
$\begingroup$

You are chasing a mouse living in a row of eight houses. Every night the mouse moves from the house it is in, to an adjacent house, and stays there the whole day. Apart from this, you have no a-priori information on the mouse's locations nor on its movements. However, you do have two mousetraps available. If you leave a mousetrap for the full day in a house, you are guaranteed to catch the mouse if on that day it happens to have targeted that particular house.

You are contemplating the mousetrap placement strategy to follow, and land on the conclusion that if on subsequent days you place the mousetraps in houses 1-2, 2-3, ..., 7-8, you are certain to catch the mouse in no more than 7 days.

Can you do better? What is the shortest time in which you can be guaranteed of catching the mouse?

|improve this question
$\endgroup$
  • 5
    $\begingroup$ I think this might be the same puzzle but with different numbers: puzzling.stackexchange.com/q/455/4551 $\endgroup$ – xnor Jan 1 '15 at 16:54
  • $\begingroup$ @xnor - if the puzzle you link to is the same, I'm sure you can give us the solution to the above without too much thought? :) $\endgroup$ – Johannes Jan 1 '15 at 17:21
  • $\begingroup$ Does the mouse move from house 8 to house 1? $\endgroup$ – Masked Man Jan 2 '15 at 7:08
  • 2
    $\begingroup$ to clarify. "mousetrap is left for a full day in a house", and "mouse moves every night", so if i put a trap in house 2 -> i'll catch the mouse that was already in there + the mouse that moves into it in the night also ? $\endgroup$ – Angel Koh Jan 2 '15 at 8:31
  • 1
    $\begingroup$ "@xnor - if the puzzle you link to is the same, I'm sure you can give us the solution to the above without too much thought?" This is exactly why douplicate questions should not be posted. $\endgroup$ – klm123 Jan 2 '15 at 8:55
10
$\begingroup$

It can be over in 4 days:

5-7, 2-4, 2-4, 5-7

Here is how it works:

You can picture the progress of the mouse like a walk on a chessboard. The rows are the days, the columns are the houses. The mouse starts from the top row and walks diagonally down. Note that it can move on one color only.

To catch the mouse, you first assume it is on a white square. There are 4 possible houses. The first day you catch the mouse in houses 5 and 7. If it survives, the mouse is in house 1 or 3. Then, the next day, it must be in houses 2 or 4 and you are certain to catch it on the second day. It is visually easy to see how the traps (x) seal the green area in the left picture.

mouse chess

You need to repeat the process on the black cells. It is the same method reversed. What the mouse did on the first 2 days is then irrelevant. The right picture shows the complete solution in 4 days. Green cells are possible survival places for the mouse.

|improve this answer
$\endgroup$
  • $\begingroup$ I'll +1 this if you can explain why it works. $\endgroup$ – Jack Aidley Jan 1 '15 at 22:14
  • 3
    $\begingroup$ Also worth pointing out why it cannot be done in less than four days. Imagine on the first day there were eight mice, one in each house. Each night the two mice in house 1 and 2 swapped, same for 3 and 4, 5 and 6, 7 and 8. In three days there is no way you could catch more than six of the eight mice. This shows that after three days, there are at least two houses left where the mouse could still be alive. $\endgroup$ – kasperd Jan 2 '15 at 1:24
1
$\begingroup$

You can catch the mouse by placing the traps as follows:

1-3, 4-6, 7-2, 3-5, 6-8. This takes 5 days.

I have no idea whether this is the fastest.

The parity of the house that the mouse is at changes each day. Essentially, this strategy first eliminates the possibility that the mouse was at an odd numbered house the first day, then eliminates the possibility the mouse started at an even numbered house. This generalizes to the situation with $n$ houses, and takes at most $\left\lfloor\frac{2n}{3}\right\rfloor$ days to catch the mouse.

|improve this answer
$\endgroup$
1
$\begingroup$

3 days

Day 1: trap at 2 and 7 (if mouse already in there, it'll be caught)

Night 1: mouse from 1 and 8 have to move into the trap. (since the puzzle doesn't allow the mouse to stay put).

Day 2: move trap inwards to 3 and 6 (if mouse is already in there, it'll be caught).

Night 2: catches mouse if they move outwards from 4 and 5

Day 3: move trap inwards to 4 and 5 (mouse got no where else to go.)

|improve this answer
$\endgroup$
1
$\begingroup$

It will take maximum of 3 days to catch the mouse.

Day 1: traps put in houses 1 and 7:-

case 1: it is in house 1 or 7 and gets trapped.

case 2: mouse is in house 8:-

it will either move to house 7 or house 1(if it can) and will be trapped

case 3: mouse is in house 2 or 6:-

either it will move towards house 1 or 7 and get caught or it will move towards houses 3 or 5

case 4: it is in houses 3-5:-

it will be available in houses 2-6 at all costs(because it can move only 1 house at a time)

Day 2: traps put in houses 2 and 6:-

again either mouse will be trapped at night or its within houses 3-5

Day 3: traps put in houses 3 and 5:- mouse will be certainly trapped at night.

|improve this answer
$\endgroup$
0
$\begingroup$

[Edit: not an answer. No idea why I read seven houses, when it's clearly written as eight houses in the OP. Sorry!]

While there are quite a few possible answers, I favor the laziest, divide-and-conquer approach, where you move the traps as rarely as possible, if at all. It's just less work.

So, one at 4 divides the problem in two. One at 2, subdivides that half of the problem further. So, traps 2 & 4 for two days would eliminate any mice at 2 and 4, of course, but also at 1 and 3, since the only places the mouse could have gone from those, after the first day, was into our traps.

Since we then know the mouse is in the range 5-7, we know the lowesst place he can reach the next day is 4. So we can just move the trap from house 2 to house 6, leaving the other trap at house 4. Sit for a couple of days - if he moves into in 4 or 6, he dies that day: if he moves into 5 or 7, then he has nowhere to move the next day except into our traps.

So: (2,4), (2,4), (4,6), (4,6).

The row of 7 houses, at the end of each day:

1234567 <- House numbers
mTmTmmm <- Day 1           m = mouse
.T.Tmmm <- Day 2           T = trap
...TmTm <- Day 3           . = known empty house.
...T.T. <- Day 4
|improve this answer
$\endgroup$
  • $\begingroup$ From the OP, "You are chasing a mouse living in a row of eight houses", but your answer is for 7 houses. $\endgroup$ – atk Jan 2 '15 at 2:16
  • $\begingroup$ ...crikey. I coulda SWORN... well sheesh. Thanks for catching that :) $\endgroup$ – Dewi Morgan Jan 2 '15 at 2:29
  • $\begingroup$ @DewiMorgan Hang on a minute. Doesn't your solution still work even if it is eight houses. You Day 3 and 4 are correct, if you just change Day 1 and Day 2 to add an extra m at the end then it should be fine $\endgroup$ – Daveo Jan 2 '15 at 3:13
  • $\begingroup$ Hee - thanks for the vote of confidence, but unfortunately not, no: if there's an eighth house, then in days 3 and 4, the mouse could just move from house 7 to 8 and back again. Florian F's answer is correct, elegant, and well-explained :) $\endgroup$ – Dewi Morgan Jan 2 '15 at 7:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.