1

An invisible rabbit sits on one of the posts of an infinite fence. A local farmer cannot stand this fact and wants to shoot the rabbit down*. Every time the farmer shoots her gun, the rabbit jumps to another post along the fence (not quickly enough to avoid the shot, though). The jump is always in the same direction and the same distance.

How can the farmer make sure she hits the rabbit with a finite number of shots?

* Not to kill it, of course, just to get it off the fence. It's a water gun.

Angkor
  • 1,347
  • 7
  • 17
  • And once I've knocked off the rabbit I can hear him hit the ground, yes? – Ben Frankel Apr 07 '15 at 11:59
  • @BenFrankel Yes. – Angkor Apr 07 '15 at 12:02
  • 3
    Looks very similar to the recent submarine question... – Rand al'Thor Apr 07 '15 at 12:03
  • @randal'thor I marked it as duplicate. Thanks for noticing. – Angkor Apr 07 '15 at 12:24
  • It should be noted that the duplicate question does not solve this in a finite number of shots. The only claim is that it can be done in a countable number of shots. The integers are countable and infinite, so these obviously do not equate. – Ian MacDonald Apr 07 '15 at 12:29
  • Additionally, the so-called duplicate question moves the submarine at a constant rate relative to time. This is in no way related to the number of shots fired. This question moves the rabbit each time the gun is fired. – Ian MacDonald Apr 07 '15 at 12:53
  • @IanMacDonald, Actually the duplicate question does indeed require only a finite number of shots, and the nuance that the submarine will still move even if we do not shoot does indeed change the question; however, the solution provided there does shoot every hour and is thus also relevant to this question. – Ben Frankel Apr 07 '15 at 13:29
  • @BenFrankel, the duplicate question most certainly does not require a finite number of shots. The wording specifically says "unlimited number" and "eventually sink". Nowhere does it stipulate that this must be done with a finite number of shots. – Ian MacDonald Apr 07 '15 at 13:42
  • @IanMacDonald, Oh. I meant that the answer solves the question in finite time and it shoots every hour, so it works for this question too. The questions are different, but only on a very shallow level. – Ben Frankel Apr 07 '15 at 13:45
  • @BenFrankel, you have also misinterpreted the accepted answer on that question. It notes that there are an infinite number of combinations of $A$ and $B$, but notes that the submarine will eventually be sunk. "Eventually" here does not imply finite, but is instead more indicative of the convergence of a limit. – Ian MacDonald Apr 07 '15 at 13:51
  • @IanMacDonald, Yes, he says eventually. His method works in finite time however. $A$ and $B$ are finite, thus $f(A,B)$ is finite, where $f$ is the function defined by the imaged spiral. He hits the submarine $(A,B)$ after $f(A,B)$ hours. EDIT: I'm talking about the accepted solution, ie, Allan's solution. – Ben Frankel Apr 07 '15 at 13:56
  • @BenFrankel, no, his algorithm loops through *all* combinations of $A$ and $B$ at any given time $t$. An individual function result for an individual $(A,B)$ pair may be finite, but the number of combinations that are iterated in his algorithm at every time $t$ is *not* finite. – Ian MacDonald Apr 07 '15 at 14:10
  • I don't think this is possible with a finite number of shots. The rabbit can start anywhere on the infinite fence. Am I missing something? – Luke Apr 07 '15 at 14:13
  • @IanMacDonald, I don't quite understand what you're saying. He only shoots once every hour, yes? Each time his shot checks if the submarine is $(X,Y)$. Either he hits and he wins, or he fails and he checks the "next" $(X,Y)$ on the next hour. Thus in finite time he reaches the constant $(A,B)$ of the submarine. – Ben Frankel Apr 07 '15 at 14:16
  • If that's what he's saying, it certainly won't catch the submarine. Consider a submarine travelling along the path $x=y$. If you miss on the first shot, the submarine gets progressively further and further away from your spiral. For example, his 31st shot is at $(4,4)$ when the submarine would be already at $(32,32)$ and getting further away. This does not converge if you only fire one shot, hence this cannot possibly be what he meant. – Ian MacDonald Apr 07 '15 at 14:26
  • @Ian It sounds like you misinterpreted the solution to the linked puzzle. The spaces in the spiral do not represent locations in space. They represent possible starting states of the sub, which the spiral eliminates one by one. For any starting state, the solution sinks the sub in finite time. However, without knowing the sub's position, there is no finite bound on how long the process might take; nor, trivially, is such a uniform bound possible for any solution. – Lopsy Apr 07 '15 at 16:39
  • @Lopsy, then you're in agreement that there is no finite termination to the process. – Ian MacDonald Apr 07 '15 at 17:42
  • @IanMacDonald There will always be a finite termination to the process. If you are so intent that it's possible there won't be, give an example of values for A and B for which the process won't terminate. – Taylor Brandstetter Apr 07 '15 at 20:42
  • @Taylor: His solution just isn't worded very well, I suppose, with the graph being unnecessary (and misleading at a glance). – Ian MacDonald Apr 07 '15 at 20:54
  • It actually is a finite problem. You can think of the solution as a single point on the A-B plane. You will always hit the solution (using the spiral) no matter what. – Allan Apr 08 '15 at 00:32
  • I'm not sure how the graph could've been misleading. The question is talking about a submarine on a number line; that is a one-dimensional number line. Perhaps you misinterpreted the question. – Allan Apr 08 '15 at 00:37
  • Does the rabbit have to move a fixed displacement each time? If not, it seems impossible to win in finite steps with certainty. It could be that each time you shoot, it was one space to the right of whereever you shot. – xnor Apr 12 '15 at 03:23
  • @xnor Yes, the jump is always in the same direction and the same distance. Still, the situation you describe is possible, and therefore shooting at post $N+C$, where $N$ is the shot number and $C$ is some constant, is not a good strategy. – Angkor Apr 13 '15 at 09:32

0 Answers0