Préparation aux olympiades de mathématiques

MENABI EL OULOUM – EJYAL EL MUSTAGHBAL

QUELQUES PRINCIPES UTILES

1. Le principe de récurrence

Le raisonnement par récurrence est un raisonnement spécifique applicable dans le cas de propriétés
dépendant d’un entier naturel. On présentera ici, exemples à l’appui, les trois variantes de ce
raisonnement.

 Variante 1 : (récurrence d’ordre 1)

Théorème : Soit 𝒫(𝑛) une propriété dépendant du naturel 𝑛.
S’il existe un entier 𝑛 tel que :
- 𝒫(𝑛 ) est vraie (Initialisation) ;
- Pour tout 𝑛 ≥ 𝑛 , si 𝒫(𝑛) vraie alors 𝒫(𝑛 + 1) est vraie (Hérédité ou transmission)
Alors pour tout 𝑛 ≥ 𝑛 , 𝒫(𝑛) est vraie.

Exemple
Démontrer que pour tout entier naturel 𝐧 ≥ 𝟑, on peut trouver 𝐧 entiers strictement positifs 𝐱 𝟏 , 𝐱 𝟐 , …, 𝐱 𝐧
deux à deux distincts, tels que :
𝟏 𝟏 𝟏
+ + ⋯+ = 𝟏.
𝐱𝟏 𝐱𝟐 𝐱𝐧

Corrigé
Pour 𝐧 ≥ 𝟑, notons 𝓟(𝐧) la propriété suivante : « il existe 𝐧 entiers strictement positifs 𝐱 𝟏 , 𝐱 𝟐 , …, 𝐱 𝐧 deux
𝟏 𝟏 𝟏
à deux distincts, tels que : + + ⋯+ = 𝟏. »
𝐱𝟏 𝐱𝟐 𝐱𝐧
Prouvons que pour tout 𝐧 ≥ 𝟑, la propriété 𝓟(𝐧) est vraie.
1ère étape : Initialisation
Pour 𝐧 = 𝟑, on a bien :
𝟏 𝟏 𝟏
𝟏= + + .
𝟐 𝟑 𝟔
Donc 𝓟(𝟑) est vraie.
2ème étape : Hérédité
Montrons que pour tout 𝐧 ≥ 𝟑, si 𝓟(𝐧) est vraie alors 𝓟(𝐧 + 𝟏) est vraie.
Supposons qu’il existe un entier 𝐧 pour lequel la propriété 𝓟(𝐧) est vraie c’est-à-dire qu’il existe 𝐧
𝟏 𝟏 𝟏
entiers strictement positifs 𝐱 𝟏 , 𝐱 𝟐 , …, 𝐱 𝐧 deux à deux distincts, tels que : + + ⋯ + = 𝟏.
𝐱𝟏 𝐱𝟐 𝐱𝐧
On peut supposer que 𝟎 < 𝐱 𝟏 < 𝐱 𝟐 < ⋯ < 𝐱 𝐧 .
𝟏 𝟏
On remarque que 𝐱 𝟏 ≥ 𝟐 puisque + ⋯ + > 0.
𝐱𝟐 𝐱𝐧
On a :
𝟏 𝟏
𝟏= +
𝟐 𝟐
𝟏 𝟏 𝟏 𝟏 𝟏
𝟏= + + + ⋯+
𝟐 𝟐 𝐱𝟏 𝐱𝟐 𝐱𝐧
𝟏 𝟏 𝟏 𝟏
𝟏= + + + ⋯+
𝟐 𝟐𝐱 𝟏 𝟐𝐱 𝟐 𝟐𝐱 𝐧
𝟏 𝟏 𝟏 𝟏
𝟏 = + + + ⋯+
𝐲𝟏 𝐲𝟐 𝐲𝟑 𝐲𝐧 𝟏
en ayant posé 𝐲𝟏 = 𝟐, 𝐲𝐤 𝟏 = 𝟐𝐱 𝐤 pour 𝐤 = 𝟏, …, 𝐧. On a alors :
𝐲𝟏 = 𝟐 < 4 ≤ 𝐲𝟐 < 𝐲𝟑 < ⋯ < 𝐲𝐧 𝟏
On a donc établi la vérité de 𝓟(𝐧 + 𝟏).

1 Prof. Sidi MAJOR

3ème étape : Conclusion
On a donc : 𝓟(𝟑) est vraie.
Pour tout 𝐧 ≥ 𝟑, 𝓟(𝐧) entraîne 𝓟(𝐧 + 𝟏).
En conséquence, pour tout 𝐧 ≥ 𝟑 : 𝓟(𝐧) est vraie.

 Variante 2 : (récurrence d’ordre 2)

