Jump to content
BrainDen.com - Brain Teasers
  • 0


bushindo
 Share

Question

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?

Link to comment
Share on other sites

7 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0
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.

Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...