Nim-Style Counting Game: Optimal Strategy and Losing Positions

Two players take turns adding an integer from $\{1, 2, 3\}$ to a running total that starts at 0. The player who first brings the total to exactly $N$ wins. Both players play optimally. **(a)** Prove that the losing positions -- the totals from which the player whose turn it is to move will lose against optimal play -- are exactly the multiples of 4. **(b)** Using this characterization, give an $O(1)$ algorithm that, given $N$, determines whether the first or second player has a winning strategy. If the first player wins, the algorithm should also output an optimal first move. **(c)** Explain how this backward-induction reasoning generalizes to other impartial combinatorial games (Sprague-Grundy theory), and why anticipating losing positions is relevant in adversarial trading or market-making contexts.