Le principe des tiroirs

La propriété à laquelle nous allons nous intéresser ici exprime un fait parfaitement évident.

Elle permet pourtant d’établir des résultats qui, pour certains d’entre-eux, sont loin d’être immédiats !

Il s’agit du « principe des tiroirs », encore appelé « principe de Dirichlet », du nom du mathématicien allemand Peter Gustav Lejeune Dirichlet (1805 – 1859) (voir section 7 du présent article).

Voici son énoncé :

Principe des tiroirs

Si l’on range $n+1$ objets dans un meuble comportant $n$ tiroirs alors, peu importe la manière dont on procède, l’un au moins des tiroirs contiendra au moins 2 objets.

En anglais, la terminologie consacrée est plutôt « principe des nichoirs ». Une version plus « british » de cet énoncé pourrait donc être :

Pigeonhole principle … in french

Si $n+1$ pigeons sont répartis dans $n$ nichoirs, alors l’un (au moins) des nichoirs accueillera nécessairement deux pigeons (ou davantage)

Dans cette illustration, on voit six pigeons et cinq nichoirs. L’un (au moins) des nichoirs (repéré par un cercle rouge) doit héberger plus d’un pigeon !

Signalons une version améliorée de ce principe.

Considérons une collection de 1000 pièces de monnaie, qu’on décide de classer en 3 catégories : « pièces en or », « pièces en argent » et « autres métaux ».

Si l’on suppose que chacune de ces trois catégories comporte au maximum 333 pièces, alors l’ensemble sera composé d’au plus 3 $\times$ 333 = 999 pièces, ce qui est absurde !

Par conséquent, l’une de trois catégories doit comporter au moins 334 pièces.

Plus généralement …

Principe des tiroirs généralisé

Si $n$ objets sont répartis en $q$ classes, alors l’une d’elles doit comporter au minimum $\left\lceil \frac{n}{q}\right\rceil$ objets.

Le symbole $\left\lceil x\right\rceil$ désigne la partie entière par excès du réel $x,$ c’est-à-dire le plus petit entier supérieur ou égal à $x$ .

On va maintenant présenter quelques applications du principe des tiroirs, en commençant par des exemples simples et en compliquant au fur et à mesure.

1 – Coloriages du plan

Imaginons que nous disposions de deux couleurs pour colorier un plan (un plan de mathématicien, bien sûr !… c’est-à-dire s’étendant indéfiniment dans toutes les directions…). Cela signifie que chaque point du plan se voit attribuer une couleur, parmi deux possibles.

Considérons par ailleurs une distance quelconque $d>0.$ Il existe alors fatalement deux points, situés à la distance $d$ l’un de l’autre, qui sont de la même couleur.

Pour s’en convaincre, il suffit de dessiner dans ce plan un triangle équilatéral de coté $d.$ Comme on ne dispose que de deux couleurs, deux des trois sommets (peut-être même les trois !) sont nécessairement de la même couleur… et c’est gagné !

Dans l’illustration ci-dessus, deux des trois sommets du triangle équilatéral sont verts.

De manière analogue, on peut prouver que si l’espace (à trois dimensions) est colorié (de manière arbitraire) à l’aide de trois couleurs, alors pour toute distance $d>0,$ il existera deux points situés à la distance $d$ l’un de l’autre, qui seront de la même couleur.

Voyez-vous comment l’argument utilisé dans le cas du plan pourrait être adapté ?

Une solution est consultable en fin d’article.

2 – Points à coordonnées entières

Munissons le plan d’un repère (orthonormal ou non, peu importe) et plaçons cinq points à coordonnées entières : l’abscisse et l’ordonnée de chacun d’eux sont des nombres entiers.

Dans le dessin ci-dessous, ces cinq points sont représentés en rouge. Intéressons-nous aux milieux (représentés en bleu) des segments limités par deux points rouges. Les points bleus sont au nombre de $\binom{5}{2}=10$ (voir cet article sur les coefficients binomiaux).

