Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 08-07-2024 09:03:17

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 320

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


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

#2 08-07-2024 15:27:09

bridgslam
Membre
Lieu : Rospez
Inscription : 22-11-2011
Messages : 1 320

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


"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
dix-sept moins cinq
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums