BrainDen.com - Brain Teasers
• 0

# Find the Rat

## Question

A rat is in one of 100 holes that are in a line.  Each night he moves to the left or right 0,1, or 2 holes randomly selected.  You pick one hole each day to look in until you find him.  What procedure do you use in order to minimize the expected number of days before you find him?

## Recommended Posts

• 0
Spoiler

Just keep looking in either of the two middle holes every day

##### Share on other sites

• 0
3 hours ago, Evilhubert said:
Hide contents

Just keep looking in either of the two middle holes every day

Looking in a middle hole every date has an expected time of over 1,000 days to find the rat.  There's a way to do it in less time.

Edited by Bob Bixler
##### Share on other sites

• 0
On 4/17/2023 at 4:23 AM, Bob Bixler said:

Looking in a middle hole every date has an expected time of over 1,000 days to find the rat.  There's a way to do it in less time.

I give up. What is the answer?

##### Share on other sites

• 0

As this is an open challenge question I want to give other people plenty of time to respond.

##### Share on other sites

• 0

Hey Bob, welcome to the den.  It's been a while since I've checked this site.

This puzzle, at first glance, seemed similar to "Groundhog in a Hole." -- http://brainden.com/forum/topic/11943--/

I have posted a couple variations, too.  -- http://brainden.com/forum/topic/12010--/ and http://brainden.com/forum/topic/18524-groundhog-in-a-hole-yet-again/

Anyway, I thought I'd ask for some clarification.  If the rat is in hole 10 on day 1, does that mean on day 2 it has an equal chance (20% each) of having gone to holes 8, 9, 10 (stayed there), 11, or 12?  If the rat is in hole 2 on day 1, on day 2 is there an equal chance (25% each) of being in holes 1, 2, 3, or 4?  And a third chance each for holes 1, 2, and 3 if starting right on the edge in hole 1?  And does the rat have an equal chance of being in any given hole on day 1 (1% each)?  Just thought I'd nail down the way the probabilities move.

Here's a quick guess before checking... anything really...

Spoiler

Alternate checking holes 3 and 98.

Holes 3 and 98 are both two away from the edges, and it is where I assume probability of this random walk should accumulate.  Alternating might help reduce the impact of reduced probabilities due to repeatedly checking the area.  I chose two away from the edge to still have 5 holes that could go to it each day.

##### Share on other sites

• 0

Yes to all your questions.  There are better ways than your initial guess.

##### Share on other sites

• 0

It seems my initial guess and idea about how the probabilities would end up were... umm,  bad.

Yay code...

Spoiler

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <fstream>

#include <math.h>
#include <cstring> //for memcpy

using namespace std;

const long double third = 1/3.0d;
const long double quarter = 1/4.0d;
const long double fifth = 1/5.0d;

long double probs[100];
long double probsnew[100];

long double probleft;
long double currenttaken;
long double expect;
int holechecked;
int lasthole;
int daynum;
ofstream *out;

void initprobs()
{
probleft = 1;
expect = 0;
daynum = 0;
lasthole = -1;
for(int i = 0; i < 100; i++) probs[i] = .01d;
}

void stepprobs()
{
probs[0] *= third;
probs[1] *= quarter;
probs[99] *= third;
probs[98] *= quarter;
for(int i = 2; i < 98; i++) probs[i] *= fifth;

probsnew[0] = probs[0] + probs[1] + probs[2];
probsnew[1] = probsnew[0] + probs[3];
probsnew[2] = probsnew[1] + probs[4];
probsnew[99] = probs[99] + probs[98] + probs[97];
probsnew[98] = probsnew[99] + probs[96];

long double currentprob = probsnew[2];
for(int i = 3; i <= 97; i++)
{
currentprob += probs[i+2] - probs[i-3];
probsnew[i] = currentprob;
}

memcpy(probs,probsnew,sizeof(long double)*100);
daynum++;
}

