Principe de tiroirs de Dirichlet

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
wilfriedd
Membre Naturel
Messages: 84
Enregistré le: 03 Mar 2006, 15:33

principe de tiroirs de Dirichlet

par wilfriedd » 11 Mar 2007, 23:54

Bonjour à tous.Je suis bloqué sur un exercice c'est pourquoi je viens vous demander votre aide.Merci d'avance.
Démontrez les affirmations suivantes:
a) Tout ensemble de n+1 éléments distincts de {1,2,...,2n} contient deux éléments consécutifs.
b) Tout ensemble de n+1 éléments distincts choisis dans {1,2,...,2n} contient au moin 2 entiers dont l'un divise l'autre.
Indication: tout entier s'écrit sous la forme (2i+1)2^j

PS:si vous pouviez jeter un oeil sur une question que j'ai posé cette après-midi dans la discussion intitulée "algèbre de base" ça serait sympa.



fahr451
Membre Transcendant
Messages: 5144
Enregistré le: 06 Déc 2006, 01:50

par fahr451 » 12 Mar 2007, 00:30

j ai fait plus que jeter un coup d oeil j ai répondu

jose_latino
Membre Relatif
Messages: 320
Enregistré le: 25 Juil 2006, 23:09

par jose_latino » 12 Mar 2007, 00:40

wilfriedd a écrit:Bonjour à tous.Je suis bloqué sur un exercice c'est pourquoi je viens vous demander votre aide.Merci d'avance.
Démontrez les affirmations suivantes:
a) Tout ensemble de n+1 éléments (redondant! distincts) de S={1,2,...,2n} contient deux éléments consécutifs.

Si est une partie de S à n+1 éléments. Par l'absurde,
On va essayer de faire la somme des difféences,

considère: , donc
En outre: , en conséquent: , voici la contradiction.

ShinobiNoMono
Membre Naturel
Messages: 70
Enregistré le: 18 Juin 2005, 00:34

par ShinobiNoMono » 12 Mar 2007, 01:16

Pour le 1) j'ai pensé à ça :

- D'abord, on voit que pour avoir des chances de constituer une telle liste l de nombres il faut les prendre à un écart régulier dans S={1,...,2n} de 1, car sinon on prend deux nombres qui se suivent ou alors on prend deux nombres séparés de deux autres qui ne sont pas dans L (et on aurait alors que le cardinal de S-L>n, impossible).
- Maintenant on peut remarquer que L est nécessairement constituée de nombres ayant la même parité, ce qui est donc impossible car dans S il y a n nombres pairs et autant de nombres impairs ...)

Voilà.

J'aime bien l'idée de la sommation mais pourquoi a-t-on ? On considère que 1 et 2n sont consécutifs ?


Pour le 2), i peut aller dans n tirroirs (n valeurs différentes de 0 à n-1, car le plus grand impair possible est 2n-1).
Donc il existe deux éléments a et b tels qu'ils aient "même i".
Et donc a=(2i+1)2^j et b=(2i+1)2^k, et c'est gagné !

Comme d'hab : sauf erreur -en plus il est tard- puré je vais encore somnoler en maths demain matin...

fahr451
Membre Transcendant
Messages: 5144
Enregistré le: 06 Déc 2006, 01:50

par fahr451 » 12 Mar 2007, 01:34

comme complément on peut chercher le nombre D(n,p) de parties de {1,...,n}
à p éléments sans éléments consécutifs

joli exo
formule simple

jose_latino
Membre Relatif
Messages: 320
Enregistré le: 25 Juil 2006, 23:09

par jose_latino » 12 Mar 2007, 04:39

ShinobiNoMono a écrit:J'aime bien l'idée de la sommation mais pourquoi a-t-on ? On considère que 1 et 2n sont consécutifs ?

Ce n'est pas ça, pour avoir , il suffit remarquer que: et .

ShinobiNoMono
Membre Naturel
Messages: 70
Enregistré le: 18 Juin 2005, 00:34

par ShinobiNoMono » 12 Mar 2007, 22:10

Ah oui, mince. :dodo:

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 56 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite