1 and 3)
No. At all times the rabbit has at least two choices for the next night. The fox can check at most one of them.
Consider the game as being played on a graph. Each node corresponds to a hole the rabbit can hide in; connect the two nodes if the rabbit can move from one to the other.
First, if there are any loops of length more than two, the rabbit wins.
If there is a subgraph of form A-B-C-D-E-F-G and D-H-I-J, the rabbit wins. ( How can the princess escape the prince? )
If there are two separate holes the rabbit is allowed to stay in overnight (loops of length 1 in the graph), and those two nodes are directly or indirectly connected, the rabbit wins. (Rabbit has two choices anywhere along the path connecting those nodes.)
If the graph is a simple path, except the one endpoint has a self loop, the fox wins. (Start at the node next to furthest from the point with the self loop. Move one step each night until at the node with the self loop. Check that a second time. Move one step away from it each night until at the starting spot.)
If the graph is a tree graph, with a simple path, with possible edges of length up to 2 from any point on the path, I think the hunter wins. If a self-loop is added to one endpoint of the path, the fox can still win.
I think this strategy works for the last case:
If all nodes are leaf nodes, there are 1 or 2 nodes, and the fox wins by repeatedly picking one node.
Call the nodes on the path P1, P2, ... P_n. P1 and P_n should not be leaf nodes (if so, just drop them and resume the proof with a shorter path).
Define Q1a, Q1b, ... as any non-leaf nodes not on the path that are adjacent to P1. Define Q2a, Q2b, ... similarly. Since every node is at most two steps from the path, every node is a P node, a Q node, or a leaf node.
If there are Q1 nodes, the fox starts with Q1a, P1, Q1b, P1, ... P1. If there are no Q1 nodes, the fox starts with P1.
The fox then moves P2, Q2a, P2, Q2b, ... P2.
Then, P3, Q3a, P3, Q3b, ..., P3.
and so on, up to Pn, except that if there are Qn nodes, the fox doesn't need to make a final Pn stop.
Finally, do those steps in reverse.
To handle the self-loop, create a new graph with two copies of the original graph, and replace the two self-loops with an edge connecting those two nodes; use the above strategy on the constructed graph. Any time the rabbit would use the self-loop, consider it as moving along the new edge. Any time the fox would choose a node on the duplicate graph, choose its original counterpart. (Because the fox actually makes two moves on the new graph for every move it makes on the actual graph, the "do these steps in reverse" part will be unnecessary.)
Because the rabbit can't start on the mirror graph, and the fox technically makes two moves at a time, it is possible that a graph with a single self-loop where the fox can win gets transformed to a graph where the rabbit wins; so graphs like 1-2-3-4-5-6-7, with a self-loop at 4, are still indeterminate.
Proof of strategy:
Definition: Two nodes are of the same parity if the distance between them is even. Two nodes are of opposite parity if the distance between them is odd.
Definition: The value of a node is z iff Pz is the first P node reachable from that node. (Nodes with value z are Pz, the Qz's, and any leaf nodes connected to Pz or a Qz.)
Definition: "First part" of fox's strategy is everything before "repeat moves in reverse". "Second part" is "repeat moves in reverse". Note that the value of the fox does not decrease during the first part, and does not increase during the second.
Note: As long as the fox moves to an adjacent hole each night, the fox and rabbit will remain at the same parity, or remain at opposite parity. If the fox checks the same hole on two adjacent night, the fox and rabbit switch from same parity to opposite parity or vice versa.
Claim: If the fox and rabbit start at the same parity, and the rabbit is not caught, then the value of the rabbit node will never be less than the value of the fox node during the first part.
Proof by contradiction: Consider the first time this happens. This is not the first move (since fox begins with value 1). The value of an animal changes by at most one each night, and can only change when moving from P node to P node.
How did the values change since the previous night?
- value of rabbit 1 higher than fox, Fox +1, rabbit -1: This is not possible since it would require both animals to be at P nodes, with the rabbit at one higher than the fox, which would have them at different parities.
- fox and rabbit at same value k, Fox +0, rabbit -1: This is not possible. The rabbit would have to be at Pk. The fox could not be at a leaf node (it never visits them) or a Qk node (which is at a different parity), so it would have to be at Pk, where it is caught.
- fox and rabbit at same value k, Fox +1, rabbit +0: This is not possible. The fox must have been on Pk. The rabbit was not on a Qk or a leaf node connected to Pk (those had different parities from the fox), so the rabbit was on a leaf node connected to Qk_m, for some m. During the time the fox has value k, the rabbit can not move to Pk (during the moves when the rabbit can move there, the fox will also be there), so the rabbit must be at Qk_m, or a leaf node connected to it. At some point in the strategy, the fox will move to Qk_m and will capture the rabbit.
Other changes in value will not change a position from rabbit >= fox to rabbit < fox.
Claim: If the fox's first move and the rabbit's starting node are the same parity, the fox will catch the rabbit during part 1.
Proof: At the end of the strategy, the rabbit's value is >= fox by above claim. Since there are no nodes with value > n, they must have equal values.
If there are no Qn nodes, then the fox ends at Pn, and the only node with value n of same parity as fox is Pn => rabbit is caught.
If there are Qn nodes, then the fox ends at a Q node. The only nodes with value n and of the same parity as the fox are other Qn nodes, so the rabbit is at some Qn node; call it Qn_k. During the time the fox had value n, the rabbit could only be at Qn_k, or leaf nodes adjacent to Qn_k. When the fox visited Qn_k, the rabbit had to be at Qn_k and would be caught.
Claim: if the fox and rabbit start with opposite parities, then the rabbit will be caught during the second part.
Proof is similar to above. At the first move of the second part, the fox checks a node two nights in a row. Since it was at opposite parity before, it will now be at the same parity, and will remain at the same parity as the rabbit during the second part. The value of the fox will remain >= value of rabbit during the second part (proof is similar to reverse claim from first part); at the end fox will win (again, proof is similar to reverse claim from first part).
This covers most graphs.
