5
$\begingroup$

I was wondering if the problem of fox and holes

(There are 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?)

you can find detailled information here (https://gurmeet.net/puzzles/fox-in-a-hole/, https://www.youtube.com/watch?v=0Prp9n7XfP8)

can be solved for an arbitrary number bigger than 5?

I've solved the case n= {1,2,3,4,5}, but for case 6 it was complicated... do you have any idea ? Maybe it is possible for n odd and not if n even. If it isn't, I'm also searching for an argument of why it isn't :)

thank you!

$\endgroup$
2
5
$\begingroup$

There is an easy strategy for any $n$.

Consider what happens if you inspect the holes $(2,\ 3,\ 4,\ ...,\ n-1)$ on successive days. Prove that if the fox starts at an even-numbered hole, then it will not be able to get past your sweep, and that you will therefore catch it.

If you did not catch it, then it must have started on an odd-numbered hole. Now number the holes starting from the other end. Prove that the fox now (i.e. after that first sweep) must be in an even-numbered hole using that new numbering.

This means that you can do a second sweep in the opposite direction and must catch it.

Therefore the sequence $(2,\ 3,\ 4,\ ...,\ n-1)$ followed by $(n-1,\ n-2,\ ...,\ 4,\ 3,\ 2)$ will catch the fox.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.