1
$\begingroup$

A submarine is moving along the line at a constant speed $s$, starting from position $a$. Thus its position is $a + st$. $t$ does not necessarily start from zero, it starts from some value $k$ that you are also unaware of.

Now, at each increment of $t$ by $1$ you may choose any point on this integer line. If the submarine is at that point, you win. If it is not, you keep trying again until you're right.

Is there a way to make sure you find the submarine in finite time?


This problem is adapted from a problem where you know that $t$ starts at $0$, thus you try values of $(a, s)$ (which are countable) while incrementing $t$ from $0$ each time, and eventually you must find the correct $(a, s)$. However when you don't know what time it is, it seems trickier. Intuitively I would think it still works since the number of possibilities for where the submarine is at any given time is countable, but I'm having trouble coming up with a way that will exhibit this.

$\endgroup$
1
$\begingroup$

Note: The position of the sub at time $T$ (starting at $0$) is $a+s(T+k)$.

Method 1: Note that $a+s(T+k)=a+sT+sk=(a+sk)+sT$ so you can use your strategy for finding a sub with formula $A+ST$ by setting $S=s$ and $A=a+sk$.

Method 2: Since the set of all triples $(a,s,k)$ is countable, you can actually just blindly test each one using $a+s(T+k)$ in order.

$\endgroup$
  • $\begingroup$ So, if, for example we start choosing points at t=1 sec, what would be the strategy? I did not understand... $\endgroup$ – Samuel Sep 6 '17 at 17:32

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.