Power-of-two ball game where taking the last loses
Question
An urn starts with balls. Alice and Bob alternate turns; on each turn a player removes balls for some of their choosing (), provided that many remain. The player forced to take the final ball loses. Alice decides whether she moves first () or second (). Suppose Bob removes balls on his first turn; let be the largest number Alice can take in reply while still keeping a winning strategy. Compute .
Short answer
. Powers of two are never multiples of , so a player facing a count always hands back a count , and the opponent can restore (with ball left being a loss). Since , Alice goes second (). After Bob's , remain and she must leave a count ; the largest power of two that does this is , leaving . So .
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 solutionLessons behind this question
- Counting and Combinatorics
- Sample Spaces, Events, and the Probability Axioms
- Conditional Probability, Total Probability, and Bayes' Rule
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