We write the integers from 1 to 100 on a board, and at each step, Little Nicolas erases two numbers, adds them, and writes the sum of the digits of the result.

1. At the end, the last number displayed is 24. Should Nicolas review his mental arithmetic?
2. Having redone his calculations without error, he gets a number between 15 and 25. What is his result?

When the desired final state is achievable, there is often nothing better to do than to explicitly exhibit the construction that works. When one wants to show, on the other hand, that a state is inaccessible, the best way to demonstrate this is to find a certain quantity that does not change during the allowed modifications: it is called an invariant. If at the final state, it must be different from its initial state, then the required construction does not exist. An invariant always provides a necessary condition but rarely a sufficient one.
Here, the invariant that comes into play when talking about the sum of digits is congruence modulo 9: indeed, we know that any number is congruent to the sum of its digits modulo 9. At each step, if Little Nicolas does not make a mistake in his calculation, he does not modify the congruence modulo 9 of the sum of all the numbers written on the board.

1. Or

$$
1+\cdots+100=\frac{100 \times 101}{2}=5050 \equiv 5+0+5+0 \equiv 1[9]
$$

In particular, $24 \not \equiv 5050[9]$, so there must have been an error somewhere.

2. The only number between 15 and 25 that is congruent to 1 modulo 9 is 19, so this is the result displayed on the board.

We will see several types of invariants and problems that make use of them, such as tilings, graphs, and game strategies. Indeed, in a game, the strategy often involves maintaining an invariant that characterizes a winning or losing position.

## Classical Invariants

Many invariants are obtained through modular arithmetic: a quantity that seems to vary can in fact remain constant modulo a well-chosen integer. An example is the classic game of Nim below.