Commençons avec les tours. Il ne peut évidemment y avoir qu'au plus une tour par rangée. Il y a donc au plus 8 tours. De plus, en plaçant les tours le long de la diagonale, on obtient une solution avec 8 tours.
Pour le problème avec les fous, on remarque qu'il y a 7 diagonales de cases blanches parallèles à la grande diagonale de cases blanches (incluant celle-là). Il ne peut y avoir au plus que 7 fous de cases blanches sur ces diagonales. Avec le même raisonnement, il ne peut y avoir que 7 fous de cases noires. Donc le nombre maximale est 14. De plus, voici une solution avec 14 fous.
Enfin pour les cavaliers, on peut se convaincre qu'on peut mettre 32 cavaliers : on peut mettre des cavaliers sur toutes les cases blanches ou toutes les cases noires par exemple.
Montrons maintenant que ce 32 est optimal. Pour cela, on remarque qu'on peut diviser notre échiquier en 8 pièces de taille 4x2 de la manière suivante
Sur chacune de ces parties, on ne peut placer que 4 cavaliers au maximum. En effet, on ne peut placer qu'un cavalier par couleur sur la figure suivante, et il n'y a que 4 couleurs.
On considère le graphe suivant. À chaque élève correspond un sommet du graphe, puis si deux élèves forment une paire gagnante, on trace une arête entre les sommets correspondants. Voici par exemple un tel graphe avec \(5\) élèves.
Montrons qu'il n'y a pas de triangles dans ce graphe. En effet, supposons par l'absurde qu'il existe un triangle, c'est à dire trois nombre irrationnels \(x_a\), \(x_b\) et \(x_c\) tel que \(x_a + x_b \in \mathbb{Q}\), \(x_a + x_c \in \mathbb{Q}\) et \(x_b + x_c \in \mathbb{Q}\). Dans ce cas, on a d'une part
$$
x_a + x_b + x_c = \underbrace{(x_a + x_b)}_{\mathbb{Q}} + x_c \notin \mathbb{Q},
$$
et d'autre part
$$
x_a + x_b + x_c = \frac12 \left( \underbrace{(x_a + x_b)}_{\mathbb{Q}} + \underbrace{(x_b + x_c)}_{\mathbb{Q}} + \underbrace{(x_c + x_a)}_{\mathbb{Q}} \right) \in \mathbb{Q},
$$
ce qui est impossible !
Quel est le plus grand nombre d'arêtes qu'un graphe à \(N\) sommets sans triangle peut avoir ? Soit \(G = (E,V)\) un tel graphe, et \(M\) ce nombre. On note \(E = (x_1, \ldots, x_{N})\) les sommets du graphe, et \(V = (s_1, \ldots, s_M)\) ses arêtes, où chaque \(s_k\) est de la forme \((x_{k_1}, x_{k_2}) \in E \times E\). Pour \(x \in E\), on note \(d(x)\) le degré de \(x\), c'est-à-dire le nombre d'arêtes qui partent ou arrivent de \(x\) (les arêtes ne sont pas orientés). On a (je laisse la démonstration)
$$
2 M = \sum_{k=1}^{N} d(x_k)
$$
Sans perte de généralité, on peut supposer que le sommet ayant le plus grand degré est \(x_N\), avec \(d(x_N) = K\), et \((x_k, x_N)_{1 \le k \le K} \in V\). Puisque \(x_1, \ldots x_K\) sont tous reliés à \(x_{N}\), aucun \(x_i\) ne peut être relié à \(x_j\) si \(1 \le i,j \le K\) (sinon, on aurait le triangle \((x_i, x_j, x_{N})\) dans le graphe \(G\)). En particulier, \(d(x_k) \le N - K\) pour tout \(1 \le k \le K\). De plus, pour tous les sommets \(x_{K+1}, \ldots, x_{N}\), on a \(d(x_k) \le K\) (par définition de \(K\)). Ainsi,
$$
2M = \sum_{k=1}^{N} d(x_k) = \sum_{k=1}^K d(x_k) + \sum_{k=K+1}^{N} d(x_k) \le K (N - K) + (N - K)K = 2K(N - K).
$$
Si \(N\) est pair, le maximum est atteint pour \(K = N/2\), et dans ce cas, on trouve \(M = (N/2)^2\). De plus, le maximum est atteint pour le graphe biparti \((N/2, N/2)\).
En ce qui concerne le problème, il ne peut pas y avoir plus de \((20/2)^2 = 100\) couples gagnants. De plus, il existe une solution avec \(100\) couples gagnants, par exemple :
