Forum de mathématiques - Bibm@th.net

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 901

Une récurrence à fagoter

Bonjour,

Le principe des tiroirs permet d'expédier des preuves plus vite qu'en Colissimo, comme dans cette question:

Parmi n+1 entiers non nuls ne dépassant pas 2n, on peut en extraire deux qui se divisent.

Saurez-vous en fournir aussi une preuve solide (et bien propre) par récurrence ?
Seul importe que le colis arrive à bon port, pour cette fois, donc à peu de frais mathématiques.

A

bridgslam

Membre Expert

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 901

Re : Une récurrence à fagoter

Bonjour,

Avec une récurrence, les seules connaissances exigées sont les propriétés basiques de la divisibilité
(du style a|b et b|c => a|c ,  et à part a et 0, le plus petit entier que divise a est 2a...).
La contre-partie est que c'est moins immédiat.

▼une solution élémentaire possible

Si n = 1 la partie P = { 1,2 }  est la partie pleine de {1 ,...,2n} , et 1 | 2 . La proprité est donc vraie au rang 1.
Supposons que à un rang n, la propriété soit vraie, à savoir que parmi $E_n = \{1 ,...,2n\}$, et toute partie $F_{n+1} \subset E_n$ à n+1 éléments deux éléments de $F_{n+1}$ au moins se divisent.

Considérons $E_{n+1}=\{ 1, ...,2n+1,2n+2\}$  dont une partie F possède n+2 éléments. On doit prouver qu'il existe dans F deux éléments en division.

A/ Si aucun élément de F ne dépasse 2n, en utilisant l'hypothèse de récurrence, c'est gagné
B/ Si un seul élément f de F dépasse 2n, on peut encore appliquer l'hypothèse de récurrence en considérant F\{f}, partie de n+1 entiers au plus égaux à 2n.
C/ Si deux éléments de F dépassent 2n, l'un f vaut 2n+1, l'autre f' vaut 2n+2.

    C-1/ si n+1 est dans F c'est gagné puisque n+1 | f'.
    C-2/ si n+1 n'appartient pas à F, on doit séparer deux cas:

           C-2-1/ si n+1 admet un diviseur d dans F, alors d | 2n+2 , c'est gagné.
           C-2-2/ si n+1 n'admet aucun diviseur dans F, la seule relation de divisibilité possible de n+1 avec un élément de F est donc n+1 divisant son double.
                      L'idée est donc de considérer ( $F$ \ $\{2n+2\} $ ) $ \cup \{n+1\}$,  partie qui permet de retomber sur le cas B/.
                      Et on est certain que la paire d'entiers en division ne concernera pas n+1, donc on reste dans F.

On a toujours trouvé deux entiers de F dont l'un divise l'autre.

Conclusion : la propriété est vraie pour tout entier non nul.

Je suis intéressé par d'autres exemples de preuves où comme en (C-2-2)  l'adjonction in extremis d'un "rejeton petit canard" devient nécessaire sans rien chambouler par ailleurs, sorte d'effet "tremplin"...
En gros contrecarrer l'adage "le remède est parfois pire que le mal" ?
Normalement il en existe en analyse combinatoire, mais je suis plus intéressé par des exemples en analyse.
Merci si vous en trouvez.

Alain