Recently, I encountered the following problem for which the given solution was straightforward but no proof was provided for a crucial claim made in the solution.
Alice and Bob plays a game where a list of numbers is given. Here are the rules of the game:
- Alice starts, and the players take turns.
- On a turn, a player can remove two consecutive similar numbers from the list.
- If a player cannot make a valid move, they lose, and the other player wins.
Determine who wins the game if both the players play optimally.
Solution: In the solution given across various websites, we start from the left end of the list and use a stack to keep track of the numbers. If you encounter a number that is similar to the one at the top of the stack, both get deleted. Otherwise, add the number to the stack. The outcome of the game depends on whether the total number of moves (i.e. the number of deletion steps) is even or odd.
Claim: "The total number of moves required for the game to end (i.e. the number of deletion steps) is independent of the order in which we make the deletions."
In order for the solution to work, the above claim should stand. In all of the websites, the above claim was made without giving any proof for it. Could somebody give a reason as to why this claim stands?