Est-il possible que parmi les dix points bleus, il ne s’en trouve aucun dont les coordonnées soient toutes deux entières ?

Je vous laisse le plaisir d’y réfléchir vous-même : la réponse est détaillée en fin d’article.

3 – Une somme multiple de n

Etant donnés des entiers $a_{1},\cdots,a_{n}$ quelconques, on va montrer qu’il est toujours possible, en ajoutant certains d’entre eux, d’obtenir un total multiple de $n$ (la somme doit comporter au moins un terme et l’on s’interdit de prendre plusieurs fois le même).

Nous allons établir ce résultat en appliquant convenablement le principe des tiroirs.

Considérons les entiers :

$S_{1}=a_{1},\quad S_{2}=a_{1}+a_{2},\qquad\cdots\qquad S_{n}=a_{1}+\cdots+a_{n}$

Si l’un des $S_{i}$ est multiple de $n,$ c’est terminé !

Sinon, le reste de la division de chaque $S_{i}$ par $n$ appartient à $\llbracket1,n-1\rrbracket.$ Nous avons donc $n$ restes et seulement $n-1$ valeurs possibles pour ces restes, d’où fatalement deux restes égaux !

Il existe ainsi des indices $i,j\in\llbracket1,n\rrbracket$ tels que $i<j$ et $S_{j}-S_{i}$ multiple de $n.$ Autrement dit : $a_{i+1}+\cdots+a_{j}\text{ multiple de }n,$ et le résultat souhaité est établi.

Notons que cette preuve est « algorithmique », ce qui signifie qu’elle permet, sans effort supplémentaire, d’écrire un programme qui résout toute instance de ce problème.

Voici, écrit en Python, un tel programme :

def somme_congrue(L):
  n = len(L)
  s = 0
  i = 0
  restes = []
  encore = True
  while encore:
    s = s + L[i]
    r = s % n
    if r == 0:
      return L[0 : i+1]
    elif restes.count(r) == 0:
      restes.append(r)
    else:
      return L[restes.index(r) + 1 : i + 1]
    i += 1

Etant donnée une liste L d’entiers, cette fonction calcule les sommes :

L[0], L[0] + L[1], L[0] + L[1] + L[2], etc …

Si l’une d’elles est multiple de n (= la longueur de la liste L), c’est réglé et on s’arrête.

Et si l’une de ces sommes, non multiple de n, est congrue au même reste modulo n qu’une autre somme calculée antérieurement, alors leur différence, qui est une somme du type L[i+1] + … + L[j], convient.

Dans tous les cas, la fonction somme_congrue renvoie une sous-liste (formée de termes consécutifs) de L, dont la somme des termes est multiple de n.

Un exemple :

>>> somme_congrue([17, 3, 12, 7, 10, 3, 5, 1, 5])
[10, 3, 5]

On voit bien, en effet, que dans la séquence [17, 3, 12, 7, 10, 3, 5, 1, 5], qui est de longueur 9, la sous-séquence indiquée en rouge totalise 18, qui est un multiple de 9.

4 – Deux exercices à tiroirs 🙂

Chacune des deux questions suivantes met en évidence une particularité des tirages de $n+1$ entiers parmi $1,2,\cdots,2n.$

Question 1

Choisissons quelques nombres entiers parmi 1, 2, 3, $\cdots$ 10 et regardons s’il est possible d’obtenir un total de 11 en ajoutant deux d’entre-eux.

Avec cinq entiers seulement, cela peut ne pas fonctionner, comme on le voit en choisissant 1, 2, 3, 4, 5 (la plus grande somme accessible est 9 = 4 + 5).

Et avec six entiers ? Essayons quelques possibilités, pour voir :

$1,2,3,4,\boxed{5},\boxed{6}\rightarrow\text{OK}$

$1,3,\boxed{4},5,\boxed{7},9\rightarrow\text{OK}$

$\boxed{1},3,5,7,9,\boxed{10}\rightarrow\text{OK}$

