16
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Can A and B be either positive or negative? $\endgroup$ – Joe Z. Apr 7 '15 at 0:17
  • $\begingroup$ @JoeZ. Yes they can, and a negative value of B means the sub is moving left $\endgroup$ – Mike Earnest Apr 7 '15 at 0:19
  • $\begingroup$ @MikeEarnest, this question also exists as duplicate on Math.SE. You can also sink the sub if its speed and starting position are not integers, if the torpedo has a (fixed) target range. $\endgroup$ – Aravind Apr 7 '15 at 4:00
  • $\begingroup$ @Aravind I don't think it's possible if it's speed and starting position are not integers. Also, could you add a link to the duplicate on Math SE? $\endgroup$ – Allan Apr 8 '15 at 2:04
  • 1
    $\begingroup$ @BigAgnes Yes you are correct. After coming back to this problem after some time, I've come up with an actual algorithm that can enumerate positive and negative rational numbers; however it takes a while for large numbers when taken to their absolute value. I'll add it into my answer below. $\endgroup$ – Allan May 11 '17 at 21:59
13
$\begingroup$

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.
enter image description here
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).

$\endgroup$
  • $\begingroup$ The visual really drives the point home, well done! $\endgroup$ – Mike Earnest Apr 7 '15 at 4:37
  • $\begingroup$ Thanks! I also just figured out that the functions used for A and B in my solution must be wrong since they will always yield a positive integer (thus their combinations only cover the upper-left corner of the grid). I'm sure that somewhere out there, someone else has already figured out a function for it. I guess manually drawing out the graph and crossing out the values as they get used would work as well. I was hoping for a function that would be computationally simple :/ $\endgroup$ – Allan Apr 7 '15 at 5:26
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Dam you came up with the idea before I did :) $\endgroup$ – Allan Apr 7 '15 at 2:28
2
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ I'm a little confused with what's going on with T(x). Could you also add in some brackets into T(x) and it's inverse function (just to clear up what's getting multiplied)? $\endgroup$ – Allan Apr 8 '15 at 0:09
  • $\begingroup$ Sure, T is a little confusing. It makes more sense when you think about the recursive version of the formula. The explicit version is just a solution to that recursion (Which is far less intuitive). $\endgroup$ – knrumsey - Reinstate Monica Apr 8 '15 at 6:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.