[bushindo]

This is a slight modification of the Mouse and cheese problems posed earlier by psychic_mind. I'd like to see a generalization of his problem to the case of any arbitrary number of rooms.

Assume that there are N rooms lined up in a hall way, each has a room number ranging from 1 to N. The first room, room 1, has the cheese. If the mouse goes into room 1 it searches for 3 minutes before finding the cheese. If it goes into room number 2, it searches for 4 minutes and then leaves. In general, if the mouse goes into room n, it searches for (n+2) minutes.

The mouse first start by randomly choosing a room and search. Assume that any time the mouse leaves a room, it randomly select another room from all 20 except the one it just searched. Or in physic_mind's words, "THE MOUSE NEVER RE-ENTERS THE ROOM IT JUST LEFT".

What is the average amount of time it takes to find the cheese, given a number of room N?

[Guest]

((N-1)/2)*((N+2+4)/2)+3 minutes

[Guest]

((n-1)/2) + 3

[bushindo]

Just some clarification. The mouse can not immediately re-enter the room it just searched. It can, however, enter a room that was entered more than 1 turn ago. For example, if the mouse is in room 5, to start a new search, it will randomly select a room between 1 and 20, room 5 not included. Suppose it chooses room 10, it is possible for the mouse to enter room 5 again after it leaves room 10.

By the way, the case of n=3 is already solved. See here

http://brainden.com/forum/index.php?showto...mouse&st=10

For those checking their formulas, the average time required for n=3 is 9 minutes.

[Guest]

Took a little while but I'm quite sure that this is right. I have tested it for n = 1, 2 and 3.

Time = 3 + (N+6)(N-1)(N-1)/2N

[bushindo]

Took a little while but I'm quite sure that this is right. I have tested it for n = 1, 2 and 3.

Time = 3 + (N+6)(N-1)(N-1)/2N

That's right. Care to elaborate more on the calculation?

[Guest]

That's right. Care to elaborate more on the calculation?

It was a little complicated but I'll type up a sketch of my solution when i get the chance.

[Guest]

I'm not that good at explaining things but I'll try anyway .

Let average time = T

Average time for first room: 3/N + 4/N + 5/N + ... + (N+2)/N

But we must also take into consideration the average time, Q, spent after the mouse visits each room.

So lets say: T = 3/N + (4 + Q4)/N + (5 + Q5)/N ... + ((N+2) + Q[N+2])/N

(Note: Q4, for example, is not Q*4 it simply represents the time average time taken to find the cheese if it enters the room for 4 minutes)

I need to find an exp​ression for Q4, Q5 etc in terms of T.

Since no room can be revisited immediately, there will only be N-1 options for the mouse to pick. Something like...

3/(N-1) + (4 + Q4)/(N-1) + (5 + Q5)/(N-1) ... which is equal to N * T/(N-1)

In general, however, if the mouse chooses a room where it spends X minutes then you have to subtract this time, (X + Qx)/(N-1), form the calculation. So the average time taken (Qx) after visiting a room of x minutes is...

3/(N-1) + (4 + Q4)/(N-1) + (5 + Q5)/(N-1)+... - (X + Qx)/(N-1) = NT/(N-1) – (X +Qx)/(N-1)

This exp​ression is therefore equal to Qx.

Qx = NT/(N-1) – (X +Qx)/(N-1)

Qx = (NT - X)/N

Since T = 3/N + (4 + Q4)/N + (5 + Q5)/N ...

substitute the values of Qx...

T = 3/N + (4 + (NT – 4)/(N-1))/N + (5 + (NT – 5)/(N-1))/N + ... + ((N+2) + (NT – (N+2)/(N-1))/N

Then, finding the sum of this series, rearranging to find T, and then factorizing gives

T = 3 + (N+6)(N-1)(N-1)/2N