Combinatoire extrême

Je suis allé il y a peu de temps au séminaire What is…? de l’ETHZ (Zurich), pour écouter l’exposé What is … Extremal Combinatorics? Si vous passez à Zurich, allez à ce séminaire, qui est le seul séminaire que je connais où sont offerts des bières et des pizzas. L’orateur était D. Korándi, et nous a proposé une série de problèmes en rapport avec la combinatoire extrême, pour qu’on comprenne ce qu’est ce nouveau sport de l’extrême.

Nous commençons par un problème classique avec des échiquiers.

L’échiquier

Quel est le nombre maximum de tours qu’on peut placer sur un échiquier \({8 \times 8}\) sans qu’aucune ne puisse en prendre une autre ? Même question avec des fous. Même question avec des cavaliers.

La même question avec des pions ou des rois n’est pas très intéressante, et la question avec les dames est un classique d’algorithmique, connu sous le nom du Problème des huit dames.

Cliquez ici pour voir la solution
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 \({4 \times 2}\) 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.

J’ai beaucoup apprécié ce second problème et sa solution. Bonne chance !

Club-city (*)

Dans la petite ville de Club-city vivent 100 personnes. Chacune de ces personnes est membre de 0 ou plusieurs clubs (dont le club d’échecs, le club de maths, le club des détails qui ne font pas avancer l’énigme, etc.). Chaque club comprend un nombre impair de membres, et si on considère deux clubs différents quelconques, alors le nombre de membres communs à ces deux clubs est pair. Combien de clubs au maximum existe-t-il à Club-city ?

Cliquez ici pour voir la solution
Pour commencer, on s’aperçoit que si chaque habitant de Club-city est le seul membre de son club privé, alors on peut avoir 100 clubs dans Club-city. Montrons que ce nombre est maximum.
On note \({M}\) le nombre de clubs dans Club-city. Soit \({\mathbb{F}_2 := \mathbb{Z}/2\mathbb{Z}}\) le corps fini à deux éléments, et soit \({H = (\mathbb{F}_2)^{100}}\) un \({\mathbb{F}_2}\)-espace vectoriel de dimension 100, vu ici comme un espace de Hilbert avec le produit scalaire usuel:

\(\displaystyle \forall v = (v_1, \ldots, v_{100}) \in H, \ \forall w = (w_1, \ldots w_{100}) \in H, \quad \langle v, w \rangle := \sum_{j=1}^{100} v_j w_j \ \textrm{mod} \ 2. \)

Pour chaque \({1 \le k \le M}\), on introduit le vecteur \({v_k}\) tel que la \({j}\)-ème composante de \({v_k}\) est \({1}\) si l’habitant \({j}\) est membre du club \({k}\), et \({0}\) sinon. Par exemple, \({(1,1,1, 0,0, \ldots, 0)}\) représente un club dont les membres sont les habitants \({1}\), \({2}\) et \({3}\).

Puisque chaque club a un nombre impair de membres, on a

\(\displaystyle \forall 1 \le k \le M, \quad \langle v_k, v_k \rangle = \sum_{j=1}^{100} \left( v_k \right)_j^2 \ \textrm{mod} \ 2 = 1. \)

En particulier, les vecteurs \({v_k}\) sont non-nuls. De plus, comme le nombre de membres communs aux clubs \({k}\) et \({k’ \neq k}\) est pair, on a

\(\displaystyle \forall 1 \le k \neq k’ \le M, \quad \langle v_k, v_{k’} \rangle = \sum_{j=1}^{100} \left( v_k \right)_j \left( v_{k’} \right)_j \ \textrm{mod} \ 2 = 0, \)

donc les vecteurs \({v_k}\) sont orthogonaux. Autrement dit, la famille \({\left\{ v_k \right\}_{1 \le k \le M}}\) est libre dans \({H}\). Comme \({H}\) est de dimension \({100}\), on en déduit que \({M \le 100}\).

Le dernier exercice est plus complexe, et nécessite un peu de théorie des graphes…

Distribution de nombres irrationnels (**)

Une professeur de maths sadique décide de donner un nombre irrationnel différent à chacun de ces N élèves. Pour chaque paire d’élèves, on dit que la paire est gagnante si la somme des deux nombres qu’ils ont est rationnelle. Quel est le nombre maximum de paires gagnantes dans la classe?

Cliquez ici pour voir la solution
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

\(\displaystyle x_a + x_b + x_c = \underbrace{(x_a + x_b)}_{\mathbb{Q}} + x_c \notin \mathbb{Q}, \)

et d’autre part

\(\displaystyle 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 vous laisse la démonstration)

\(\displaystyle 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,

\(\displaystyle 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 notre 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 :

C’est tout pour aujourd’hui. Encore merci à D. Korándi pour ce lot de jolis problèmes.

Lien pour marque-pages : Permaliens.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *