Boxes and Rat

[Guest]

Mr.X has five boxes arranged in a line (1-2-3-4-5). An intelligent rat comes out of nowhere and finds a place for itself in one of the boxes. Every night when Mr. X is sleeping, this rat moves to a new neighboring box to its left or to its right. Mr. X knew this behavior of the rat. Since this rat was a trouble for him, he was desperate to find it. Also due to paucity of time, he decided to search in only one of the boxes every day. He implements a strategy to make sure that he eventually finds this rat. This strategy helped him to find the rat in minimum number of trials in all cases possible. What is the minimum number of trials needed to come to the solution for all possible cases?

[Guest]

I keep coming up with 5 with almost no strategy. Start on one end and go across.

[Guest]

I keep coming up with 5 with almost no strategy. Start on one end and go across.

This strategy will not work! Remember that the rat can move 1 box left or right.

rat only moves while you sleep

rat starts in box 4 --> you select 1.

rat moves to box 5 ---> you select 2.

rat moves to box 4 ---> you select 3

rat moves to box 3 ----> you select 4

rat moves to box 2 -----> you select 5

5 sequential guesses and 5 misses.

How intelligent can the rat be if it sets a pattern of predictability of only 1 box shift?

[Guest]

7 trials

Strategy: search order for boxes :- 2 2 3 4 4 3 2

[Guest]

7 trials

Strategy: search order for boxes :- 2 2 3 4 4 3 2

Hi

Can u please elaborate on this strategy?

[Guest]

Hi sseth

Suppose rat is under 1

so rat will be caugth in second try.

If rat under 3 initially,

if it moves left after 1 try then it will be caught in second try.

It can also move towards right (under 4)

this situation is similar to another one(if rat was under 5 then it will move to 4)

So after two trys rat at 3 and 5 could be at 5 or 3.

If at three caught after 3rd try.

if at 5 then lift 4 twice so rats initially at 3 or 5 will be caught in 5th try.(only one possible move for end boxes)

Now if the rat is under 4 initially,

possible moves for rat

3 2 3 2 3 so caught in 6 th move

3 2 3 2 1 2 so caught in 7th move.

5 4 3 so caught in 3rd try

5 4 5 4 caught in 5th try

So rat is guaranteed to be caugth in 7 trys.

Chelsea 3- 5 Arsenal

[Guest]

Hi sseth

Suppose rat is under 1

so rat will be caugth in second try.

If rat under 3 initially,

if it moves left after 1 try then it will be caught in second try.

It can also move towards right (under 4)

this situation is similar to another one(if rat was under 5 then it will move to 4)

So after two trys rat at 3 and 5 could be at 5 or 3.

If at three caught after 3rd try.

if at 5 then lift 4 twice so rats initially at 3 or 5 will be caught in 5th try.(only one possible move for end boxes)

Now if the rat is under 4 initially,

possible moves for rat

3 2 3 2 3 so caught in 6 th move

3 2 3 2 1 2 so caught in 7th move.

5 4 3 so caught in 3rd try

5 4 5 4 caught in 5th try

So rat is guaranteed to be caugth in 7 trys.

Chelsea 3- 5 Arsenal

Thanks alot!!!!

[Guest]

1, look where there is rat droppings the first morning, and the rat will be in there.

[Guest]

Look which one is moving most. Duh!

[wolfgang]

put rat poison in the boxes..2,3,4,and 5....check only number 1...lol

[mewminator]

4 times should do it

Day 1: search box 2 (worst case senario:not found)

Day 2: search box 2 (worst case senario:not found)

therefore I can safely assume that it is now in box 3, 4 or 5

Day 3: search box 4 (worst case senario:not found)

Day 4: search box 4 (worst case senario:not found)

therefore I can safely assume it was in box 3 then moved to box 2

then it is currently inside box 2

[mewminator]

whoops made a mistake here's 6 times

days 1 and 2: box 3

days 3 and 4: box 2

days 5 and 6: box 4

If at day 6 he doesn't find the rat then it is in box 2

[Guest]

whoops made a mistake here's 6 times

days 1 and 2: box 3

days 3 and 4: box 2

days 5 and 6: box 4

If at day 6 he doesn't find the rat then it is in box 2

This does not work

day 1, rat in 1 -->you look in 3

day 2, rat moves to 2 ----> you look in 3

day 3 rat moves to 3 --->you look in 2

day 4 rat moves to 4 ---> you look in 2

day 5 rat moves to 3 --->you look in 4

day 6 rat moves to 2---> you look in 4

At this point you have properly deduced that the rat was in 2 but you will not look again until the next day after the rat moves again, which may be either 1 or 3.

[Guest]

7 trials

Strategy: search order for boxes :- 2 2 3 4 4 3 2

Hi sseth

Suppose rat is under 1

