Sink the Submarine

Question

There is submarine somewhere on the number line. Initially (say, at midnight), it is at position $A$, and is moving $B$ units per hour to the right, where $A$ and $B$ are both integers; both $A$ and $B$ are unknown to you. You have an unlimited number of torpedoes. Starting at midnight, and at the top of every hour, you can fire a torpedo somewhere on the number line, sinking the sub if it is there. What strategy can you use to guarantee you eventually sink the sub?

Answer 1

We are given the following information
P(0) = A
V(t) = B
P(t) = A + Bt

Since we know our current time, we can cycle through all the possibilities of P(t) by cycling through all the combinations of A and B at the current time and we will eventually land on the correct combination of A and B.
NOTE: There are actually an infinite amount of combinations because the set of integers are unbounded. But since we know that A and B are finite numbers, this algorithm will eventually find the answer.

Here is a picture which shows a method for computing all the possible combinations. I'm sure there's probably an actual function out there that is able to compute the unique pair of values given an integer.

NOTE: The image depicted here is not the exact same as the function used in the solution below (it's simply been rotated). To view the actual geometry of the function used, visit the link.

Note that we have to increment t by 1 each time because we are firing the torpedo with respect to the current time (1 hour intervals).

I'll try to come up with a better explanation and maybe an animation if I have the time.

EDIT: (Sketchy) Algorithm for enumerating 2 rational numbers:
Since enumerating 2 rational numbers would essentially require enumerating 4 integers (i.e. integers a,b,c,d correspond to rational numbers a/b and c/d), this is what this algorithm essentially does.

First add 0 (special case that only needs to be considered once)

Then find all permutations where 1 is the biggest

1 1 1 1

Then find all permutations where 2 is the biggest

2 1 1 1
...
2 2 2 2

and so on...

Now for each line we need to enumerate all possible permutations of +/- (2^4 permutations).

Answer 2

There are countably many possible submarine paths, since each is given by an integer start point and speed. Enumerate all of them. On hour $h$, sink submarine $h$ on the list by bombing its location at that time. Any possible submarine will eventually be be sunk.

I could give an explicit strategy, but I find that brute-force constructions like this better explain why a solution must exist than clever explicit ones.

The same construction extends to submarines that move with as integer quadratics, or integer polynomials, or move with rational speeds, or move on lattice points on the plane, etc.

Answer 3

It's one ugly formula, but at least it's explicit! You can fire your $n^{th}$ torpedo at location $$P(n) = (-1)^n\left[A(n) + B(n)\cdot n\right]$$ where $$A(n) = \left\lfloor\frac{ \left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil\left(\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil+1\right) - 2(n-1) }{4} \right\rfloor$$

$$B(n) = \left\lfloor\frac{2(n-1) + 2\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil -\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil\left(\left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil+1\right)}{4} \right\rfloor$$

For instance, this table gives $P(n)$ for the first ten shots (and a few more).

Torpedo (n)     Location P(n)     Corresponding (A,B) 
1               0                 (0,0)
2               1                 (1,0)
3               3                 (0,1)
4               -1                (-1,0)
5               6                 (1,1)
6               -6                (0,-1)
7               2                 (2,0)
8               7                 (-1,1)
9               -8                (1,-1)
10              20                (0,2)
...             ...               ...
35              -104              (1,-3)
100             -397              (3,-4)
1000            5018              (18,5)
12345           -604934           (-29,-49)  

Derivation

Where to fire

Clearly, if we know $A$ and $B$, then at time $n$ we fire our torpedo at position $$P(n) = A + Bn$$

Mapping $\mathbb N$ to $\mathbb Z$

This function provides a bijective map from $\mathbb N$ to $\mathbb Z$.

$$H(k) = (-1)^k\lfloor k/2 \rfloor$$

For instance, we have $$H(1) = 0 \quad\quad H(2) = 1 \quad\quad H(3) = -1 \quad\quad H(4) = 2 \quad\quad H(5) = -2 \quad\quad etc$$

Enumerating $A$ and $B$

Consider a table, where the $i^{th}$ row and $j^{th}$ column holds the pair $(H(i), H(j))$. Every pair $(A, B)$ lies somewhere on this table, so we need only find the $i$ and $j$ which correspond to it. We will map $\mathbb N$ to $(A,B)$ pairs by moving along the diagonals. For instance, the first $5$ $(A, B)$ pairs are

$$(0,0) \quad\quad (1,0) \quad\quad (0,1) \quad\quad (-1, 0) \quad\quad (1,1)$$

Formally, this involves mapping $n$ to a pair $(A, B) = (H(I(n)), \ H(J(n)))$.

Finding $I(n)$ and $J(n)$

Let $T(k)$ be a function which returns the $n$ corresponding to the first row and $k^{th}$ column of our table. This function can be written recursively as

$$T(k) = T(k-1) + k \quad\quad \text{with }\ T(0) = 0$$

This recursion relation has the solution

$$T(k) = \frac{k}{2}\left(k+1\right)$$

whose inverse is

$$T^{-1}(k) = \frac{\sqrt{8k + 1} -1}{2}$$

Since the $k^{th}$ diagonal contains $k$ pairs, the $k^{th}$ diagonal of the table contains the $u^{th}$ through $v^{th}$ pairs where $u = T(k) - k + 1$ and $v = T(k)$. Moreover $\lceil T^{-1}(n)\rceil$ gives the length of the diagonal which contains the $n^{th}$ pair. Therefore in terms of $n$ $$v = T\left(\lceil T^{-1}(n)\rceil\right)$$ $$u = v - \lceil T^{-1}(n)\rceil + 1$$

Now just by counting rows (or columns) away from $u$ (or $v$) we obtain $I(n)$ and $J(n)$.

$$I(n) = v - n + 1$$ $$J(n) = u - n$$

Putting all the pieces together gives the equation for $P(n)$.