## Yoak: Foxy!

There are five holes in a row in my yard.  A fox lives in them moving around as follows:  Each night, it abandons it current residence and moves to an immediately neighboring hole.  If I’m allowed to check one hole each morning, identify a sequence of holes that I can check in order to be sure to catch the fox.

1. ### Blaine said,

October 14, 2009 at 7:14 pm

I think I can catch the fox in a maximum of 6 turns.
[spoiler]
Check hole #2
Uncaught fox could be in 1, 3, 4, 5
After moving it could be in 2, 3, 4, 5

Check hole #3
Uncaught fox could be in 2, 4, 5
After moving it could be in 1, 3, 4, 5

Check hole #4
Uncaught fox could be in 1, 3, 5
After moving it could be in 2, 4

Check hole #4
Uncaught fox will be in 2
After moving it could be in 1, 3

Check hole #3
Uncaught fox will be in 1
After moving it will be in 2

Check hole #2

There are other patterns that would work like 234234 and reflections like 432432[/spoiler]

2. ### Andy said,

October 14, 2009 at 10:25 pm

Call the holes 1, 2, 3, 4, 5. Then every time the fox moves, the parity of the hole it is in changes. We can use this to limit the holes it can be in. Basically we want to force it to be in only one of the two even holes, from which situation it is easy to get a solution.
We start off picking hole 2. Assume we don’t get it. That means on the second day it could be in any of the holes except 1. Now we check hole 3. Assume we don’t get it. So on the second day it’s in hole 2, 4, or 5. That means that on the third day the only even hole it could be in is 4. So we check 4. Assume we don’t get it. Then it must have been in hole 2 or 4 on the second day, so on the fourth day it is again in hole 2 or 4.
Now we check hole 2. If we didn’t get it, it must be in hole 3 or 5. So we check 3, and now if we didn’t get it must be in hole 4, so we check 4 and we are certain to get it.
So the final sequence is 2, 3, 4, 2, 3, 4.