Le principe des tiroirs

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

Pourtant, cette propriété permet d’établir des résultats qui sont parfois 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é :

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 des tiroirs contiendra au moins 2 objets.

 

En anglais, on utilise la terminologie de pigeonhole principle (“principe des nichoirs”). Une version plus “british” de cet énoncé pourrait donc être :

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 légèrement améliorée du principe des tiroirs :
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\times333=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, si l’on répartit n objets en q classes, alors l’une des classes doit comporter au minimum {\displaystyle \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 peut ê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 l’article sur les coefficients binomiaux).

 
Et maintenant, posons-nous la question : 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 nombres :

    \[ S_{1}=a_{1},\quad S_{2}=a_{1}+a_{2},\quad\text{etc ...}\quad S_{n}=a_{1}+\cdots+a_{n} \]

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

Et sinon, cela signifie que pour chaque i\in\left\{ 1,\cdots,n\right\} , le reste de la division de S_{i} par n appartient à \left\{ 1,\cdots,n-1\right\} .

Oui, mais voilà : nous avons n restes et seulement n-1 valeurs possibles pour ces restes, d’où fatalement deux restes égaux !

Ainsi, il existe i,j\in\left\{ 1,\cdots,n\right\} 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,\cdots,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..

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 \left\{ 1,\cdots,2n\right\} 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\left\{ 1,2,\cdots,2n\right\} 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\left\{ 1,\cdots,2n+2\right\} tel que \textrm{Card }\left(X\right)=n+2.

\rightarrow Si aucun des entiers 2n+1 et 2n+2 n’appartient à X, alors X\subset\left\{ 1,\cdots,2n\right\} et l’hypothèse de récurrence s’applique à X privé de l’un quelconque de ses éléments.

\rightarrow 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.

\rightarrow 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

 
Nous noterons A_{n} le nombre 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 un entier naturel Q qui n’est multiple ni de 2 ni de 5 (autrement dit : Q est “premier avec 10”).

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 \]

k est un entier. Mais il se trouve que :

({\ensuremath{\star)   \[ A_{j}-A_{i}=10^{j-i}A_{j-i}}} \]

et il en résulte que Q est un diviseur de 10^{j-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} \]

A présent, on fait intervenir un incontournable théorème d’arithmétique :

Théorème (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é, à partir de 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…

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

 

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. Et dans ce cadre, un résultat célèbre dû au mathématicien français Joseph Liouville (1809 – 1882) montre que les nombres réels algébriques sont, en un sens, “difficiles à approcher”.

Théorème (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 (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é d’irrationnels \frac{p}{q} tels que

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

C’est pour établir ce théorème que Dirichlet a introduit le “Schubfachprinzip”, qu’on appelle aujourd’hui le principe de tiroirs.

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

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\left\{ 0,\cdots,N-1\right\} 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 :

Théorème (T)

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 théorème une sous-suite monotone et bornée. Cette dernière sera croissante et majorée ou décroissante et minorée, donc convergente.

Quant au théorème (T), on peut en donner une preuve directe, mais on peut aussi le voir comme corollaire d’un important théorème de F. Ramsey :

Théorème (Ramsey)

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

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 monotone 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 théorème \left(T\right) :

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\left\{ 1,\cdots,mn+1\right\} , 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}

Pour chaque i\in\left\{ 1,\cdots,mn+1\right\} , on a par hypothèse 1\leqslant U_{i}\leqslant m et 1\leqslant D_{i}\leqslant n, d’où mn valeurs possibles pour le couple \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.

 

9 – 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 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 :

    \[ A_{37}=3\qquad A_{31}=15\qquad A_{29}=28 \]

Pour information :

    \[ 777=37\times21 \]

    \[ 777\thinspace777\thinspace777\thinspace777\thinspace777=31\times25\thinspace089\thinspace605\thinspace734\thinspace767 \]

    \[ 7\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777\thinspace777=29\times268\thinspace199\thinspace233\thinspace716\thinspace475\thinspace095\thinspace785\thinspace440\thinspace613 \]


 

Merci de m’avoir lu jusqu’au bout. Si vous avez des remarques ou des questions relatives à cet article, n’hésitez pas à poster un commentaire ou à me joindre directement via le formulaire de contact.

Partager cet article
  • 1
  •  
  •  
  •  
  •  

Laisser un commentaire

Fermer le menu