Problem #33 HARD
The Sinking Probability
Google Netflix Probability Statistics
Problem Statement
A naval commander hides a submarine in one of five ocean sectors labeled A, B, C, D, and E. Each day, a search aircraft checks one sector. If the submarine is in the searched sector, it is found with a probability of 0.7 (it may hide within the sector). If not found on a given day, the submarine silently moves to one of its two adjacent sectors overnight with equal probability. The sectors are arranged in a straight line: A-B-C-D-E. The aircraft searches sector C on day 1 and does not find the submarine. Which sector should it search on day 2 to maximize the probability of detection?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
Search sector B on day 2 (or equivalently D — both have equal probability ≈ 38.5%). The failed day-1 search in C depresses C's posterior and movement spreads that mass into adjacent sectors, making B and D the optimal targets.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
Use Bayesian updating. Let P(sub in sector X) = 1/5 initially. After a failed search of C with detection probability 0.7, update using Bayes' rule. Then apply the movement model to get day-2 priors.
Step 1: Day 1 prior: P(A)=P(B)=P(C)=P(D)=P(E)=0.2.
Step 2: Aircraft searches C. P(not found | sub in C) = 0.3. P(not found | sub not in C) = 1.
Step 3: Apply Bayes: P(sub in C | not found) = 0.2 x 0.3 / (0.2 x 0.3 + 0.8 x 1) = 0.06/0.86 ≈ 0.070.
Step 4: Updated posteriors: P(A)=P(B)=P(D)=P(E) = 0.2/0.86 ≈ 0.233 each. P(C) ≈ 0.070.
Step 5: Overnight movement: A moves to B only. B moves to A or C equally. C moves to B or D. D moves to C or E. E moves to D only.
Step 6: Day 2 priors: P(B) = P(A)x1 + P(B)x0.5 + P(C)x0.5 = 0.233 + 0.117 + 0.035 = 0.385. P(D) = P(C)x0.5 + P(D)x0.5 + P(E)x1 = 0.035 + 0.117 + 0.233 = 0.385. B and D are symmetric — search B.
Key Insight:
The failed search in C simultaneously reduces C's posterior and redistributes probability to neighbors. Movement then spreads probability outward from C, making B and D the highest-probability zones on day 2. The Bayesian update is what separates a good searcher from a naive one.