Find the pairs of integers $(k, \ell)$ such that $5 k+3 \ell=32$.

## - Exercise Solutions -
Since 3 and 5 are coprime, the equation has an infinite number of solutions. Obviously, one could perfidiously remark that $(k, \ell)=(4,4)$ is a solution.

However, in general, we will start by looking for integers $\hat{k}$ and $\hat{\ell}$ satisfying Bézout's relation $5 \hat{k} + 3 \hat{\ell} = 1$. Using the extended Euclidean algorithm, we find $\hat{k} = -1$ and $\hat{\ell} = 2$, so that $(k, \ell) = (-32, 64)$ is also a solution.

Subsequently, and since 3 and 5 are already coprime, the solutions to the equation are in fact pairs of the form $(k, \ell) = (3x - 32, 64 - 5x)$, where $x$ is any integer.

## 3 Combinatorics

## 1 Game Theory

Combinatorial game theory is the study of mathematical games and the existence or non-existence of a winning strategy for one of the players. Many tools facilitate the search for such a strategy, but before delving into these methods in detail, it is necessary to start with a rigorous definition of a mathematical game?

What is a game? First, a set of states, or game positions, with rules allowing players to move from one position to another, and certain positions designated as winning for one or the other player, or as a draw.

## Definition 3.1.1.

Let $(V, E)$ be a directed acyclic graph where each path is of finite length. A mathematical game on the graph $(V, E)$ is a quintuple $G = (V, E, x_0, (A_1, A_2), (G_1, G_2))$, where $V$ corresponds to the vertices, $E$ to the directed edges connecting them, $x_0$ to the starting position, $A_1$ and $A_2$ partition the non-terminal vertices into positions playable by players 1 and 2, and $G_1$ and $G_2$ the terminal vertices into winning positions.

We study winning strategies in games, i.e., a choice of moves for one or the other of the two players that guarantees reaching one of their winning positions regardless of the choices of the other player.

## Definition 3.1.2.

A strategy for player $n \in \{1, 2\}$ is a function $S: A_n \mapsto V$ associating with each position playable by $n$ a reachable position from it.

## Definition 3.1.3.

A play of a game is a sequence of positions $J = (x_0, x_1, \ldots, x_p)$ such that for all $k < p$, there is an edge connecting $x_k$ and $x_{k+1}$, and $x_k$ is a terminal vertex of the graph. It is said to be winning for player $n$ if $x_k \in G_n$.

## Definition 3.1.4.

A strategy $S$ is said to be winning for player $n \in \{1, 2\}$ if every play $J$ such that $\forall x_k \in A_n, x_{k+1} = S(x_k)$ is winning for $n$.

We can view the existence of a winning strategy through a sequence of quantifiers $\forall$ and $\exists$: player 1 wins if, for every move or series of moves played by player 2, there exists a move or series of moves playable by player 1 such that for every... Or, in other words, that no matter what 2 plays, 1 can always play in such a way as to reach a winning position for him.

With this perspective, the following theorem is easily interpretable: the negation of $\forall x_1 \exists x_2 \exists x_3 \forall x_4, x_4 \in G_1$, for example, is $\exists x_1 \forall x_2 \forall x_3 \exists x_4, x_4 \in G_2$, in the case where terminal positions are reached after 4 moves (in reality, terminal positions are generally not reached after a predetermined number of moves, and this reasoning does not, of course, serve as a proof of the theorem).

Theorem 3.1.5 (Zermelo's Theorem).

Let $G$ be a two-player mathematical game. Then one and only one of the following two propositions is true:

- Player 1 has a winning strategy.
- Player 2 has a winning strategy.

Proof. Let $S_i$ be the set of vertices from which player $i$ has a winning strategy, and $T$ the set of vertices from which no player has a winning strategy. Suppose that $x$ is a vertex belonging to $T$.

Without loss of generality, assume that $x \in G_1$. If there exists an edge $(x, y)$ such that $y \in S_1$, then $x \in S_1$; if, for every edge $(x, y)$, the vertex $y$ belongs to $S_2$, then $x \in S_2$; therefore, there exists an edge $(x, y)$ such that $y \in T$.

But then, by setting $y = f(x)$, and if each player decides, from a position $x \in S$, to go to position $f(x)$, we thus obtain an infinite play, which is not possible. Therefore, $T$ is in fact empty.

Thus, to show that player 1 has a winning strategy, it suffices to show that player 2 does not have one! And, to show that player 2 does not have one, it suffices to show that if he did, then player 1 would also have one. This is the core of our first method, the strategy-stealing argument.