$\boxed{3},4,5,\boxed{8},9,10\rightarrow\text{OK}$

Jusqu’ici, cela semble concluant : il semble que, peu importe les six entiers choisis, il s’en trouve toujours deux ayant pour somme 11.

Mais que faire pour en être absolument certain ? On pourrait poursuivre l’énumération des différentes possibilités … sauf qu’il en existe $\binom{10}{6}=210$ (voir l’article sur les propriétés des coefficients binomiaux) ! Et même en effectuant cette tâche fastidieuse, nous n’aurions rien traité de plus qu’un cas particulier : celui où l’on choisit 6 entiers parmi 1, …,10.

Le cas général consiste à montrer qu’en choisissant d’une manière quelconque $n+1$ entiers parmi $1,\cdots,2n$ , il s’en trouvera certainement deux ayant pour somme $2n+1$ .

Il est possible, grâce au principe des tiroirs, de traiter ce cas général de manière élégante.

Voici comment :

Considérons un ensemble $X$ de $n+1$ entiers choisis parmi $1,2,3,\cdots,2n.$

En formant les $n$ paires d’entiers « complémentaires » :

$\left\{ 1,2n\right\} ,$ $\left\{ 2,2n-1\right\} ,$ $\left\{ 3,2n-2\right\} ,$ etc … $\left\{ n,n+1\right\} ,$

on voit que deux des $n+1$ éléments de $X$ appartiendront à la même paire.

C’est tout 🙂

Question 2

On peut choisir cinq entiers parmi 1, 2, 3, $\cdots$ 10 de telle sorte qu’aucun d’entre eux n’en divise un autre. C’est en effet le cas si l’on choisit :

$4,5,6,7,9$

Même chose en choisissant :

$5,6,7,8,9$

On peut d’ailleurs vérifier que ce sont là les deux seules possibilités.

En revanche, si l’on choisit six entiers parmi 1, 2, 3, $\cdots$ 10, alors peu importe la manière de procéder : deux d’entre eux seront tels que le plus petit divise le plus grand.

Là encore, une solution consisterait à passer en revue les 210 configurations possibles… mais comme on l’a déjà expliqué, ce n’est pas une tâche très passionnante et il vaut mieux se pencher sur le cas général. Nous allons montrer que :

Si $n$ est un entier supérieur ou égal à 1, alors pour tout sous-ensemble $X$ de $\llbracket1,2n\rrbracket$ de cardinal $n+1,$ il existe deux entiers distincts $a,b\in X$ tels que $a\mid b.$

Pour cela, on commence par écrire chaque élément de $X$ sous la forme $2^{\alpha}m$ avec $\alpha\geqslant0$ et $m$ impair (tout entier naturel non nul peut s’écrire ainsi et d’une seule façon).

Nécessairement $1\leqslant m\leqslant2n-1,$ ce qui donne $n$ possibilités pour $m$ (en effet, les entiers impairs $1,$ $3,$ $5,$ …, $2n-1$ sont au nombre de $n).$

Comme $X$ renferme $n+1$ éléments, le principe des tiroirs impose que deux d’entre eux soient associés au même $m.$ Ainsi, il existe des entiers $\alpha<\beta$ tels que $X$ contienne $2^{\alpha}m$ et $2^{\beta}m.$ Et manifestement, le premier est un diviseur du second.

Je trouve cette preuve vraiment élégante ! En outre, elle illustre parfaitement la puissance du principe des tiroirs.

Précisons qu’il est possible d’établir le même résultat par une récurrence, mais elle n’est pas commode et cela conduit à quelque chose de nettement moins lumineux :

On prouve par récurrence que l’assertion $\mathcal{A}_{n}$ suivante est vraie pour tout entier $n\geqslant1$ :

$\mathcal{A}_{n}$ : « Pour tout $X\subset\llbracket1,2n\rrbracket$ vérifiant $\text{card}\left(X\right)=n+1,$ il existe $\left(a,b\right)\in X^{2}$ tel que $a\neq b$ et $a\mid b$ »

