(Rédigé par Yann Ollivier.)
Le principe des invariants est assez vague, c'est plutôt une méthode qu'un énoncé mathématique précis.
Principe des invariants - Si une quantité est conservée par une certaine classe de transformations, alors il est impossible de passer d'une situation à une autre où la quantité est différente en utilisant seulement des transformations de cette classe.
Ce sont souvent les seuls moyens qu'on a pour prouver que certaines choses sont impossibles. (Prouver que quelque chose est possible est souvent plus facile : il suffit de donner un exemple.)
La parité est souvent l'un des meilleurs invariants que l'on puisse trouver...
Exercice - Peut-on recouvrir un échiquier
avec des dominos
?
Exercice - Une feuille de papier est déchirée en trois parties. Ensuite, l'une de ces parties est déchirée de nouveau en trois parties, et ainsi de suite. Peut-on obtenir, en fin de compte, un total de cent parties ?
Exercice - Une grenouille domestique a été placée par son maître dans une salle de bains carrelée où sont installés un abri (A) et une baignoire (B). La grenouille saute de carreau en carreau à la recherche de l'entrée la baignoire pleine d'eau. Elle ne sait sauter que des manières indiquées par les flèches sur le dessin :
Arrivera-t-elle à passer de son abri à la baignoire ?
Exercice - Est-il possible de répartir les entiers
en
groupes disjoints de trois éléments chacun, de sorte que dans chaque groupe l'un des éléments soit la somme des deux autres ?
Exercice - 22 arbres sont mis en rond ; sur chaque arbre se pose un corbeau. Toutes les minutes, deux corbeaux se déplacent chacun sur un arbre voisin du leur. Est-il possible pour les corbeaux, après un certain nombre de minutes, de se rassembler tous sur le même arbre ?
Les symétries sont un cas particulier d'invariant :
Principe de symétrie - Si une situation est symétrique et qu'on ne peut la transformer qu'en utilisant des transformations symétriques, alors on ne peut pas arriver à une situation non symétrique.
Exercice - Un jeton est posé sur chaque case d'un damier
. Les cases du damier sont repérées de la manière suivante : la case centrale a les coordonnées
; la coordonnée x augmente de
vers la droite et la coordonnée y augmente de
vers le haut. Ainsi la case en bas à gauche est la case
et la case en haut à droite,
. Deux joueurs prennent, tour à tour, des jetons en respectant la règle suivante:
Le joueur qui a gagné est le premier qui arrive à atteindre la situation où il reste un seul jeton, situé sur la case
- si le premier joueur prend un jeton situé sur la case
, il doit aussi prendre les jetons des cases
,
et
;
- si le deuxième joueur prend un jeton situé sur la case
, il doit aussi prendre les jetons des cases
,
et
.
. Un des deux joueurs peut-il gagner ?
Les invariants peuvent aussi être de véritables quantités numériques définies à partir des données.
Exercice - À partir d'un triplet
on peut effectuer l'opération suivante :
Peut-on passer du triplet initial
- on choisit deux des nombres du triplet, mettons x et y ;
- on remplace x par
et y par
, en laissant le troisième nombre inchangé.
au triplet
en respectant ces règles ?
La parité revient à diviser les nombres entiers en deux couleurs alternativement : les multiples de
d'une couleur, les multiples de
plus
d'une autre couleur. On peut faire la même chose avec
: on colorie successivement les entiers en trois couleurs, à savoir d'un côté les multiples de
, d'un autre côté les multiples de
plus
, d'un troisième côté les multiples de
plus
. Si deux nombres a et b sont de la même couleur, on dit que a est congru à b modulo
. On peut aussi définir des congruences modulo
, ou modulo n'importe quel nombre.
Très souvent, dans des problèmes, une certaine quantité reste invariante modulo n pour un certain n ; cela veut dire qu'elle ne change que par des multiples de n. Chercher un n tel que certaines quantités ne changent que par des multiples de n fournit très souvent de bons invariants. La valeur de n à tester peut parfois être devinée par l'énoncé (y a-t-il
sortes d'objets ? regardez modulo
, peut-être modulo
ou
...).
Exercice - Sur une île déserte vivent
caméléons. Au départ
sont jaunes,
sont rouges et
sont verts. Lorsque deux caméléons de couleurs différentes se rencontrent, ils prennent tous les deux la troisième couleur. Lorsque se rencontrent deux caméléons d'une même couleur il ne se passe rien. Au bout d'un an tous les caméléons sur l'île sont devenus de la même couleur. Laquelle ? (Il faut non seulement déterminer la couleur, mais aussi prouver que c'est la seule possible.)
Exercice - On dispose d'une pile de 1001 jetons. On utilise les règles suivantes :
Peut-on se débrouiller pour qu'à un moment donné on n'ait que des piles de trois jetons ? (Attention : si une pile ne comporte qu'un jeton et qu'on retire ce jeton, on considère qu'on a désormais une pile à 0 jeton, et non que la pile a disparu.)
- au premier coup, on choisit un jeton que l'on élimine du jeu, et on sépare la pile en deux piles arbitraires ;
- puis, à chaque coup, on choisit un jeton que l'on élimine du jeu, et on sépare une pile (pas forcément celle dont on a extrait le jeton) en deux piles arbitraires.
Un autre truc : dès qu'il est question de somme des chiffres, il faut penser à regarder modulo
: en effet, un nombre et la somme de ses chiffres sont toujours dans la même classe modulo
(c'est ce qui fait marcher la « preuve par
»).
Exercice - On écrit successivement tous les nombres de
à un million. Puis, on remplace chaque nombre par la somme de ses chiffres. Puis on recommence, jusqu'à ce qu'il n'y ait plus que des nombres à un chiffre. Quel chiffre apparaît le plus souvent ?
