Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
202 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Divisibilité

Envoyé par Anselme-Olivier 
Divisibilité
il y a treize années
Bonjour,
Prouver que parmi tout ensemble de n+1 entiers choisis dans l'ensemble {1,2,3,...,2n},
il y a au moins deux entiers a et b tels que b divise a.
(Erdos)

Anselme-Olivier.
Re: Divisibilité
il y a treize années
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.
Re: Divisibilité
il y a treize années
avatar
ça marche très bien par récurrence .

Domi
Re: Divisibilité
il y a treize années
avatar
<latex> 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
Re: Divisibilité
il y a treize années
Bravo à vince, qui a produit la preuve que j'avais, et bravo à Domi pour la preuve par récurrence.

Anselme-Olivier.
Re: Divisibilité
il y a treize années
je crois que j' ai vu ça aussi dans proof from the book
Re: Divisibilité
il y a treize années
avatar
Il est vrai qu'avec un peu de réflexion la méthode de Vince n'est pas du tout artificielle et bien plus rapide ( et élégante ) que la récurrence.

Domi
Re: Divisibilité
il y a treize années
Oui, encore une jolie application du principe des tiroirs.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 139 162, Messages: 1 353 850, Utilisateurs: 25 111.
Notre dernier utilisateur inscrit Rapha.


Ce forum
Discussions: 5 169, Messages: 62 653.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page