Théorème : Soit 𝒫(𝑛) une propriété dépendant du naturel 𝑛.
S’il existe un entier 𝑛 tel que :
- 𝒫(𝑛 ) et 𝒫(𝑛 + 1) sont vraies (Initialisation) ;
- Pour tout 𝑛 ≥ 𝑛 , si 𝒫(𝑛) et 𝒫(𝑛 + 1) sont vraies alors 𝒫(𝑛 + 2) est vraie (Hérédité ou
Transmission)
Alors pour tout 𝑛 ≥ 𝑛 , 𝒫(𝑛) est vraie.

Exemple
Considérons la suite (𝐮𝐧 ) définie, pour tout entier 𝐧, par les relations :
𝐮𝟎 = 𝟏, 𝐮𝟏 = 𝟏
.
𝐮𝐧 𝟐 = 𝟓𝐮𝐧 𝟏 − 𝟔𝐮𝐧
Démontrer que pour tout entier 𝐧 : 𝐮𝐧 = 𝟐𝐧 𝟏
− 𝟑𝐧 .
Corrigé
Soit 𝓟(𝐧) la propriété : « ∀𝐧 ∈ ℕ, 𝐮𝐧 = 𝟐𝐧 𝟏
− 𝟑𝐧 »

1ère étape : Initialisation

Pour 𝐧 = 𝟎, on a bien 𝟐𝟎 𝟏 − 𝟑𝟎 = 𝟏 = 𝐮𝟎 ,
Pour 𝐧 = 𝟏, on a bien 𝟐𝟏 𝟏 − 𝟑𝟏 = 𝟏 = 𝐮𝟏 .
Donc la propriété est vraie pour 𝐧 = 𝟎 et pour 𝐧 = 𝟏.
2ème étape : Hérédité
Montrons que pour tout 𝐧 ≥ 𝟏, si 𝓟(𝐧) et 𝓟(𝐧 + 𝟏) sont vraies alors 𝓟(𝐧 + 𝟐) est vraie.
Supposons qu’il existe un rang 𝐧 pour lequel la propriété est vraie pour 𝐧 et 𝐧 + 𝟏 c’est-à-dire que :
𝐮𝐧 = 𝟐𝐧 𝟏 − 𝟑𝐧 et 𝐮𝐧 𝟏 = 𝟐𝐧 𝟐 − 𝟑𝐧 𝟏
(Hypothèse de récurrence (H.R)).
Selon la définition de la suite (𝐮𝐧 ) :𝐮𝐧 𝟐 = 𝟓𝐮𝐧 𝟏 − 𝟔𝐮𝐧 .
En remplaçant 𝐮𝐧 et 𝐮𝐧 𝟏 par leurs valeurs supposées, on obtient :
𝐮𝐧 𝟐 = 𝟓(𝟐𝐧 𝟐 − 𝟑𝐧 𝟏 ) − 𝟔(𝟐𝐧 𝟏 − 𝟑𝐧 )
𝐮𝐧 𝟐 = (𝟏𝟎 − 𝟔) × 𝟐𝐧 𝟏 − (𝟏𝟓 − 𝟔) × 𝟑𝐧
𝐮𝐧 𝟐 = 𝟒 × 𝟐𝐧 𝟏 − 𝟗 × 𝟑𝐧
𝐮𝐧 𝟐 = 𝟐(𝐧 𝟐) 𝟏 − 𝟑𝐧 𝟐
Donc la propriété est vraie pour 𝐧 + 𝟐.
3ème étape : Conclusion
On a : 𝓟(𝟎) et 𝓟(𝟏) sont vraies.
Pour tout 𝐧 ≥ 𝟎, 𝓟(𝐧) et 𝓟(𝐧 + 𝟏) entraîne 𝓟(𝐧 + 𝟐).
En conséquence, pour tout 𝐧 ≥ 𝟎 : 𝓟(𝐧) est vraie.

 Variante 3 : (récurrence forte)

Théorème : Soit 𝒫(𝑛) une propriété dépendant du naturel 𝑛.
S’il existe un entier 𝑛 tel que :
- 𝒫(𝑛 ) est vraie (Initialisation) ;
- Pour tout 𝑘 ≥ 𝑛 , si 𝒫(𝑘) est vraie pour 𝑘 = 𝑛 , 𝑘 = 𝑛 + 1, …, 𝑘 = 𝑛 alors 𝒫(𝑛 + 1) est vraie
(Hérédité ou Transmission)
Alors pour tout 𝑛 ≥ 𝑛 , 𝒫(𝑛) est vraie.

