Skip to content

Guaranteed hit on a submarine with unknown start and speed

Question

A submarine sits at an unknown integer position on a line at time 00 and each turn moves by the same unknown integer amount (possibly negative or zero). Once per turn you may fire at one integer point. Describe a strategy that is certain to hit the submarine after finitely many turns.

Short answer

Enumerate all (start, step) pairs. The pairs (a,b)∈Z2(a,b)\in\mathbb Z^2 are countable, so list them as (a0,b0),(a1,b1),…(a_0,b_0),(a_1,b_1),\dots. At turn tt fire at at+btta_t+b_t t, where the submarine would be if its parameters were the tt-th pair. The true pair appears at some finite index TT, and that shot hits.

Adapted from Joshi, Denson & Downes, Quant Job Interview Questions and Answers, Q5.17, p.159; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free