D’évidence, $\mathcal{A}_{1}$ est vraie.

Supposons $\mathcal{A}_{n}$ vraie pour un certain $n\geqslant1$ et soit $X\subset\llbracket1,2n+2\rrbracket$ tel que $\textrm{Card }\left(X\right)=n+2.$

➡ Si aucun des entiers $2n+1$ et $2n+2$ n’appartient à $X,$ alors $X\subset\llbracket1,2n\rrbracket$ et l’hypothèse de récurrence s’applique à $X$ privé de l’un quelconque de ses éléments.

➡ Si l’un seulement des entiers $2n+1$ et $2n+2$ se situe hors de $X,$ alors l’hypothèse de récurrence s’applique au sous-ensemble de $X$ obtenu en supprimant l’autre.

➡ Supposons à présent que $2n+1$ et $2n+2$ appartiennent à $X.$

Si $n+1\in X,$ c’est terminé puisque $n+1\mid2n+2.$
Sinon, on considére l’ensemble $Y$ déduit de $X$ en remplaçant $2n+2$ par $n+1.$ D’après l’hypothèse de récurrence, il existe $a,b\in Y-\left\{ 2n+1\right\}$ tels que $a\neq b$ et $a\mid b.$
Si $a=n+1,$ alors nécessairement $b=2n+2,$ ce qui est exclu. Donc $a\neq n+1$ et en particulier $a\in X.$
Si $b\neq n+1,$ alors $a,b\in X$ et c’est réglé; et si $b=n+1,$ alors a fortiori $a\mid2n+2$ et c’est encore gagné : on a su trouver dans tous les cas deux éléments de $X,$ l’un divisant l’autre.

Pour en savoir plus sur les preuves par récurrences, voir cet article introductif et cet autre article, plus approfondi.

5 – Multi-Jackpot

Notons $A_{n}$ l’entier dont l’écriture décimale comporte $n$ fois le chiffre 7. Par exemple :

$A_{1}=7\qquad A_{2}=77\qquad A_{3}=777$

Donnons-nous aussi $Q\in\mathbb{N}$ premier avec 10 (càd : qui ne soit multiple ni de 2 ni de 5).

Il existe alors nécessairement un entier $n\geqslant1$ tel que $A_{n}$ soit multiple de $Q.$

En effet, considérons les nombres $A_{1},\thinspace A_{2},\cdots,A_{Q+1}$ et effectuons la division (euclidienne) de chacun d’eux par $Q.$ Comme chacun des $Q+1$ restes est compris entre $0$ et $Q-1$ (ce qui représente évidemment $Q$ possibilités), on voit d’après le principe des tiroirs qu’il doit y avoir deux restes égaux.

Reformulons… il existe nécessairement des entiers $i,j$ tels que :

➡ $1\leqslant i<j\leqslant Q+1,$
➡ la division de $A_{i}$ par $Q$ et celle de $A_{j}$ par $Q$ donnent le même reste.

On parvient ainsi, par différence, à l’égalité :

$A_{j}-A_{i}=kQ$

où $k$ est un entier. Mais il se trouve que :

$A_{j}-A_{i}=10^i\,A_{j-i}\qquad\left(\star\right)$

et il en résulte que $Q$ est un diviseur de $10^i\,A_{j-i}.$

Si la formule $\left(\star\right)$ n’est pas claire, l’examen d’un exemple devrait aider :

$A_{7}-A_{3}=7777777-777=7777000=10^{3}\times A_{4}=10^3\times A_{7-3}$

A présent intervient un incontournable théorème d’arithmétique :

Théorème de Gauss

Soient $a,b,c$ trois entiers naturels non nuls.

Si $a$ divise $bc$ et si $a$ est premier avec $b,$ alors $a$ divise $c$ .

Comme $Q$ est premier avec $10$ et donc avec $10^{j-i},$ on voit en appliquant le théorème de Gauss que $Q$ divise $A_{j-i}.$ Notre objectif est atteint !