so rat will be caugth in second try.

If rat under 3 initially,

if it moves left after 1 try then it will be caught in second try.

It can also move towards right (under 4)

this situation is similar to another one(if rat was under 5 then it will move to 4)

So after two trys rat at 3 and 5 could be at 5 or 3.

If at three caught after 3rd try.

if at 5 then lift 4 twice so rats initially at 3 or 5 will be caught in 5th try.(only one possible move for end boxes)

Now if the rat is under 4 initially,

possible moves for rat

3 2 3 2 3 so caught in 6 th move

3 2 3 2 1 2 so caught in 7th move.

5 4 3 so caught in 3rd try

5 4 5 4 caught in 5th try

So rat is guaranteed to be caugth in 7 trys.

Chelsea 3- 5 Arsenal

Though I agree that 14.swapnil.14 has giving a solution for every possible move of the dumbest rat

The rat can be found in 2 nights. Remember original premise. stated "...An intelligent rat ...". Now if the rat is truly intelligent, then it will know that moving into box 1 or 5 will put him/her at a disadvantage, therefore, the mouse will only move into boxes 2, 3, or 4. So strategy is select box 3. If the rat is not there the first night, the rat will move to it to avoid boxes 1 and 5 and you will find the rat on teh second night.

Edited November 13, 2011 by thoughtfulfellow

[mewminator]

This does not work

If I know where the rat is I could spare a few moments of my day to be rid of it rather than waste another day of searching

Edited November 13, 2011 by mewminator

[mewminator]

I think I met the requirements without objection but then again it's a case of logic is the man so tired/ busy/ whatever that he could not search in a box he already knows contains the rat and would instead waste another day of searching because if so I'd have to add 2 days to this scenario

Edited November 13, 2011 by mewminator

[Guest]

7 trials

Strategy: search order for boxes :- 2 2 3 4 4 3 2

I think I met the requirements without objection but then again it's a case of logic is the man so tired/ busy/ whatever that he could not search in a box he already knows contains the rat and would instead waste another day of searching because if so I'd have to add 2 days to this scenario

In the above solution, he would also know the position of the rat on the 6th try and only require 1 additional day to get the mouse. If we are allowed to alter the problem, then search box 2 & 4 first day and if you didn't get the rat first day, then rat will be in 2 or 4 second so search these two again and got him in two days and only 4 searches maximum.

[mewminator]

In the above solution, he would also know the position of the rat on the 6th try and only require 1 additional day to get the mouse. If we are allowed to alter the problem, then search box 2 & 4 first day and if you didn't get the rat first day, then rat will be in 2 or 4 second so search these two again and got him in two days and only 4 searches maximum.

I meant if I knew the rat's position I might as well go deal with it otherwise it's stick to the routine

[Guest]

2.3.4.2.3.4

[Guest]

I believe amiab is right...

Checking the boxes 2 3 4 2 3 4 : -

If it starts with 1, it will take longest to be caught in the 1 2 3 4 5 4 scenario.

Starting with 2, its caught on first day.

Starting with 3, the longest situation is 3 2 3 4 5 4, 3 4 3 4 5 4 and 3 4 5 4 5 4

Starting with 4, it's caught by either 4 3 or 4 5 4

Starting with 5, it's caught by either 5 4 3 4 5 4 or 5 4 5 4 5 4

[curr3nt]

Taking the explaination further...

The first pick should be 2 or 4. The movement patterns for 1,3 and 5 match on the 4th day and every day after so choices then have the greatest effect.

Spend the first 3 days eliminating starting boxes 2 and 4 with either 2, 3, 4 or 4, 3, 2.

On the four day the rat has to be in an even box so pick 2 or 4. If not found then the next day the rat has to be in 1 or 3 if 4 was picked or 3 or 5 if 2 was picked. Choosing 3 either find the rat or predicts where the rat will be the next day since the rat only has one move option in either case.

Working options being 234234, 234432, 432234, 432432.

Trying to eliminate 1, 3 or 5 earlier than the 4th day is inefficient and it just so happens to take 3 days to eliminate 2 and 4.

[EventHorizon]

(by me )

(fyi, the answer to 4 ended up pretty interesting)

[mewminator]

I wonder... if the 6 boxes were forming a circle (i.e 1 could link to 5).... how many days would it take to find the rat

[Guest]

I wonder... if the 6 boxes were forming a circle (i.e 1 could link to 5).... how many days would it take to find the rat

you cant find the rat by yourself in that case

[EventHorizon]

I wonder... if the 6 boxes were forming a circle (i.e 1 could link to 5).... how many days would it take to find the rat

Amiab is right. On a side note, that is close to question 2 from my modifications I linked to earlier (though I used an analog clock as my example... so 12 holes).

[Guest]

check the same box everyday for 5 days