Who Will Win the Game

74 Views Asked by At

The question is based on this article.

A player can choose any number (regardless of whether or not it was chosen during a previous turn) in the inclusive range between $L$ and $R$.

The game ends when the running sum of chosen numbers (i.e., sum of all numbers chosen by both players) is greater than or equal to $K$, and the last player to take their turn wins.

For given $L,R,K$, which player will win?

Min Value = K- R*[(K/R)]
Min Value>=L first one will win 
1

There are 1 best solutions below

2
On BEST ANSWER

This is essentially a subtraction game. Rather than counting up, let's start at $K$ and count down. The first person to make the sum drop to $0$ (or below) wins.

If $K > L+R$, then take out as many multiples of $L+R$ as possible to produce a value $K'$ in the range $(1,L+R)$.

  • If $K' \in (1,R)$, then the next player wins.
  • If $K' \in (R+1, L+R)$, then the next player loses.

If a player is in a winning position, then in general they respond to the other player's move by choosing a value that makes both moves add up to $L+R$. To put it another way, the players would like to make a move that leaves a sum $K'$ (as described above) within the range $(R+1,L+R)$.


Example: Suppose $(L,R) = (4,7)$, and $K=25$. We calculate $K'=25-2(11)=3 \in (1,4)$, so the first player to move wins. The winning moves are $4,5$, and $6$.