Sauriez-vous trouver, par programme, le plus petit $n$ pour lequel $A_{n}$ est divisible par $37$ ? Et par $31$ ? Et par $29$ ? Réponses en fin d’article.

6 – Cure de remise en forme

C’est décidé, dès demain, je me remets au sport !

Afin de m’obliger à reprendre de bonnes habitudes, j’ai décidé que pendant $30$ jours consécutifs, je ferai au moins une séance de gym chaque jour. En outre, je m’impose au cours de cette période, un total de $40$ séances.

Fatalement, il y aura des jours où je devrai faire au moins deux séances ! Mais on peut affirmer quelque chose de moins évident : il y aura nécessairement une suite de jours consécutifs au cours desquels je devrai faire exactement $19$ séances.

Pour expliquer cela, notons $S_{i}$ le nombre de séances de gym effectuées entre le premier et le $i-$ ème jour (inclus). On a donc :

$1\leqslant S_{1}<S_{2}<\cdots<S_{30}=40$

Si l’on ajoute $19$ à chaque membre des inégalités précédentes, il vient :

$S_{1}+19<S_{2}+19<\cdots<S_{30}+19=59$

Les $60$ nombres entiers $S_{i}$ (pour $1\leqslant i\leqslant30)$ et $S_{j}+19$ (pour $1\leqslant j\leqslant30)$ sont tous compris entre $1$ et $59.$ D’après le principe des tiroirs, deux d’entre-eux doivent être égaux. Mais les 30 premiers sont tous distincts, de même que les 30 suivants. Il existe donc des indices $i,j$ tels que $i<j$ et $S_{i}+19=S_{j}.$

Bien sûr, on peut généraliser…

Proposition

Si $S_{1},\cdots,S_{N}$ sont des entiers tels que :

$1\leqslant S_{1}<S_{2}<\cdots<S_{N}<2N-1$

alors, en posant $Q=2N-1-S_{N}$ :

$S_{1}+Q<\cdots<S_{N}+Q=2N-1$

et par le même raisonnement, il existe des indices $i,j$ tels que :

$1\leqslant i<j\leqslant N\text{ et }S_{i}+Q=S_{j}$

7 – Approximation par des rationnels

Abordons un exemple lié à ce qu’on appelle la théorie des nombres.

Rappelons, pour commencer, qu’un nombre algébrique est par définition un nombre complexe $z$ pour lequel il existe un polynôme non nul à coefficients entiers qui admet $z$ parmi ses racines. Le plus petit degré d’un tel polynôme est appelé le degré (d’algébricité) de $z.$ Bien entendu, ce degré vaut $1$ lorsque $z$ est rationnel.

Une question importante de théorie des nombres consiste à étudier la précision (ou l’imprécision) avec laquelle un nombre réel peut être approché par des nombres rationnels. Dans ce cadre, un résultat célèbre dû au mathématicien français Joseph Liouville montre que les nombres réels algébriques sont, en un sens, « difficiles à approcher ».

Théorème de Liouville

Si $x\in\mathbb{R}$ est algébrique de degré $d\geqslant2,$ alors il existe $C>0$ tel que pour tout $\left(p,q\right)\in\mathbb{Z}\times\mathbb{N}^{\star}$ :

$\left|x-\frac{p}{q}\right|\geqslant\frac{C}{q^{d}}.$

Ce théorème permit à Liouville de donner le premier exemple connu de nombre transcendant. Il pu en effet établir que le nombre réel :

$\xi=\sum_{n=0}^{\infty}\frac{1}{10^{n!}}$

ne vérifie la condition précédente pour aucun entier $d\geqslant2.$

La première démonstration de ce résultat remarquable a été publiée par Liouville en 1851, dans le Journal de Mathématiques Pures et Appliquées.

Voici un autre résultat, dû à Dirichlet et quasiment contemporain du précédent :

Théorème de Dirichlet

