We have a set of k positive integers $a_i$ and $x$ coins. A and B take turns picking up the coins so that the last picker is the winner. Each turn, one person can only pick up a positive number of coins that in the given set. Knowing that, in the given set always contains number 1. A is the first person to go.
For examples:
Suppose that: With $x=9,k=2$ and $a_1=1,a_2=4$. The result is $A$, because A and B will take turn: $A:4;B:1;A=4$.
With $x=10,k=2$ and $a_1=1,a_2=4$. The result is $B$, because in any case, B always is the winner.
This is my try: I try build recursion to determine A or B win. I think that the importance in this problem is the number 1 in this set of $k$ positive integers.
- If $n$ is even, I will be find the maximize even number in this set and the rest is using the number 1.
- If $n$ is odd, I will be find the maximize odd number in this set and the rest is using the number 1.
But I can't think it clearly to come finally solution!!!
I would use two recursive functions: $V_p(r)$ is the value of the game to player A assuming that at the beginning of player $p$'s turn, there are $r$ coins left, and that both players play optimally. If $V_p(r)=1$ then player A will win and if 0 then player A will lose (regardless of the value of $p$).
Let $V_A(0) = 0$ and $V_B(0) = 1$. Then $$\begin{align*} V_A(r) & = \max_{a\in \{a_1,\ldots,a_k\}} \{V_B(r-a)\} \\ V_B(r) & = \min_{a\in \{a_1,\ldots,a_k\}} \{V_A(r-a)\} \end{align*}$$ The logic is: Player A wants to choose the value of $a$ (the number of coins to take) that maximizes the value of the game, accounting for the fact that on the next turn, there will be $r-a$ coins left and it will be player B's turn. If $r-a=0$, then player A wins since $V_B(0)=1$.
On the other hand, Player B wants to choose the value of $a$ that minimizes the value of the game (since the value is defined from player A's point of view), accounting for the fact that on the next turn, there will be $r-a$ coins left and it will be player A's turn. If $r-a=0$, then player B wins since $V_A(0)=0$.
Edit: To implement this approach, don't use recursion. Recursion would require you to calculate the value function over and over again for the same $p$ and $r$.
Instead, just loop through $r=1,\ldots,x$ and calculate $V_A(r)$ and $V_B(r)$ at each iteration. When you calculate $V_p(r)$, you use values of $V_p(s)$ for smaller $s$, which you have already calculated.