Rabbit Season
March 1st, 2010
There are 10 cells in a line. A transparent rabbit is in one of them. You have a shotgun, and obviously you want to shoot the rabbit.
If you hit the cell with the rabbit, you kill him (and win). Otherwise, if you shoot an empty cell, the rabbit hears the shot, gets scared of the noise and jumps one cell to the right or one cell to the left. In case the rabbit is in the right-most cell, it can only jump to the left (and similarly, if the rabbit is in the left-most cell, it jumps to the right).
Can you kill the rabbit? If so, what is the minimum number of shots needed to guarantee a kill?
Extra Credit
Spoiler Warning – read after solving the riddle above!
Instead of considering the cells in a row, the riddle can be generalized to a graph.
If the graph has cycles, no solution exists (make sure you see why!).
What happens if the graph is a general tree?
March 2nd, 2010 at 12:16 pm
first try to shot the rabbit if it was in cell 1. one shot is enough/
noe try to shot it if it was in cell 2: after first shot it is in cell 1 or 3, then shot first to cell 1, then now if it steel alive, it has to be in cell 2 or 4, then shot cell 2, then 3, 4,5,6,7,8,9. this ensure killing if it was firet in crll 2.
noe we go on if the first situation was cell 3. after 10 shots as before, it must be in an odd cell (1 0r 3 …) again shot 1,2… and so on/
March 2nd, 2010 at 1:08 pm
s,
Good solution, but its is a little complicated and requires quite a lot of shots. A much more efficient (and simple) solution exists.
Also, try to think of the extra-credit part.
March 2nd, 2010 at 1:26 pm
well, let me try again/
first let me think that the rabbit was in cell 1 or 3 or 5 or 7 or 9/
then if we shot cell 1, the rabbit steel alive just if it is (after the shot) in cell 2, or 4, or 6 or 8 or 10.
now let shot cell 2, the rabbit steel alive just if it is (after the shot) in cell 3, or 5, or 7 or 9.
now let shot cell 3, the rabbit steel alive just if it is (after the shot) in cell 4, or 6, or 8 or 10.
this way, after 10 shots we know that the rabbit is killed/
that mens that if it steel alive, it has to be now in cell 2 or 4,6,8,10/
again shot cell 2, 3, till 9, and the job is done. (18 shots at all)
March 2nd, 2010 at 1:54 pm
s,
Note that the first shot (in cell 1) is wasted, and so is the shot in cell 10.
A slightly better solution is then: 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2, which consists of 16 shots (16 is indeed the minimum number of shots required).
March 2nd, 2010 at 6:23 pm
The rabbit *must* move? or it may remain stationary?
If it must move then also a sweep 2 2 3 3 … n-1 n-1 will surely kill it.
March 2nd, 2010 at 6:36 pm
Rani,
The rabbit must move – if it were allowed to remain stationary then there is no solution! (see why?)
Also, the sweep you are suggesting does not work. If the rabbit starts in cell 4, then moves to cell 3 (after your first shot to cell 2) and then moves to cell 2 (after your second shot to cell 2) and then oscillates between cells 1 and 2 during the rest of the sweep, you will not kill it.
March 5th, 2010 at 1:08 am
Seems to me that for a general tree, the rabbit can survive indefinitely.
Consider a a simple tree with one central vertex, which has four legs stretching from it, each leg being a string of three vertices (so 13 vertices altogether). Assuming that the rabbit knows your shooting strategy, it can compute its strategy as follows: If it is not in the central vertex, it will jump in the direction of the vertex – unless that location will be targeted next, in which case it will jump backward. If it is on the central vertex, it will jump into one of the “free” legs, which will be defined later.
Assuming we can always jump into a “free” leg from the center without dying, the only way that the rabbit will die is when it is in the outer vertex of a leg, and on the next turn the middle vertex of the leg will be shot; for this to happen, the inner vertex of the leg must have been shot on this turn (or the rabbit would have jumped to it instead of the outer vertex). This tells the rabbit that he must avoid being on a leg when the middle vertex is shot immediately after the inner. When the rabbit is in the center, call the next leg to have such a pattern in it a dead leg. Also say that the leg shot on the turn before the pattern appears is dead, and also the leg to be shot next turn. There are at most three dead legs, so there is at least one “free” leg to jump to which isn’t dead. The rabbit can jump to that leg as it won’t be shot next turn, and when the pattern appears next the rabbit will have 3 turns in which the leg he is on won’t be shot – enough time to return to the center of the graph, and jump to the next free leg, and so will live indefinitely.
March 5th, 2010 at 1:24 am
Dan,
Great solution! As usual!
A reasoning similar to yours above (or a few lines of python) show that in a “star”-tree with only 3 legs of length 3 and a center (so 10 nodes in total) the rabbit will survive forever.
BTW – if you remove one node, so one of the legs has length 2 (and the graph has only 9 nodes in total), the rabbit dies. So probably the 3-3 star is the smallest tree in which the rabbit survives.
The next logical generalization is: given any graph (tree or not), what is the minimum number of shots per turn needed to guarantee a kill? Some particularly interesting special cases are trees, and maybe a checkerboard (i.e. a 2d analog of the original question).
March 7th, 2010 at 11:34 am
Nice one!
July 14th, 2012 at 2:10 am
See a complete proof here:
http://arxiv.org/abs/1204.5490