(Infinite Solitaire)(^) You all know the rules of solitaire: there are marbles on a board, and you eliminate marbles by jumping over them with another marble, etc. Now consider the plane and place marbles on all integer points of the negative half-plane. The goal of the game is to place a marble as high as possible in a finite number of moves. The drawing shows how to place a marble at height 1. What is the maximum height that can be reached?

![](https://cdn.mathpix.com/cropped/2024_05_10_59677aa68548da326d08g-019.jpg?height=369&width=1459&top_left_y=1873&top_left_x=214)

- Solutions to the exercises -
It is easy to raise a ball to height 1, 2, and 3, and with a bit of patience, one can raise a ball to height 4, but that is the limit. Let $\varphi$ be the golden ratio, which satisfies $\varphi^{2}=\varphi+1$:

$$
\varphi=\frac{1+\sqrt{5}}{2}
$$

Then, we need to sum over all points with coordinates $(x, y)$ on which there are balls of $\varphi^{y-|x|}$. I leave it to the reader to verify that this quantity remains constant or decreases when the balls are moved, and that in the initial position, it is equal to $\varphi^{5}$. This proves that it is impossible to raise a ball to height 5 or more.

## 2 Course/TD on Basic Strategies

## - Recurrence -

The principle of recurrence is fundamentally linked to the notion of integers: every time one needs to prove that a result is true for all integers from a certain rank, whether in arithmetic, geometry, algebra... one can be led to reason by recurrence.

The proof by recurrence is based on the fact that every integer $n$ has a successor $n+1$, and that if one "climbs step by step" the set $\mathbb{N}$ of natural numbers, starting from 0, going from one integer to the next, and repeating indefinitely, one thus fully traverses $\mathbb{N}$.

We will therefore prove that a property is true for the integer $n=0$ (initialization), and then that if it is true for any integer $n \geqslant 0$, it is still true for the next integer $n+1$ (induction): we deduce from this that the property is true for all natural numbers $n$. This is the reasoning by recurrence.

It should be noted that both parts of the proof are important, even if the first is often quite obvious. One must not forget to initialize the recurrence, that is, to prove that the property is true for $n=0$. One can start the recurrence at a value other than 0, for example, at $1, 2, \cdots$ or $K$; it will then be necessary to prove (initialization) that the property is true for $n=K$, and then (induction) that for $n \geqslant K$, if it is true for $n$, it is still true for $n+1$.

It should also be noted that induction has some variants. For example, it sometimes happens that one has to prove that if the property is true for all integers $k \leqslant n$, then it is true for $n+1$.