Skip to content

Power-of-two ball game where taking the last loses

Question

An urn starts with 100100 balls. Alice and Bob alternate turns; on each turn a player removes 2k2^k balls for some k≥0k\ge0 of their choosing (1,2,4,8,…1,2,4,8,\dots), provided that many remain. The player forced to take the final ball loses. Alice decides whether she moves first (p=1p=1) or second (p=2p=2). Suppose Bob removes 3232 balls on his first turn; let bb be the largest number Alice can take in reply while still keeping a winning strategy. Compute 100p+b100p+b.

Short answer

264264. Powers of two are never multiples of 33, so a player facing a count ≡1(mod3)\equiv1\pmod 3 always hands back a count ≢1\not\equiv1, and the opponent can restore ≡1\equiv1 (with 11 ball left being a loss). Since 100≡1100\equiv1, Alice goes second (p=2p=2). After Bob's 3232, 6868 remain and she must leave a count ≡1(mod3)\equiv1\pmod3; the largest power of two that does this is 6464, leaving 44. So 200+64=264200+64=264.

Adapted from QuantQuestions.io; 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