Exemple
Montrer que tout entier naturel supérieur ou égal à 𝟐 est produit d’entiers premiers (on comprend le mot
produit dans le sens où il peut s’agir d’un produit d’un seul terme).
Corrigé
Soit 𝓟(𝐧) la propriété en question.
1ère étape : Initialisation

2 Prof. Sidi MAJOR

Pour 𝐧 = 𝟐, 𝓟(𝟐) est vraie car 𝟐 est premier.

2ème étape : Hérédité

Montrons que pour tout 𝐧 ≥ 𝟐, si 𝓟(𝟐), 𝓟(𝟑), …, 𝓟(𝐧) sont vraies alors 𝓟(𝐧 + 𝟏) est vraie.
De deux choses l’une, ou 𝐧 + 𝟏 est premier, ou il ne l’est pas.
 Si 𝐧 + 𝟏 est premier il s’écrit comme produit d’un entier premier, produit au sens défini dans l’énoncé.

 Si 𝐧 + 𝟏 n’est pas premier alors il est le produit de deux entiers différents de 𝟏 et de 𝐧 + 𝟏 ; ces deux
entiers sont donc compris entre 𝟐 et 𝐧, ils sont donc produits d’entiers premiers et donc 𝐧 + 𝟏 aussi.
3ème étape : Conclusion
On a : 𝓟(𝟐) est vraie.
Pour tout 𝐧 ≥ 𝟐, 𝓟(𝟐), 𝓟(𝟑), …, 𝓟(𝐧) entraînent 𝓟(𝐧 + 𝟏). En conséquence, pour tout 𝐧 ≥ 𝟐 : 𝓟(𝐧) est
vraie.

2. La descente infinie de Fermat

La descente infinie de FERMAT est un principe introduit la première fois par Pierre de FERMAT (magistrat
de formation, mathématicien amateur surnommé le prince des amateurs) et qu’il a utilisé fréquemment
dans ces travaux en théorie des nombres.

Elle repose sur le résultat suivant :

« Toute suite, d’entiers naturels, strictement décroissante est finie » ou en d’autres termes : « il
n’existe, dans ℕ, aucune suite strictement décroissante infinie ».
Le but de cette méthode est de prouver qu’une équation diophantienne (équation à inconnues dans ℤ)
n’admet pas de solutions.

Exemple
Montrer que le nombre √𝟐 est irrationnel.
Corrigé
Raisonnons par l’absurde :
𝐩𝟎
On suppose que √𝟐 est rationnel c’est-à-dire que √𝟐 = 𝐪𝟎 avec 𝐩𝟎 et 𝐪𝟎 des entiers naturels.On sait
𝐩
que : √𝟐 = 𝟎 𝐪𝟎 ⟺ 𝐩𝟎 𝟐 = 𝟐𝐪𝟎 𝟐 .
L’égalité 𝐩𝟎 𝟐 = 𝟐𝐪𝟎 𝟐 assure que 𝐩𝟎 est pair c’est-à-dire que 𝐩𝟎 = 𝟐𝐩𝟏 et donc l’égalité 𝐩𝟎 𝟐 = 𝟐𝐪𝟎 𝟐 s’écrit
𝐪𝟐𝟏 = 𝟐𝐩𝟐𝟏 .
Le même raisonnement nous conduit également à 𝐪𝟐 pair et à l’égalité : 𝐩𝟐𝟐 = 𝟐𝐪𝟐𝟐 .
Ainsi, cela nous amène à la suite d’entiers naturels strictement décroissante :
𝐩 𝐩 𝐩 𝐩
𝐩𝟎 , 𝐩𝟏 = 𝟎 𝟐, 𝐩𝟐 = 𝟎 𝟒, 𝐩𝟑 = 𝟎 𝟖, …, 𝐩𝐧 = 𝟎 𝟐𝐧
Or on sait qu’une telle suite n’existe pas et par suite notre hypothèse de la rationalité de √𝟐 est fausse.
D’où le résultat.

3. Le principe des tiroirs

Ce principe est parfois appelé principe des pigeons (pigeonhole en anglais). On l’attribue au
mathématicien franco-belge Dirichlet car c’est lui qui l’a utilisé la première fois dans des démonstrations
non évidentes.

Version simple : « Si 𝐧 + 𝟏 objets sont placés dans 𝐧 tiroirs, au moins un tiroir contiendra 𝟐 objets
ou plus ».

Version générale : « Si n objets sont placés dans 𝐤 tiroirs, au moins un tiroir contiendra 𝐄𝐧𝐭(𝐧/𝐤)
objets ou plus ».

3 Prof. Sidi MAJOR