long double checkhole(int holenum)
{
lasthole = holechecked;
holechecked = holenum;
if ((holenum < 0) || (holenum >= 100)) {currenttaken = 0 ; return 0;}
currenttaken = probs[holenum];
probleft -= currenttaken;
probs[holenum] = 0;
expect += daynum * currenttaken;
return currenttaken;
}

long double sanitycheck()
{
long double total = probleft;
for(int i = 0; i < 100; i++) total-=probs[i];
}

void printstatus()
{
*out << holechecked << "," << (holechecked-lasthole) << "," << (1-probleft) << "," << probleft << "," << currenttaken << "," << (currenttaken/probleft) << "," << sanitycheck() << "," << expect << ",";
*out << (expect + ((daynum+1)*(probleft))) << ",";

if (currenttaken>0) *out << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << ",";
else *out << "inf" << ",";

*out << (expect + (1000000000000*probleft)) << ",";
for(int j = 0; j < 100; j++)
{
*out << "," << probs[j];
}
*out << endl;
if (daynum % 100 == 0) cout << daynum << "," << probleft << "," << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << endl;
}

{
*out << "holechecked" << "," << "holediff" << "," << "taken" << "," << "probleft" << "," << "currenttaken" << "," << "currenttaken/probleft" << "," << "probleft error" << "," << "expect" << ",";
*out << "expectmin" << ",";
*out << "expectapprox" << ",";
*out << "expectlarge" << ",";
for(int j = 0; j < 100; j++)
{
*out << "," << "hole " << j;
}
*out << endl;
}

int findmax(int mode) //0leftmost,1rightmost,2closest
{
int maxhole = 0;
for(int i = 1; i < 100; i++)
{
if (probs[maxhole] < probs[i]) maxhole = i;
else if (probs[maxhole] == probs[i])
{
switch (mode)
{
case 0://do nothing
break;
case 1:
maxhole = i;
break;
case 2:
if (abs(holechecked-maxhole) > abs(holechecked-i))
maxhole = i;
break;
}
}
}
return maxhole;
}

void doday(int hole) {checkhole(hole); printstatus(); stepprobs();}

int main(int argc, char *argv[])
{
ofstream outfile;
outfile.open("output.csv");
out = &outfile;

initprobs();

/* //1000 -- 81.9813
doday(94);
doday(97);
for(int j = 0; j <= 33; j++)
{
for(int i = 2; i <= 14; i+=3) doday(i);
for(int i = 18; i <= 30; i+=3) doday(i);
for(int i = 34; i <= 97; i+=3) doday(i);
}
*/

/* //1000 -- 82.0348
doday(92);
doday(2);
doday(97);
for(int i = 0; i <= 1000; i++)
{
doday(findmax(0));
}
*/

/* //9000 -- 862.492
for(int i = 0; i <= 9000; i++) doday(49);
*/

/* //9000 -- 782.726
for(int i = 0; i <= 4500; i++) {doday(2); doday(97);}
*/

outfile.close();
}

My best approach so far...

Spoiler

I calculated an expected value for the day to catch the rat for this as about 81.9813 days.
First, check hole 95, then 98.  Then, starting with hole 3, check every third hole (moving an extra hole twice... 19 instead of 18, then 35 instead of 34).  Go back to hole 3 and begin checking every 3rd hole again with the same modifications, and repeat.

My code is 0-based, so add 1 to those if you want the holes numbered 1-100.

doday(94);
doday(97);
for(int j = 0; j <= 33; j++)
{
for(int i = 2; i <= 14; i+=3) doday(i);
for(int i = 18; i <= 30; i+=3) doday(i);
for(int i = 34; i <= 97; i+=3) doday(i);
}

It seems we calculate the expected value for the day the rat is found differently.

Spoiler

I have that Evilhubert's approach would take 862.492 days.  (And my initial guess wasn't much better, at 782.726)

##### Share on other sites

• 0

Yes, you have the basic procedure which is to start at or near one end and move 3 holes each time until you reach the end and repeat at or near the start.  There are subtle modifications as you describe but they all give about the same result.  The interesting point is that there is an enormous difference between this approach and offhand initial guesses.

## Join the conversation

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

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

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