Two Opaque Boxes: Place or Take for Maximum Expected Payoff
Company: Jane Street
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are playing a one-player game with two opaque boxes, both of which start empty. The game lasts exactly 100 turns, and on every turn you must choose one of the following two actions:
- **Place**: a third party puts \$1 into one of the two boxes, chosen uniformly at random. (This money is not yours yet — it just sits in the box.)
- **Take**: one of the two boxes is chosen uniformly at random; you receive all of the money currently inside that box, and the box is emptied.
The boxes are opaque: you can never see how much money is in either box, and you do not learn how much money you have collected until the game is over. In other words, you receive no feedback during the game, so your decisions cannot depend on any observed outcomes.
Assuming optimal play, what is the expected total payoff of this game? Describe the optimal strategy (which turns should be Place and which should be Take, and in what order) and compute the exact expected value it achieves.
Quick Answer: This question evaluates probabilistic reasoning, expected-value analysis, and sequential decision-making under uncertainty, testing competency in stochastic modeling, combinatorics, and optimization.
You play a solitaire game with **two opaque boxes**, both starting empty, over exactly `n` turns. On every turn you must choose one action:
- **Place**: a third party drops \$1 into one of the two boxes, chosen uniformly at random. (Not yours yet — it just sits there.)
- **Take**: one of the two boxes is chosen uniformly at random; you receive everything currently in it, and that box is emptied.
The boxes are opaque and you get **no feedback** until the game ends, so your decisions cannot depend on observed outcomes — your whole plan is a fixed sequence of `n` Place/Take moves fixed in advance.
Assuming optimal play, return the **maximum expected total payoff** as a floating-point number.
**Key idea to derive:** Follow a single placed dollar. It sits in one fixed box and is collected the first time a later Take happens to select that box. If `k` Takes occur after it, it is collected with probability `1 - (1/2)^k`, contributing that much in expectation (by linearity of expectation, this sums independently over all placed dollars). To maximize each dollar's `k`, schedule **all Places first, then all Takes**. With `q` Takes at the end, each of the `n - q` Places sees `k = q`, so the expected payoff is `(n - q) * (1 - 2^(-q))`. Scan `q` from `0` to `n` and return the best.
**Example (n = 100):** the maximum is at `q = 6`: `94 * (1 - 1/64) = 94 * 63/64 = 92.53125` — place for 94 turns, then take for the final 6.
Constraints
- 0 <= n <= 10000
- Each turn is exactly one of Place or Take.
- No feedback during play — the strategy is a fixed action sequence.
- Return a float; a tolerance of 1e-6 is applied when grading.
Examples
Input: (100,)
Expected Output: 92.53125
Explanation: Optimal q=6 Takes at the end: 94 * (1 - 1/64) = 94 * 63/64 = 92.53125 (place 94 turns, take the last 6).
Input: (0,)
Expected Output: 0.0
Explanation: Edge case: no turns, so nothing can be placed or collected.
Hints
- Because you never observe anything until the game ends, your entire strategy is a fixed sequence of Place/Take moves decided in advance — there is nothing to adapt to.
- Trace one placed dollar. It stays in its (random) box and is collected the first time a later Take selects that box. With k Takes after it, the collection probability is 1 - (1/2)^k. Sum this over all dollars by linearity of expectation.
- To give every dollar the largest possible k, do all Places first and all Takes last. With q Takes, the payoff is (n - q) * (1 - 2^(-q)); scan q from 0..n and return the maximum. For n=100 the optimum is q=6 (place 94, take 6) => 92.53125.