Guaranteed hit on a submarine with unknown start and speed
Question
A submarine sits at an unknown integer position on a line at time 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 are countable, so list them as . At turn fire at , where the submarine would be if its parameters were the -th pair. The true pair appears at some finite index , 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 solutionLessons behind this question
- Gambler's Ruin and First Passage Times
- Simple Random Walks — Symmetric and Asymmetric
- Sample Spaces, Events, and the Probability Axioms
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