medium   Games

Stone Pick I

A release-checked medium problem for training Number Theory.

Question

Alice and Bob pick alternate turns in the following game: Initially, there are $n \geq 1$ stones in the middle. Either player can choose to take $1$ to $r$ stones from the pile. Assume that $n \equiv 1 \hspace{3pt} (\text{mod} \hspace{3pt} r+1)$. The player who draws the last stone loses. Alice gets to determine if she goes first or second. Assuming Alice selects her position in the game optimally and both Alice and Bob play optimally, in how many turns (total actions by the players) does Alice win the game, inclusive of the draw that makes Bob lose, when $n = 101$ and $r = 4$?

Practice focus

This Games problem is tagged Number Theory. State the random variables and conditioning information explicitly, then check the result against boundary cases before opening hints or a solution.

Reviewed questions in this area

easyFresh BagelReviewed

Games · WorldQuant, Valkyrie Trading