Divisibilité

bonsoir,
tout entier s'écrit de manière unique sous la forme 2^a*(2b+1) a et b entiers naturels.
Mais ici b ne peut excéder n-1 soit n possibilités décrites par l'ensemble {0;....;n-1}
Parmi les n+1 entiers choisis 2 s'écriront 2^(a1)*(2b+1) et 2^(a2)*(2b+1)
et l'un de ces 2 entiers divisera l'autre.

Vincent.

Pour expliciter un peu .

Pour $n \in \mathbb{N}^*$ , notons $I_n = \{1;2;3;...;2n\}$ . Montrons par récurrence sur $n \in \mathbb{N}^*$ que pour toute partie à $n+1$ éléments de $I_n$ , il existe deux éléments $a$ et $b$ tels que $a$ divise $b$ .

La propriété est évidente pour $n = 1$ supposons maintenant qu'elle est vérifiée au rang $n$ et considérons $n+2$ éléments de $I_{n+1}$ . Si $n$ de ces éléments sont dans $I_n$ , l'hypothèse de récurrence permet de conclure . Sinon cela veut dire que $2n+1$ et $2n+2$ sont parmi les $n+2$ éléments choisis et les $n$ autres sont dant $I_n$ .
Alors , deux cas de figure si $n+1$ est dans la partie choisie , en prenant $n+1$ et $2n+2$ , on a nos $a$ et $b$ .
Sinon , en ajoutant enlevant $2n+1$ et $2n+2$ à notre partie et en ajoutant $n+1$ on obtient une partie à $n+1$ éléments de $I_n$ à laquelle on peut appliquer l'hypothèse de récurrence et dénicher un $a$ divisant $b$ . Si $a$ et $b$ sont différents de $n+1$ , c'est fini sinon , c'est $b$ qui est égal à $n+1$ et en revenant à la partie initiale , $a$ divise $2n+2$ . La récurrence est établie .

Domi

je crois que j' ai vu ça aussi dans proof from the book