Solution to Puzzle #109: Fox in a Hole

From this week, I am moving to a one-week shifted model, where I will publish the solution for puzzles posted 2 week back instead of one week back, this will give everyone two weeks to look at the puzzle just in case they do not get a chance in the first week.

For #109, I got a lot of solutions and mostly all correct. It is a very nice puzzle. Folks who sent the correct answer included Pratik Poddar (first one to send a solution, and his solution is the one I am reproducing here – thanks Pratik!), Amit Mittal, Suman Saraf and Siddharth Mulherkar. Tarun Walia sent a correct answer but not an optimal one.

Here is the solution from Pratik, which also has a solution to the generalised version.

Lets prove that 2,3,4,2,3,4 is sufficient and will always give us a solution. (Please note that 4,3,2,4,3,2 will also work)

Initially, the fox could be in either {1,3,5} or {2,4}

If initially the fox was in {2,4} we can prove that the operation 2,3,4 always finds the fox.
(Proof: If 2 did not work, the fox was in 4. So, it would have moved to 3 or 5. If 3 did not work in the second chance, it was at 5. So, it will now move to 4 and will get caught in the third catch)

Now for the case when it begins a place in {1,3,5}. After 3 days, it would go to one in {2,4} and so now a 2,3,4 operation will find the fox.

Related problem: Lets say that the number of holes is not 5 – its n.

Generalising the answer for n holes:

sequence of inspection should be,
Part 1: 2,3,4…,(n-1);
followed by
Part 2: (n-1),(n-2),…2.

if fox started in an even numbered hole, then fox will be found in part 1.
otherwise
if fox started in odd numbered
hole , then fox will be found in part 2.

Proof: The end holes 1 and n are not checked because, before being caught in these end holes, fox will be found in hole 2 or hole n-1. in both parts we are traversing from one end to other and parity of our movement is different in part 1 and part 2. Hence fox will be caught in whichever part our parity matches with that of fox.

So, for the 5 hole case 2,3,4,4,3,2 is also a solution.

Hope you all enjoyed the puzzle!

This entry was posted in Solution and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s