Exemple
La Mauritanie compte 𝟒 𝟎𝟎𝟎 𝟎𝟎𝟎 d’habitants. Un être humain a, au plus 𝟔𝟎𝟎 𝟎𝟎𝟎 cheveux sur la tête. Au
vu de ces données, et sachant seulement cela, combien de mauritaniens peut-on trouver qui ont
exactement le même nombre de cheveux sur la tête.
Corrigé
Il y a 𝟒 𝟎𝟎𝟎 𝟎𝟎𝟎 d’habitants à placer dans 𝟔𝟎𝟎 𝟎𝟎𝟏 catégories, allant de celle des habitants ayant 𝟎
cheveux, jusqu’à celle des habitants ayant 𝟔𝟎𝟎 𝟎𝟎𝟎 cheveux. Alors, il y a, au moins, une catégorie qui
contient 𝐄𝐧𝐭(𝟒 𝟎𝟎𝟎 𝟎𝟎𝟎/𝟔𝟎𝟎 𝟎𝟎𝟏) = 𝟔 mauritaniens, ayant le même nombre de cheveux.

4. Le principe de l’invariance

Le principe des invariants consiste à trouver une quantité qui ne change pas, indépendamment des étapes
suivies dans un processus. Il s’agit d’une méthode permettant le plus souvent de démontrer qu’un
problème n’a pas de solution en cherchant une fonction (quantité) invariante dans une transformation
(processus).

Exemple
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 ?
Corrigé
L’algorithme consiste à ajouter 𝟐 au nombre de parties de feuille à chaque tour. Donc la parité du nombre
de parties est un invariant. Or on part d’une feuille, donc d’un nombre de parties égal à 𝟏, donc impair. Il
est donc impossible d’atteindre 𝟏𝟎𝟎 parties, qui est un nombre pair.

5. Le 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.

Exemple
Un jeton est posé sur chaque case d’un damier 7𝑥7. Les cases du damier sont repérées de la manière
suivante :
la case centrale a les coordonnées (𝐱 = 𝟎, 𝐲 = 𝟎) ; la coordonnée 𝐱 augmente de 𝟏 vers la droite et la
coordonnée 𝐲 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 :

– 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 le jeton situé sur la case (𝐱 = 𝐚, 𝐲 = 𝐛), il doit aussi prendre les jetons des
cases : (𝐱 = −𝐚, 𝐲 = 𝐛), (𝐱 = −𝐚, 𝐲 = −𝐛) et (𝐱 = 𝐚, 𝐲 = −𝐛). Le joueur qui a gagné est le premier qui
arrive à atteindre la situation où il reste un seul jeton, situé sur la case (𝐱 = 𝟏, 𝐲 = 𝟎). Un des joueurs
peut-il gagner ?

Corrigé
Les règles du jeu conduisent à une situation systématiquement symétrique par rapport au point de
coordonnées (𝐱 = 𝟎, 𝐲 = 𝟎). Une fin du jeu avec une seule case remplie de coordonnées (𝐱 = 𝟏, 𝐲 = 𝟎)
ne présenterait plus cette symétrie. Elle est donc impossible.

4 Prof. Sidi MAJOR

6. Le principe de l’extremum

On sait qu’un ensemble fini de nombres réels contient toujours un maximum et un minimum, et qu’un
ensemble éventuellement infini d’entiers naturels contient toujours un minimum.
Le principe de l’extremum est une heuristique qui consiste à considérer un objet pour lequel une
certaine quantité associée est minimale ou maximale.

Exemple
On se donne 𝐧 points du plan. On suppose que chaque triplet de points forme un triangle d’aire inférieure
ou égale à 𝟏. Montrer que les 𝐧 points sont tous à l’intérieur d’un triangle d’aire inférieure ou égale à 𝟒.
Corrigé
On considère trois points 𝐀, 𝐁, 𝐂 formant un triangle d’aire maximale. On trace la droite parallèle à un
des cotés et passant par le troisième sommet.

On sait qu’il n’y a pas de point dans la zone grise.

En effet, un tel point formerait avec les deux autres points un triangle d’aire plus grande que le triangle
𝐀𝐁𝐂 (il aurait une hauteur plus grande que celle de 𝐀𝐁𝐂 et la même base), ce qui contredirait la
maximalité supposée de l’aire du triangle 𝐀𝐁𝐂. Un raisonnement analogue avec les deux autres côtés
définit une zone autorisée de forme triangulaire, formée de quatre triangles semblables au triangle 𝐀𝐁𝐂,
et donc d’aire inférieure ou égale à 𝟒.

5 Prof. Sidi MAJOR