A beautiful logic puzzle that I found on Gurmeet’s puzzle collection, which he has attributed originally to K Rustan M Leino at Microsoft Research.
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?
Please send your answers either directly on the blog site as comments, or to me at alokgoyal_2001@yahoo.com. If you like the puzzle, please share it with others. If you have interesting puzzles to share, please send them to me at my e-mail given above.
Happy hide and seek with the fox!
Alok Goyal's Puzzles Page 
We can solve this by sub dividing the problem into 2 sets.
On a given day, the fox can either be in the odd numbered holes or the even numbered holes.
Let Hd denote the set of holes the fox can be in on Day d.
Therefore, H1 = {1,3,5} or H1 = {2,4} (i.e. on Day 1 the fox can be in any of 5 Holes)
Case 1: H1 = {2, 4} (Case where fox was holed up in any of the even numbered holes on Day 1)
Start by checking Hole 2.
If fox is initially in Hole 2 we have caught it. Lucky Day!
Else if fox was in Hole 4 it has now moved to either Hole 3 or Hole 5
Therefore, H2 = {3,5}
On Day 2 inspect Hole 3
If the fox had moved to Hole 3 the previous night, we have caught it.
Else if the fox had moved to Hole 5, it has to move to Hole 4 tonight.
Therefore, H2 = {4}
On Day 2 inspect Hole 4. And, lo and behold we have caught the fox.
Case 2: H1 = {1,3,5} (Case where fox was holed up in any of the odd numbered holes on Day 1)
So we started off inspecting Hole 2.
If fox was in Hole 1 it would move to Hole 2 tonight.
If fox was in Hole 3 it would move to Hole 2 or Hole 4 tonight.
If fox was in Hole 5 it would move to Hole 4 tonight.
Therefore H2 = {2,4}
On Day 2 we inspected Hole 3.
If the fox had moved to Hole 2 the previous night, it now can move to either Hole 1 or Hole 3 tonight.
If the fox had moved to Hole 4 the previous night, it now can move to either Hole 3 or Hole 5 tonight.
Therefore H3 = {1, 3, 5}
On Day 3 we inspected Hole 4
If fox was in Hole 1 it would move to Hole 2 tonight.
If fox was in Hole 3 it would move to Hole 2 or Hole 4 tonight.
If fox was in Hole 5 it would move to Hole 4 tonight.
Therefore H4 ={2,4}
This means that on the pleasant morning of the fourth day, the fox is either holed up in Hole 2 or Hole 4 (And close to getting caught. YaY!! ). We have already solved how to catch the fox in such a case (Refer Case 1) and it turns out that we need to examine Hole 2, Hole 3 and Hole 4.
So, the final solution i.e. catching the fox eventually, is the union of solution for both the cases presented(i.e case where H1 = {1,3,5} and case where H1 = {2,4}). Thus, we need to examine the holes 2, 3, 4, 2, 3, 4 in order to catch the fox.
Tried to solve it, here is the solution I came up with. Guess, it would take a maximum of 8 days.
X = Holes where Fox can be present
* = Holes we are checking on a particular day
0 = Holes where Fox cannot be present
Day 1: X*XXX
Day 2: 0*XXX
Day 3: 0XX*X
Day 4: XX*X0
Day 5: X*X0X
Day 6: 0*0X0
Day 7: 00*0X
Day 8: 000*0
Cheers,
Trueindian
Thanks Tarun, I am just posting the answer. You can do it in 6 days. Please see the solution.
This is what I think the solution is—
Let us name the 5 holes 1,2,3,4,5 such that numbers are written in the correct order. Let us call the holes designated an even number ‘even holes’ (holes 2 and 4) and the holes designated an odd number ‘odd holes’ (holes 1,3,5). Keeping in mind the operation that is possible (the fox moving either left or right when possible), it can be noticed that the parity of the holes always changes with each operation, in other words, if the fox is in an even hole, the next time it moves it must be in an odd hole and vice versa. We can use this to find our answer. To go about finding the fox, let us first assume that the fox is hiding in an even hole. We first test this by checking an even hole first, lets say, hole number 2. If hole number 2 is empty, through our assumption, we then deduce that the fox must have been in hole number 4 at first and hence must be in hole number 3 or 5 now (using our assumption). We check hole number 3 next. If hole number 3 is empty, using our assumption, the fox was in hole number 5 at that time. This means the fox must go to hole number 4 the next day, as there is no other place for the fox to go from hole no. 5. We check hole number 4 the next day. If hole number 4 is empty, this disproves our assumption that the fox hid in an even hole on the first day, implying that it was in an odd hole on the first day. Knowing that it was hiding in an odd hole on the first day, the next time we check (that is the fourth morning), using the cycle odd – even -odd- even (using the fact that the parity of the hole changes after every operation), we realize that when we check now, the fox must be in an even hole (either hole 2 or 4). We go about finding the fox the same way as before. We check hole no. 2, if hole two is empty, we know that the fox is in hole no. 4, The next day it must have either gone to hole no. 3 or hole no.5. We check hole no.3, if this hole is also empty then, we know that the fox is in hole number 5 and the next day the fox must travel to hole no. 4. When we check hole no. 4 the next day the fox must be there. Therefore the strategy for finding the fox is selecting holes 2,3,4,2,3,4 in that order. Thanks for the nice puzzle!