Si $x\in\mathbb{R}$ et $N\in\mathbb{N^{\star}},$ alors il existe $\left(p,q\right)\in\mathbb{Z}\times\mathbb{N}^{\star}$ tel que

$\left|x-\frac{p}{q}\right|<\frac{1}{qN}\qquad\text{et }0<q\leqslant N.$

Corollaire

Si $x$ est irrationnel, alors il existe une infinité de rationnels $\frac{p}{q}$ tels que :

$\left|x-\frac{p}{q}\right|<\frac{1}{q^{2}}.$

C’est pour l’établir que Dirichlet a introduit le Schubfachprinzip, terme allemand qui a été traduit par « principe des tiroirs ».

Passons à la preuve du théorème de Dirichlet :

Preuve (cliquer pour déplier / replier)

Pour tout réel $t,$ nous noterons $\left{ t\right}$ la partie fractionnaire de $t;$ c’est par définition la différence entre $t$ et sa partie entière :

$\left{ t\right} =t-\left\lfloor t\right\rfloor \in\left[0,1\right[$

Soient $x\in\mathbb{R}$ et $N\in\mathbb{N}^{\star}.$ Comme l’intervalle $\left[0,1\right[$ est l’union disjointe des $N$ « tranches » $\left[\frac{i}{N},\frac{i+1}{N}\right[$ pour $0\leqslant i\leqslant N-1,$ le principe des tiroirs assure que deux (au moins) des $N+1$ réels $\left\{ x\right\} ,\left\{ 2x\right\} ,\cdots,\left\{ \left(N+1\right)x\right\}$ tombent dans une même tranche.

Autrement dit, il existe deux entiers $k,\ell$ tels que $1\leqslant k<\ell\leqslant N+1$ ainsi qu’un entier $i\in\llbracket0,N-1\rrbracket$ vérifiant :

$\frac{i}{N}\leqslant\left\{kx\right\} ,\left\{\ell x\right\} <\frac{i+1}{N}$

Dès lors :

$\left|\left\{\ell x\right\} -\left\{kx\right\} \right|<\frac{1}{N}$

c’est-à-dire :

$\left|\left(\ell-k\right)x-\left(\left\lfloor \ell x\right\rfloor -\left\lfloor kx\right\rfloor \right)\right|<\frac{1}{N}$

ou encore, en posant $p=\left\lfloor \ell x\right\rfloor -\left\lfloor kx\right\rfloor$ et $q=\ell-k$ :

$\boxed{\left|x-\frac{p}{q}\right|<\frac{1}{qN}\qquad\text{avec }\left(p,q\right)\in\mathbb{Z}\times\mathbb{N}^{\star}\text{ et }q\leqslant N}$

En un sens, ce théorème de Dirichlet et son corollaire « contrebalancent » le résultat de Liouville : l’un dit en gros que tout irrationnel est approchable à l’ordre au moins 2 par des rationnels, tandis que l’autre exprime l’impossibilité, pour $x$ algébrique de degré $d,$ d’aller au-delà de l’ordre $d.$

8 – Un théorème de P. Erdös et G. Szekeres

Le célèbre théorème de Bolzano-Weierstrass affirme qu’on peut extraire de toute suite réelle bornée une sous-suite convergente.

Ce résultat peut être démontré très rapidement si l’on connaît le :

Lemme des pics

De toute suite réelle, on peut extraire une sous-suite monotone.

En effet, si une suite réelle est bornée, elle admettra d’après ce lemme une sous-suite monotone et bornée, donc convergente.

On peut donner une preuve directe de ce lemme (voir l’exercice n° 9 de cette fiche), ou bien le voir comme un corollaire d’un important théorème de F. Ramsey :

Théorème (Ramsey)

Pour tout graphe complet infini et pour toute coloration finie de ce graphe, il existe un sous-graphe complet monochrome infini.

Il suffit en effet, étant donnée une suite réelle $u,$ de considérer le graphe complet dont les sommets sont les entiers naturels et de le colorier de la façon suivante. L’arête $\left\{i,j\right\}$ est coloriée en :

rouge si $u_{i}<u_{j}$
vert si $u_{i}=u_{j}$
bleu si $u_{i}>u_{j}$

L’existence d’un sous-graphe complet monochrome infini exprime alors l’existence d’une sous-suite strictement monotone ou constante.

Venons-en à l’objet de cette section. En 1935, les mathématiciens hongrois Paul Erdös et Georges Szekeres publièrent ce qu’on pourrait appeler une « version finie » du lemme des pics :

Théorème (Erdös – Szekeres)

Soient $m,n$ deux entiers naturels non nuls. De toute liste de $mn+1$ réels, on peut extraire une sous-liste croissante de longueur $m+1$ ou une sous-liste décroissante de longueur $n+1.$

Dans cet énoncé, le « ou » est inclusif et l’adjectif « (dé)croissante » doit être compris au sens large.

Soit $\ell=\left(a_{1},\cdots,a_{mn+1}\right)$ une liste de réels. Supposons que toute sous-liste croissante de $\ell$ soit de longueur $\leqslant m$ et que toute sous-liste décroissante de $\ell$ soit de longueur $\leqslant n.$

Pour chaque $i\in\llbracket1,mn+1\rrbracket,$ notons :

➡ $U_{i}$ la longueur maximum d’une sous-liste croissante qui démarre en $a_{i}$

➡ $D_{i}$ la longueur maximum d’une sous-liste décroissante qui démarre en $a_{i}$

Par hypothèse $1\leqslant U_{i}\leqslant m$ et $1\leqslant D_{i}\leqslant n$ pour tout $i$ , d’où $mn$ valeurs possibles pour les $mn+1$ couples $\left(U_{i},D_{i}\right).$ D’après le principe des tiroirs, il existe deux indices $j,k$ tels que $1\leqslant j<k\leqslant mn+1$ tels que $\left(U_{j},D_{j}\right)=\left(U_{k},D_{k}\right).$ Notons $\left(\alpha,\beta\right)$ ce couple. Si $a_{j}\leqslant a_{k},$ alors en préfixant par $a_{j}$ une sous-liste croissante de longueur $\alpha$ qui démarre en $a_{k},$ on obtient une sous-liste croissante de longueur $\alpha+1$ qui démarre en $a_{j}$ : c’est impossible ! Et si $a_{j}>a_{k},$ alors en préfixant par $a_{j}$ une sous-liste décroissante de longueur $\beta$ qui démarre en $a_{k},$ on obtient une sous-liste décroissante de longueur $\beta+1$ qui démarre en $a_{j}$ : c’est impossible !

Cette contradiction montre que $\ell$ possède une sous-liste croissante de longueur $\geqslant m+1$ ou une sous-liste décroissante de longueur $\geqslant n+1.$

Cette photographie, prise en 1984 à l’université de Newcastle (Australie) montre Georges Szekeres (à droite), son épouse Esther (née Klein) et Paul Erdös (au milieu). Georges et Esther Szekeres furent des mathématiciens de premier plan. Quant à Paul Erdös, on peut dire qu’il fut un mathématicien hors norme.

Esther Szekeres fut notamment à l’origine d’une très jolie question de géométrie combinatoire : étant donnés cinq points du plan en position générale (càd qu’on ne peut pas trouver, parmi eux, trois points alignés), montrer que quatre d’entre eux sont les sommets d’un quadrilatère convexe. Ce problème, résolu par Georges Szekeres, fut dénommé « happy ending problem » par Paul Erdös, car Georges et Esther se marièrent peu de temps après.

Réponses aux questions laissées en suspens

Coloriage

Il suffit de considérer un tétraèdre régulier d’arête d. Vu qu’on ne dispose que de trois couleurs et que le tétraèdre possède quatre sommets, deux au moins des quatre sommets seront de la même couleur.

Points à coordonnées entières

Non, ce n’est pas possible et l’un au moins des dix milieux est nécessairement à coordonnées entières.

En effet, les points du plan qui sont à coordonnées entières peuvent être répartis en quatre catégories, selon la parité de leurs coordonnées :

• Catégorie 1 : abscisse paire et ordonnées paire
• Catégorie 2 : abscisse paire et ordonnées impaire
• Catégorie 3 : abscisse impaire et ordonnées paire
• Catégorie 4 : abscisse impaire et ordonnées impaire

Etant donnés qu’il y a cinq points rouges et quatre catégories, l’une des catégorie comporte (au moins) deux d’entre-eux, d’après le principe des tiroirs. Le milieu de ces deux points est alors à coordonnées entières (car la somme de deux entiers de même parité est paire).

On peut formuler un énoncé analogue dans l’espace : sauriez-vous trouver le nombre minimal $N$ de points (à coordonnées entières) à considérer pour qu’on soit sûr que, parmi les $\binom{N}{2}$ milieux, l’un au moins soit à coordonnées entières ?

Multi-Jackpot

Avec le langage Python, on peut définir la fonction suivante :

def cherche(d):
  if d % 2 == 0 or d % 5 ==0:
    print (d, "n'est pas premier avec 10")
    return
  n = 1
  m = 7
  while not m % d == 0:
    n += 1
    m = 10 * m + 7
  return n

Cette fonction renvoie $N_d=$ le plus petit entier $n\geqslant1$ pour lequel $A_{n}$ (cf. notations de la section 5) est multiple de $d$ (ou bien affiche un message d’erreur si jamais $d$ n’est pas premier avec $10).$ On trouve ainsi que :

$\boxed{N_{37}=3\qquad N_{31}=15\qquad N_{29}=28}$

Pour information :

$A_3=777=37\times21$

$A_{15}=777\thinspace777\thinspace777\thinspace777\thinspace777=31\times25\thinspace089\thinspace605\thinspace734\thinspace767$

$A_{28}=7\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777=29\times268\thinspace199\thinspace233\thinspace716\thinspace475\thinspace095\thinspace785\thinspace440\thinspace613$

Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.

Partager cet article

Cet article a 3 commentaires

Oncle Junior 21 Août 2022 Répondre

Je vous en prie, c’est bien le minimum que je puisse faire 😊
Oncle Junior 21 Août 2022 Répondre

Bonsoir,
Merci pour ce très bel article.

J’ai relevé quelques micro-coquilles (sauf erreur de ma part bien sûr!) :
– Partie 4 question 1 : (…) il s’en trouvera certainement deux ayant pour somme « 2n+1 » au lieu de 2n ;
– Partie 7 dans le corollaire qui suit le théorème de Dirichlet : (…) il existe une infinité de « rationnels » au lieu d’irrationnels ;
– Partie 8 dans l’énoncé du théorème de Ramsey : il me semble qu’il est nécessaire d’ajouter que le sous-graphe mentionné est infini.
Puis juste en-dessous, à la deuxième ligne qui suit les cas rouge vert bleu, on peut remplacer « monotone » par « monochrome » et ajouter « infini » ;
– Tout à la fin de l’article, dans l’encadré violet à la fin des réponses, il est peut-être plus clair de renommer les trois quantités. Par exemple D37 à la place de A37, puisque les An sont déjà définis par ailleurs.

Bien à vous.
1. René Adad 21 Août 2022 Répondre
  
  Un grand merci pour votre lecture attentive. Vous êtes bien aimable de qualifier de « micro-coquilles » les erreurs que vous avez débusquées ! J’ai effectué les mises à jour qui s’imposaient et j’en ai profité pour éliminer encore une erreur qui traînait à la section 5 : la bonne formule (*) est $A_j-A_i=10^i\,A_{j-i}$ . Comme quoi, on a beau se relire …
  Je vous suis donc très reconnaissant de m’avoir signalé ces anomalies et je dois dire que c’est un peu navrant qu’elles aient pu rester là près de quatre ans, sans que personne ne les déniche !