7

Submarine puzzle:

A submarine is located at an integer somewhere along the number line. It is moving at some integral velocity (an integral number of units per second). Every second you may drop a bomb which will destroy the submarine if the submarine is at that location.

Can you be guaranteed of destroying the submarine? If so, what strategy would you use?

(from http://math-fail.com/2011/01/submarine-puzzle.html)

And the answer is to enumerate all $(a,b)$ pairs, where $a, b$ are integers and the location of the submarine at time $t$ equals to $at+b$.

My question is, if now $a, b$ can be any real numbers, and the bomb can now destroy the submarine in a region of length 1,
i.e. if at time $t$ the bomb is dropped at $x_t$ and $x_t - 0.5 \le at+b \le x_t+0.5$,
the submarine will be destroyed.

Then can we be guaranteed to destroy the submarine?

Some thinking:

When $b$ is given, the mission can be done by enumerating $a$ in all rational number (since rational number is dense).

When $a$ is restricted to an integer, the mission can be done by the same method as above.

For general case, I think it is not possible to destroy the submarine, but I cannot prove it.

nnkken
  • 91
  • Are these assumptions correct: The position of the submarine at time $t=0$ is some $a\in\mathbb{Z}$, and the velocity of the submarine is is some $b\in\mathbb{Z}$ and never changes. Hence the position is $a+bt$. – Jeff Snider Jan 18 '14 at 20:16
  • @Jeff: Yes, that is the case for the first variant. Now the OP wants to know whether the puzzle can still be solved if $a$ and $b$ are allowed to take non-integer values. – TonyK Jan 18 '14 at 20:46

2 Answers2

3

Yes, the submarine can be destroyed. For simplicity assume the first bomb is $n=0$, and with the $n$-th bomb you wipe out a stripe in the $a,b$ plane of horizontal width 1 and slope $-1/n$. Subdivide the plane into unit squares, and enumerate the squares so that the plane is covered by countably many of them. If, starting at arbitrary bomb $n$, we can cover a unit square in finitely many bombs, we are able to cover the whole plane in countably many bombs and are guaranteed to destroy he submarine.

Pick the position of bomb $n$ so that the stripe covers the bottom edge of the square, which means it covers the bottom $1/n$ of the left edge. Pick the next bomb so it covers the bottom $1/(n+1)$ of the right edge. That stripe has a shallower slope than the previous: they overlap. The next bomb covers the next $1/(n+2)$ of the right edge, the following the next $1/(n+3)$ of the right edge, etc. It will require finitely many bombs to completely cover the unit square.

Since this is true for any unit square, starting with any $n$, we can completely cover the $a,b$ plane, hence destroy the submarine no matter where it started or its speed.

Apologies for brevity, I will expand my explanation from someplace other than my phone.

Jeff Snider
  • 2,817
  • 1
    I was thinking about how to fill the plane by these straight line regions, or how to prove that it is not possible... And your method definitely works. – nnkken Jan 19 '14 at 04:52
  • 1
    That is nicely done. – Mark Bennet Jan 19 '14 at 12:43
  • @Jeff Snider: Can you please attach a picture or graph so that we better understand the technique? For example, if b>=0 and a>0, starting to shoot at t=1, what would be the first pairs? How do we guarantee to cover all the pairs and finally destroy it? – Jason Sep 08 '17 at 14:07
1

Let's examine what's happening in the plane whose points are $(a,b)$

At time $t$ we eliminate points from consideration if we have $x_t-0.5-at \leq b \leq x_t+0.5-at$

For a given $a$ I choose my axes so that this is a horizontal line of length $1$. In the $(a,b)$-plane as $a$ varies you get a diagonal stripe of horizontal width $1$ and slope $-t$. The question becomes whether given one stripe for each integer $t$ one can cover the whole plane. The stripes have different slopes.

Now most of the stripes are nearly horizontal themselves. So it looks to me as though you can partition the $(a,b)$ plane e.g. into squares of side $0.5$ (you could probably be more efficient) - there are a countable number of these, and you order them to take out one with each stripe - which you do by choosing the appropriate value for $x_t$ for the stripe in question.

In this way you cover the whole $(a,b)$-plane - and therefore destroy the submarine wherever it started and however fast it is going.

NOTE - this doesn't work - see comment below. Maybe it can be modified, but the comment also identifies a difficulty which would require some care.

Mark Bennet
  • 100,194
  • Ah, you beat me by a couple of minutes. Well done. +1 – Daniel Robert-Nicoud Jan 18 '14 at 21:00
  • @DanielRobert-Nicoud - actually this does't work - I misled myself in visualising - the horizontal width of the stripes is constant, but as the stripes themselves approach the horizontal, they become thinner. So if I divide the plane into pieces of the same size and shape I'll eventually find they won't fit in. And I run into the fact that summing $\frac 1 n$ allows me to get as high as I want, but summing $\frac 1 {n^2}$ gives me only a finite area. – Mark Bennet Jan 18 '14 at 22:15
  • Well, if you show that you can cover only finitely many area, then it's a proof that you cannot be sure of catching the submarine, because every strategy will leave some hole in $\mathbb{R}^2$, which corresponds for a speed/initial position which would allow the submarine to escape. – Daniel Robert-Nicoud Jan 19 '14 at 10:49
  • @DanielRobert-Nicoud - each stripe has infinite area, of course, but the problem is to partition the plane into pieces which can be covered by stripes when the width of the stripe is $\frac 1{\sqrt {1+t^2}}$ which goes like $\frac 1t$ - so that if the pieces are all the same shape the area of the pieces will go as $\frac 1{t^2}$, and therefore the area 'under control' would be finite. It is still open whether the shape of the pieces could change so that the pieces would get longer as they got narrower - the difficulty then is to arrange it so that the pieces definitely cover the plane. – Mark Bennet Jan 19 '14 at 12:42