A mouse, Two mousetraps, Eight houses

Question

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?

Answer 1

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.



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.

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

[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