DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Puzzles && Algorithms
*****************************************************
#Post#: 99--------------------------------------------------
Strategy for identifying Fox
By: ravu Date: November 18, 2012, 8:55 am
---------------------------------------------------------
Consider five holes in a line. One of them is occupied by a
fox. Each night, the fox moves to a neighboring hole, either to
the left or to the right. Each morning, you get to inspect a
hole of your choice. What strategy would ensure that the fox is
eventually caught?
#Post#: 101--------------------------------------------------
Re: Strategy for identifying Fox
By: kranthipls Date: November 18, 2012, 10:23 pm
---------------------------------------------------------
Randomly pick one hole to inspect and the inspect every
alternate hole the next day (in only one direction). This will
lead us to the fox.
#Post#: 105--------------------------------------------------
Re: Strategy for identifying Fox
By: kpr29 Date: November 18, 2012, 11:13 pm
---------------------------------------------------------
@Kranthi: So the worst case of catching the fox is 5 for this
example.............. since we go by randomness............. Is
there efficient way to do this.........
kp
#Post#: 120--------------------------------------------------
Re: Strategy for identifying Fox
By: ravu Date: November 18, 2012, 11:54 pm
---------------------------------------------------------
How is it possible?
Consider for example
1 2 3 4 5. Initially fox is in the 5 th hole, now as per
Kranthi's method first randomly choose 3 in the first morning.
But, that night fox will be in 4 th hole, but then next day you
will be checking 5 th hole, then what?
#Post#: 139--------------------------------------------------
Re: Strategy for identifying Fox
By: adi Date: November 19, 2012, 3:19 am
---------------------------------------------------------
given holes 1 2 3 4 5
check hole 1 first day : if fox in 1 caught ;D
if in 2, next day either to 1 or 3 so simply check 2 : if it had
gone to 1 next day on checking 2 caught. That's day 3. if it
had gone to 3 and comes back to 2 again caught.
So on day three if fox not caught we know fox is in 4 5. (since
from 3 it would move to 2 or 4)
So on 4th day check 3rd hole if fox comes back it ;D otherwise
in 4 or 5 . If in 4 next day to 3 or 5 so check 3rd hole on 5th
day again. if 3 then ;D otherwise sure 5 so check 4 next day. 6
days ???
#Post#: 145--------------------------------------------------
Re: Strategy for identifying Fox
By: ravu Date: November 19, 2012, 3:42 am
---------------------------------------------------------
Hint - Identify what is the sequence if the fox was initially
in the even holes(like 2 or 4)
#Post#: 147--------------------------------------------------
Re: Strategy for identifying Fox
By: ravu Date: November 19, 2012, 9:47 pm
---------------------------------------------------------
The answer is as follows -
234234-
Initially fox can be in either {1,2,3,4,5}. Assume in the first
day fox can be in either {2,4}- then strategy to catch the fox
is 2,3,4. But if we are not able to catch then which means
initially fox was in {1,3,5}. So on 2nd day fox will be in
{2,4}, on third day {1,3,5,}, on fourh day again on {2,4}.
Hence, we have to repeat the same sequence - 2,3,4 again to
catch the fox.
#Post#: 159--------------------------------------------------
Re: Strategy for identifying Fox
By: kpr29 Date: November 19, 2012, 10:38 pm
---------------------------------------------------------
@Techie: Awesome...........
#Post#: 160--------------------------------------------------
Re: Strategy for identifying Fox
By: kranthipls Date: November 19, 2012, 10:43 pm
---------------------------------------------------------
@ravu Good question
#Post#: 162--------------------------------------------------
Re: Strategy for identifying Fox
By: ravu Date: November 19, 2012, 10:51 pm
---------------------------------------------------------
@kranthi - what is this?
Don't think you are. Know you are -Kranthi?
*****************************************************