6. Removing Matches

Your task is to find out and prove who wins the following game.

Input: A pile of $n$ matches is given and two players take turns. In each turn, a player removes exactly $2^k$ matches where $k$ is an integer and $k \geq 0$ . In other words, each player can remove a number of matches equal to some power of two.
Question: For which $n$ does the first player win and for which $n$ does the second player win? We assume that both players play perfect strategy, i.e., they do not make any mistakes.

Your solution must include a formal proof of the correctness of the solution. It is not sufficient to describe winning strategies, you need to also prove their correctness.

Instructions

Read the task and solve it by yourself. In case of plagiarism, your homework will not be considered solved.
Then, submit scanned and hand-written solution as a single PDF file using MS Teams.
The deadline for submission is April 3, 2025, 23:59. The deadline is strict.