Sujet
Séries autres que S
Ahmed et Anrifa jouent ensemble à un jeu : ils dessinent sur leur feuille une grille carrée de taille quelconque, puis placent chacun à leur tour une croix dans une des cases de cette grille. Ils essayent de faire en sorte qu'il n'y ait jamais deux lignes, ni deux colonnes, ni une ligne et une colonne, qui comportent exactement le même nombre de croix. Le gagnant est alors celui qui a placé la dernière croix qui permet d'atteindre cette configuration. Au départ, toutes les lignes et colonnes sont vides, donc comptent toutes le même nombre de croix : zéro. Le but du problème est de montrer que ni Ahmed ni Anrifa ne pourront jamais gagner à ce jeu...1. Étude d'un premier cas
On considère la grille \(6 \times 6\) suivante :
a) Placer, au hasard, un nombre quelconque de croix dans la grille cidessus (à rendre avec votre copie), comme le feraient Ahmed et Anrifa. Vous arrêtez de placer des croix quand vous voulez...
b) Citer alors soit deux lignes, soit deux colonnes, soit une ligne et une colonne, qui comptent exactement le même nombre de croix.
Le jeu est donc perdu !
2. Une première généralisation
On considère la même grille \(6 \times 6\) que dans la partie précédente. Ahmed et Anrifa ont placé dans les cases de cette grille un nombre quelconque de croix.a) Pour une ligne ou une colonne quelconque de la grille, quelles valeurs peut prendre le nombre de croix qui y sont placées?
b) Combien cette grille compte-t-elle au total de lignes et de colonnes ?
c) Démontrer que dans cette grille, quel que soit le nombre de croix placées, on peut toujours trouver deux lignes, ou deux colonnes, ou une ligne et une colonne, qui comptent exactement le même nombre de croix.
3. Généralisation finale
On considère une grille de taille quelconque \(\mathrm{N} \times \mathrm{N}\), où N est un entier supérieur à 1. Ahmed et Anrifa placent successivement et au hasard dans les cases de cette grille, un nombre quelconque de croix.Démontrer qu'il est toujours possible de trouver deux lignes, ou deux colonnes, ou une ligne et une colonne, qui comptent exactement le même nombre de croix, et ce quels que soient les choix d'Ahmed et d'Anrifa.
Séries autres que S
Ahmed et Anrifa jouent ensemble à un jeu : ils dessinent sur leur feuille une grille carrée de taille quelconque, puis placent chacun à leur tour une croix dans une des cases de cette grille. Ils essayent de faire en sorte qu'il n'y ait jamais deux lignes, ni deux colonnes, ni une ligne et une colonne, qui comportent exactement le même nombre de croix. Le gagnant est alors celui qui a placé la dernière croix qui permet d'atteindre cette configuration. Au départ, toutes les lignes et colonnes sont vides, donc comptent toutes le même nombre de croix : zéro. Le but du problème est de montrer que ni Ahmed ni Anrifa ne pourront jamais gagner à ce jeu...1. Étude d'un premier cas
On considère la grille \(6 \times 6\) suivante :
a) Placer, au hasard, un nombre quelconque de croix dans la grille ci-dessus (à rendre avec votre copie), comme le feraient Ahmed et Anrifa. Vous arrêtez de placer des croix quand vous voulez... Voir la figure ci-dessus.
b) Dans la configuration ci-dessus, on remarque par exemple que \(L_{4}\) et \(L_{6}\) comptent deux crois, que \(c_{1}\) et \(C_{6}\) en comptent trois et que \(C_{2}\) et \(L_{6}\) en comptent deux. Le jeu est donc perdu !
2. Une première généralisation
On considère la même grille \(6 \times 6\) que dans la partie précédente. Ahmed et Anrifa ont placé dans les cases de cette grille un nombre quelconque de croix.a) Dans uine ligne ou une colonne quelconque, on peut mettre \(0,1,2,3,4,5\) ou 6 croix (soit sept possibilités).
b) Combien cette grille compte-t-elle au total de lignes et de colonnes ?
La grille compte 6 lignes et 6 colonnes, soit au total 12 éléments.
c) Chacun des 12 éléments listés ci-dessus (ligne ou colonne) doit se voir attribuer un nombre de croix parmi les 7 possibilités listées à la question a). Comme \(12>7\), les nombres de croix attribués à ces 12 éléments ne peuvent pas
être tous différents (c'est le principe des tiroirs : il n'existe pas d'injection d'un ensemble de cardinal \(n\) dans un ensemble de cardinal \(p\) si \(n>p\) ). On en déduit qu'il existe toujours au moins deux éléments (ligne ou colonne) qui comptent le même nombre de croix.
3. Généralisation finale
Dans une grille de taille \(N \times N\), il y a \(N\) lignes et \(N\) colonnes, soient \(2 N\) éléments. Dans chaque ligne ou chaque colonne, on peut placer \(0,1, \ldots, N\) croix, soit \(N+1\) possibilités. Il faut donc attribuer aux lignes et aux colonnes \(2 N\) valeurs prises parmi \(N+1\) possibilités.Or \(2 N>N+1\) si \(N>1\). Toujours d'après le principe des tiroirs, il n'est pas possible d'attribuer à ces \(2 N\) éléments des valeurs toutes distinctes. Il doit donc y avoir au moins deux éléments qui comptent le même nombre de croix.