Yakob and Baptiste are playing on a $20 \times 20$ grid where the cells are square and have a side length of 1. The distance between two cells is the distance between their centers. They take turns playing as follows: Yakob places a red stone on a cell, ensuring that the distance between any two cells with red stones is never $\sqrt{5}$, then Baptiste places a blue stone on the grid without any restrictions. The game stops when one of them can no longer place a stone. Find the largest $K$ such that Yakob can always place at least $K$ stones, regardless of Baptiste's responses.

## - Solutions -

Translate the above text into English, preserving the original text's line breaks and format, and output the translation result directly.
Let's show that $K=100$. Yakob can always place 100 stones: it suffices to color the grid in a checkerboard pattern and always play on a white square. Indeed, two white squares are never at a distance of $\sqrt{5}$ from each other. Let's show that Baptiste can prevent Yakob from placing more than 100 stones: we tile the grid with copies of the rectangle

$A C B D$

$B D A C$

$C A D B$

$D B C A$

If Yakob plays on a square, Baptiste plays in the same rectangle, on the square of the same color that is not at a distance of $\sqrt{5}$ from the first. Thus, Yakob is deprived of the two other squares of the same color in the same rectangle. In the end, Yakob cannot cover more than one quarter of the rectangle, which contains 400 squares.

## 3 Groups

- Course -


## Definition 3.3.1.

Let $G$ be a non-empty set with a binary operation: for every pair $a, b \in G$, there is an element $a b \in G$. Then we say that $G$ is a group if the following axioms are satisfied.

1. (Associativity) For all $a, b, c \in G(a b) c=a(b c)$.
2. (Identity element) There exists $e \in G$ such that for all $a \in G e a=a$ and $a e=a$.
3. (Invertibility) For all $a \in G$, there exists a (unique) $a^{-1} \in G$ such that $a a^{-1}=e$ and $a^{-1} a=e$.

## Definition 3.3.2.

We say that $G$ is an abelian (or commutative) group if it also satisfies the following property

1. For all $a, b \in G, a b=b a$.

## Notation.

In the case of abelian groups, we often use the sign + for the binary operation, writing $a+b$ instead of $a b$. In this case, we also denote 0 as the identity element and $-a$ as the inverse of $a$.

## Example 3.3.3.

All the following examples are groups:

1. The set of integers with addition (abelian).
2. The set of non-zero real numbers with multiplication (abelian).
3. The set of translations in the plane forms a group (is it abelian?).
4. The set of permutations (shuffles) of a finite set.
5. The set of transformations of the plane consisting of rotations and translations.

## Notation.

If $A$ and $B$ are two subsets of $G$, we denote

$$
A B=\{a b \mid a \in A, b \in B\} \text { and } A+B=\{a+b \mid a \in A, b \in B\}
$$

## Definition 3.3.4.

We say that a subset $H$ of $G$ is a subgroup of $G$ if it is a group with the binary operation of $G$.

## Definition 3.3.5.

If $H$ is a subgroup of $G$ and $a \in G$, $a H$ (resp. $Ha$) is called the left (resp. right) coset generated by $H$.

## Definition 3.3.6.

A subgroup $H$ of $G$ is said to be normal if for all $a \in G$ we have $a H=H a$.

## Remark 3.3.7.

If $G$ is abelian, all subgroups are normal.

## Theorem 3.3.8.

If $H$ is a normal subgroup of $G$, then the cosets generated by $H$ form a group with the binary operation

$$
(a H)(b H)=(a b H)
$$

We call this group the quotient group and denote it by $G / H$.

Proof. We need to verify that the definition we have given does not depend on the representative of the class. Let $a^{\prime} \in a H$ and $b^{\prime} \in b H$, we show that $a^{\prime} b^{\prime} \in a b H$. Let $h_{1} \in H$ and $h_{2} \in H$ such that $a^{\prime}=a h_{1}$ and $b^{\prime}=b h_{2}$, then $a^{\prime} b^{\prime}=a h_{1} b h_{2}$. Since $H$ is normal, there exists $h_{3}$ such that $h_{1} b=b h_{3}$ and thus $a^{\prime} b^{\prime}=a b h_{3} h_{2}$, which belongs to $a b H$.

## Example 3.3.9.

Let $n$ be a natural number, the groups $H=n \mathbb{Z}$ are normal subgroups of $\mathbb{Z}$. The quotient group $\mathbb{Z} / n \mathbb{Z}$ are the integers modulo $n$.

## Definition 3.3.10.

We call the order of $G$ the number of elements of $G$ and denote it by $|G|$.

Theorem 3.3.11 (Lagrange's Theorem).

If $H$ is a subgroup of a finite group $G$, then $|H|$ divides $|G|$.

Proof. The classes of $H$ define an equivalence relation

$$
a \sim b \Leftrightarrow \exists h \in H, a=b h .
$$

We will verify that it is symmetric, reflexive, and transitive.

We now need to make the following observation: All classes have $|H|$ elements. Indeed, if $b h_{1}=b h_{2}$, then $h_{1}=h_{2}$. Therefore, since $G$ is equal to the disjoint union of its classes, $|G|$ is equal to $|H|$ times the number of classes.

Definition 3.3.12.

Let $a \in G$. We call the order of $a$ (and denote it by $\operatorname{ord}(a)$) the smallest integer $k$ such that $a^{k}=e$.

## Remark 3.3.13.

If $a^{n}=e$, then $k$ divides $n$.

## Remark 3.3.14.

For all $a \in G$, the set $\left\{a^{k} \mid k \in \mathbb{Z}\right\}$ forms a subgroup of $G$. The order of this group is equal to $\operatorname{ord}(a)$.

## Corollary 3.3.15.

For all $a \in G$, $\operatorname{ord}(a)$ divides $|G|$.