The problem is asking for the numbers $N$ for which Shakur can force a win. Just like tic-tac-toe, but in that case, if both player plays perfectly, the game always ends up in a draw. But in this game, clearly draw isn't a case.
We define, $f:\mathbb{N}\cup\{0\}\to\{0,1\}$ such that
\[\forall N\geq1,f(N) =\left\{\begin{array}{100}1 & \mbox{if Shakur has a winning strategy for }N \\0 & \mbox{otherwise}\end{array}\right.\]
We also define$f(0)=0$ since if it's your turn and the number of coins is $0$, that means you lost and the game terminates.
$\text{Lemma :}$ Let $k(N)$ be the greatest integer for which $N\geq2^{k(N)}$. Then,
\[1-f(N)=\prod_{j=0}^{k(N)}f(N-2^j)\]
$\text{Proof :}$
Let's consider the product, \[P_N=\prod_{j=0}^{k(N)}f(N-2^j)\] Where $k(N)$ is the greatest integer for which $N-2^{k(N)}\geq0$.
Since $\forall j, 0\leq j\leq k, f(N-2^j)\in\{0,1\}$, we conclude that $P_N\in\{0,1\}$
- Case 1 : $P_N=1$
$P_N=1$ if and only if $\forall j, 0\leq j\leq k(N), f(N-2^j)=1$.
So, whatever power of $2$ Shakur chooses, he will always end up with a number that ensures win for Tiham. So, Shakur does not have a winning strategy for $N$.
$\therefore f(N)=0\Longrightarrow1-f(N)=1=P_N$.
So, our lemma is true for $P_N=1$.
- Case-2 : $P_N=0$
$P_N=0$ if and only if $\exists j, 0\leq j\leq k(N), f(N-2^j)=0$
In this case, Shakur would choose $2^j$ such that $f(N-2^j)=0$. Now, in Tiham's turn, he has got a number for which he does not have a winning strategy. That means he cannot force a win from here. So, if Shakur plays perfectly, he would win, since if he loses even after playing perfectly, that means Tiham has a winning strategy for $N-2^j$ which is obviously not the case. So, Shakur has a winning strategy for $N$.
$\therefore f(N)=1\Longrightarrow1-f(N)=0=P_N$.
So, our lemma is true for $P_N=0$
This completes the proof of our lemma. $\text{Q.E.D.}$
Now we will prove the following claim using the principle of mathematical induction.
$\text{Claim :}$ \[f(N) =\left\{\begin{array}{100}0 & \mbox{if }3|N \\1 & \mbox{otherwise}\end{array}\right.\]
- Base case : $N\in\{0,1,2\}$
We use our $\text{Lemma}$ and we get,
$f(0)=0$,
$f(1)=1-f(0)=1$,
$f(2)=1-f(1)f(0)=1$
- Induction Hypothesis : Let's assume out claim is true for $N\in\{0,1,2,\dots,3m,3m+1,3m+2\}$ where $m\in\mathbb{N}\cup\{0\}$
We will prove that our claim is also true for $N\in\{3m+3,3m+4,3m+5\}$
- Inductive Step :
- $N=3m+3$
Using our lemma,
$f(N)=1-P_{3m+3}=1-f(3m+2)f(3m+1)\cdots f\left(3m+3-2^{k(3m+3)}\right)$
Since $\forall j, 0\leq j\leq k(3m+3), 3\nmid3m+3-2^j$
By our induction hypothesis, we get, $f(3m+3-2^j)=1\Longrightarrow P_{3m+3}=1\Longrightarrow f(N)=0$.
- $N=3m+4$
In this case, we have, $f(N-1)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$
- $N=3m+5$
In this case, we have, $f(N-2)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$
So, by
Principle of mathematical induction, our claim is proved for all $N\in\mathbb{N}\cup\{0\}$. $\text{Q.E.D.}$
So, the number of $N$s between $1$ and $999$ for which Shakur has a winning strategy is,
\[\boxed{\sum_{k=1}^{999}f(k)=\sum_{3\nmid k, 1\leq k\leq999}1=666}\]