15

This is a variant of the sleeping princess puzzle.

There are fifteen foxholes, connected by underground tunnels as shown below. A fox is sleeping in one of them.

  • Every day, a hunter checks one of the foxholes, finding the fox if it is there.

  • Every night, the fox moves through a tunnel to a different, adjacent foxhole.

How can the hunter catch the fox?

Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • Probably the same concept - but instead of odd-even, it's at the nth stage of the binary tree – Quintec Sep 07 '17 at 23:57
  • 1
    For some reason, just seeing 'hunter chasing fox' makes me think of IMOq3 – Wen1now Sep 08 '17 at 01:23
  • hunter comes in a day while fox moves in night. so hunter waits for whole day until tomorrow or he checks and go back? – Oray Sep 08 '17 at 05:23

1 Answers1

18

Number the nodes as follows:

enter image description here

A valid solution is to check:

4,2,5,2,1,3,6,3,7,4,2,5,2,1,3,6,3,7

To see that this works, first note that the fox can only go from a hole in an even-numbered level of the tree to a hole in an odd-numbered level of the tree and vice-versa. If the fox starts in an odd level, the sequence 4,2,5,2,1,3,6,3,7 guarantees the hunter will catch it. This works because the hunter alternately looks at a hole at an odd level and then immediately checks the only possible remaining entrance to it, making sure the fox can never return to that hole:

enter image description here

If the fox has not been caught after this sequence, then you know it is in an even level of the tree. For the next day, it must have moved into a hole in an odd level, so we can use the same sequence again to seal its fate.

ffao
  • 21,733
  • 4
  • 68
  • 109