Problem

Source: Brazil National Olympiad Junior 2022 #1

Tags: combinatorics, invariant



A single player game has the following rules: initially, there are 10 piles of stones with 1,2,...,10 stones, respectively. A movement consists on making one of the following operations: i) to choose 2 piles, both of them with at least 2 stones, combine them and then add 2 stones to the new pile; ii) to choose a pile with at least 4 stones, remove 2 stones from it, and then split it into two piles with amount of piles to be chosen by the player. The game continues until is not possible to make an operation. a) Give an example of a sequence of moves leading to the end of the game. b) Make a table with the total number of stones and the number of piles before and after the first 5 operations in your example above. c) Show that the number of piles with one stone in the end of the game is always the same, no matter how the movements are made.