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
240 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
 
 
 
 
 

Principe des tiroirs

Envoyé par huile de vidange 
huile de vidange
Principe des tiroirs
il y a quatorze années
Bonjour, connaissez-vous des exemples simples et "spectaculaires" de l'applications du principe des tiroirs de Dirichlet?

par exemple, j'ai beaucoup apprécié la démo de l'existence d'au moins 2 personnes qui possèdent exactement le meme nombre de cheveux en France utilisant ce principe

Merci beaucoup



Edité 1 fois. La dernière correction date de il y a quatorze années et a été effectuée par michael.
ryo
Re: Principe des tiroirs [Hors math]
il y a quatorze années
je sais pas si ca répondra aux critères simples et spectaculaires mais le principe des tiroirs sert par exemple pour les approximations des réels par des rationnels et ca débouche sur l'existence des nombres transcendants (en en exhibant un, pas "à la Cantor"). Evidemment j'ai pas l'énoncé sous la main mais ca se trouve par exemple dans Rouvière ou Chambert-Loir je crois

Ah je viens de voir que le sujet titrait "hors-maths" donc tu cherches surement des exemples dans le genre de celui que tu as donné (tu montres ca comment d'ailleurs?)
Re: Principe des tiroirs [Hors math]
il y a quatorze années
Il y a au moins deux chauves en France (Barthez + un autre). L'exemple est sans intérêt.
huile de vidange
Re: Principe des tiroirs [Hors math]
il y a quatorze années
Le nombre moyen de cheveux par tete, meme pour des très chevelus est d'environ 300 000, moins de 60 millions en tout cas.

J'identifie les cheveux aux tiroirs et le nombre de français (60 millions) aux chaussettes, et comme il y a plus de français que de tiroirs (cheveux) , forcément il va avoir au moins un tiroir (cheveux) qui va contenir au moins un français (je ne sais pas si j'ai été clair là)
huile de vidange
Re: Principe des tiroirs [Hors math]
il y a quatorze années
Pour Richard, je modifie l'énoncé "comment prouver que parmi les chevelus de France, il y en a au mions 2 qui aient exactement le meme nombre de cheveux".

Petite précision, je suis lycéen, il est possible que je n'ai pas bien compris le principe quand mon prof me l' expliqué, ça m'a fasciné, alors n'hésitez pas à donner d'autres exemples à la portée d'un TS svp...si c'est possible...et à me corriger si je fais fausse route

merci
gb
Re: Principe des tiroirs [Hors math]
il y a quatorze années
avatar
Nous sommes tous cousins...
ryo
Re: Principe des tiroirs [Hors math]
il y a quatorze années
merci il me manquait l'égalité 1 personne=300000 cheveux en fait, après ca va

Je savais pas que t'étais au lycée, mon exemple du début n'est pas adapté.
Mais je peux quand meme te donner la définition d'un nombre transcendant, c'est sympathique aussi :un nombre transcendant (sur $\Q$), c'est un réel qui n'est pas racine d'un polynome à coefficients dans $\Q$

Des exemples de non transcendants , c'est facile tous les rationnels mais aussi les trucs du genre $\sqrt(2)$ qui est racine de $X^2-1$..
Des exemples de transcendants, il y a $\pi$ ou $e$ mais c'est assez dur à montrer vu qu'il faut montrer qu'il n'existe pas de polynome $P$ à coefficients dans $\Q$ tel $P(\pi)=0$

Le truc que je racontais dans mon premier post a pour but de construire des nombres transcendants (les nombres de Liouville).

je crois me souvenir que j'utilisais le principe des tiroirs dans une UE d'informatique, j'essaierais de retrouver ca et de voir si c'est pas un truc difficile.
Re: Principe des tiroirs [Hors math]
il y a quatorze années
avatar
Application : Soit P un polyêdre convexe. Il existe deux faces de P ayant le même nombre d'arêtes.
bs
Re: Principe des tiroirs
il y a quatorze années
avatar
Bonjour,

Dans chercher : "principe des tiroirs",on obtient 4 pages de "best of", rien que dans la dernière année, dont:

\lien{[www.les-mathematiques.net]}



Edité 1 fois. La dernière correction date de il y a quatorze années et a été effectuée par bs.
Re: Principe des tiroirs
il y a quatorze années
avatar
La solution ici:
\lien {[www.les-mathematiques.net]}

(Ne cliquez pas si vous préférez chercher)
Re: Principe des tiroirs
il y a quatorze années
avatar
J'ai peut-être parcouru trop vite les exemples donnés ci-dessus. Il me semble qu'il manque celui-ci :

On considère 20 cubes en pierre dont les arrêtes s'échelonnent de 1cm en 1cm à partir de 5cm. Montrer que l'on peut construire deux tas distincts de même hauteur.

L'homme n'est ni ange ni bête, et le malheur veut que qui veut faire l'ange fait la bête.
Re: Principe des tiroirs
il y a quatorze années
Il y a aussi la petite propriété sympathique selon laquelle un réel est rationnel ssi son développement en base truc (où $truc\in\N$) est périodique à partir d'un certain rang.

Il me semble qu'historiquement le premier nombre transcendant est $\sum \frac{1}{10^{n!}}$, et c'était bien une histoire d'approximation rationnelle.
ryo
Re: Principe des tiroirs
il y a quatorze années
Je ne sais pas si c'est la démo originale (je ne pense pas) mais on peut montrer que $\sum\limits_{n=1}^{+\infty} \frac{1}{10^{n!}}$ est transcendant en regardant le reste d'ordre $n$ de cette série qui est un $o(\frac{1}{n^k})$ pour $k$ un entier fixé

En effet, si on se donne $k$ un entier, $x$ un réel (sans autre hypothèse) et $(\frac{p_n}{q_n})_n$ une suite de rationnels qui est toujours différente que $x$ et telle que $|x-\frac{p_n}{q_n}|=o(\frac{1}{q_n^k})$, alors $x$ est transcendant.

La démo de ce critère peut se faire par l'absurde en se donnant $P \in \Z[X]$ annulant $x$ et de degré $k$ et en considérant la suite $u_n=q_n^kP(\frac{p_n}{q_n})$, on montre que ce truc est une suite d'entiers non nuls qui converge vers $0$ d'où la contradiction !
On vient de montrer que $x$ ne peut être algébrique de degré $k$ et $k$ est arbitraire donc...

Sauf erreur vu que je tape ça direct en latex donc ce n'est pas un gage de rigueur.
Bon, tout ça est bien éloigné de la question initiale eye rolling smiley
Brot
topologie sur les fonctions mesurables
il y a quatorze années
Bonjour, je me pose une question topopolique à la quelle je n'ai pas de réponses.
Sur l'ensemble des fonctions mesurables de [0;1] dans R (pour la mesure de Lebesgue) peut-on trouver une topologie dont les suites convergentes soient exactement les suites qui convergent presque partout.
Je pense que c'est faux mais je n'arrive pas à le démontrer. Si quelqu'un a une idée ou une référence ce serait cool.

ps : désolé pour les fautes d'orthographe



Edité 1 fois. La dernière correction date de il y a quatorze années et a été effectuée par AD.
Re: topologie sur les fonctions mesurables
il y a quatorze années
1°) C'est (presque) vrai : l'application $d$ définie par
$$d(f,g):=\int_{[0,1]} \frac{|f(x)-g(x)|}{1+|f(x)-g(x)|}dx$$
définit bien une distance sur les fonctions mesurables. Si $f_n$ converge presque partout vers $g$, on a bien $d(f_n,g)\to0$. Réciproquement, si $d(f_n,g)\to0$, de toute sous-suite $(f_{\phi(n)})_n$, on peut extraire une nouvelle sous-suite $(f_{\phi\circ\psi(n)})_n$ qui converge presque partout vers $g$.


2°) C'est (vraiment) faux, en gros justement parce qu'on ne peut pas faire mieux que ce qui précède. En effet:
- a) Dans un espace métrique, on a équivalence entre :
(*) - $f_n\to g$
(**) - de toute suite extraire $f_{\phi(n)}$, on peut extraire une sous-suite $f_{\phi(\psi(n))}$ convergeant vers $g$.

- b) (**) n'implique pas (*) pour la convergence presque partout. Un contre exemple classique est le suivant: pour $n=2^k+p$ avec $0\le p<2^k$ ($k$ et $p$ existent et sont uniques, donc définissent des fonctions de la variable entière $n$), on pose
$$f_n=1_{[p2^{-k},(p+1)2^{-k}[}$$
$f_n$ vérifie (**) avec $g=0$, mais ne converge en aucun point vers $0$.
JONAS BROTHERS
Re: Principe des tiroirs [Hors math]
il y a douze années
Pourriez-vous m'aider à un exercice c'est les 300 tiroirs :
Trois cent personnes font la queue devant un bloc de trois cents tiroirs fermés numérotés de un à trois cent
1 la première pers ouvre tous les tiroirs
2 la 2 ferme tous les tiroirs qui portent un numéro pair
3 la 3 s'intéresse aux tiroirs dont les numéro sont des multiples de 3 : si un tel tiroir est ouvert elle le ferme, si il est fermé elle l'ouvre
4 la 4 s'intéresse aux tiroirs dont les numéro sont des multiples de 4 : pareille que la 3
5 s'intéresse aux tiroirs dont les numéro sont des multiples de 5
ET ainsi de suite jusqu'à 300 personnes.
Combien y a-t-il de tiroirs ouvert et quels sont-ils ?
Merci de répondre car c'est pour vendredi.
ev
Re: Principe des tiroirs [Hors math]
il y a douze années
avatar
Bonsoir JONAS BROTHERS.

Tu as deux points de vue (disons un bon et un mauvais):
- Celui d'un tiroir.
- Celui d'une personne.
Tu peux poser $300 = n$, ce n'est pas plus compliqué.

amicalement,

e.v.
Ryuken
Re: Principe des tiroirs [Hors math]
il y a douze années
Les théorèmes de Ramsey, par ex: dans un graphe non orienté à 6 sommets, sans boucle, il y a 3 sommets reliés 2 à 2, ou il y a 3 sommets tels qu'aucun n'est relié à un autre (parmi les trois).
personne
Re: Principe des tiroirs [Hors math]
il y a douze années
Bonjour,
Pouvez-vous être plus explicite?
AD
Re: Principe des tiroirs
il y a douze années
avatar
Bonjour Personne

Je me souviens de cette réponse (dans un autre forum spinning smiley sticking its tongue out)
[www.espacemath.com]

Alain
personne
Re: Principe des tiroirs [Hors math]
il y a douze années
ev
Re: Principe des tiroirs
il y a douze années
avatar
Ce qui est amusant avec cet exercice c'est qu'il permet de démontrer que
\[\forall n\in\mathbb N^*,\; \sum_{k=1}^n \left[\dfrac nk\right] - \sqrt n \in 2\mathbb Z. \]

où $[x]$ désigne la partie entière de $x$.

amicalement,

e.v.
Ga?
Re: Principe des tiroirs
il y a douze années
$\displaystyle \forall n\in\mathbb N^*,\; \sum_{k=1}^n \left[\dfrac nk\right] - \sqrt n \in 2\mathbb Z. $

Tiens, une preuve que $\sqrt{2}$ est entier? :D

Cordialement,

*************
Pourquoi faire simple quand on peut faire compliqué?
ev
J'adoube
il y a douze années
avatar
\[\forall n\in\mathbb N^*,\; \sum_{k=1}^n \left[\dfrac nk\right] - \left[\sqrt n\right] \in 2\mathbb Z. \]

où $[x]$ désigne la partie entière de $x$.
Je regrette.

e.v.
Utilisateur anonyme
Re: Principe des tiroirs
il y a douze années
*



Edité 2 fois. La derni&egrave;re correction date de il y a huit ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par qg77.
Re: Principe des tiroirs
il y a douze années
.



Edité 3 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par borde.
vincentpasloggue
Re: Principe des tiroirs
il y a douze années
Pour les tiroirs, j'aime bien citer le théorème de Wedderburn sur les polynômes cyclotomiques. On utilise un "double tiroir" : puisqu'on a une infinité de boules qui se rangent dans un nombre fini de tiroir et donc il y a un tiroir qui contient une infinité de boules.
Re: Principe des tiroirs
il y a douze années
avatar
Je remonte le sujet,
En parcourant le livre "raisonnements divins" j'ai lu une application du principe des tiroirs à la résolution d'un problème. C'est tout simplement génial !

Soit a(0),...a(n) une suite de n+1 nombres entiers distincts ou non.
Il existe toujours deux entiers i et j positifs ou nuls tels que la somme a(i)+a(i+1)+...+a(i+j) est divisible par n.
Re: Principe des tiroirs [Hors math]
il y a neuf années
Bonjour,


J'ai un exercice à faire concernant le principe des tiroirs, sauf que l'on a jamais étudié ce principe. Pourriez vous m'aidez s'il vous plais ?
Je vous écris ci dessous le sujet:

- Déterminer le nombre de façons de ranger quatre petits livres différents dans trois grands tiroirs. ( est ce qu'il y aura au moins un des tiroirs qui va contenir plus d'un livre ?, y a t'il une formule mathématique de probabilité là dessus ? )

- Répondre à la même question pour deux livres différents dans trois grands tiroirs.

Merci de votre aide
Re: Principe des tiroirs [Hors math]
il y a neuf années
smiling bouncing smileysmiling bouncing smileysmiling bouncing smiley

Cet énoncé n'a rien à voir avec ce que l'on appelle le principe des tiroirs ...
Re: Principe des tiroirs [Hors math]
il y a neuf années
Bonjour Serkan.

Difficile de t'aider à répondre sans savoir ce que tu es supposé connaître. Une partie de tes questions est du dénombrement. Seule la question "est ce qu'il y aura au moins un des tiroirs qui va contenir plus d'un livre ?" relève du principe des tiroirs, qui est la mathématisation de "S'il y a plus de livres que de tiroirs, un des tiroirs en contiendra au moins 2", corolaire du théorème qui dit que deux ensembles finis en bijection ont le même nombre d'éléments (*).

Cordialement.

(*) pour un ensemble fini parce que en bijection avec la partie $[1;n]$ de $\mathbb N$, le nombre d'éléments est $n$.
Re: Principe des tiroirs
il y a neuf années
J'ai vue le cours sur le dénombrement. Mais ce qui m’embête dans cette exercice c'est la question suivante: est ce qu'il est possible de mettre les 4 livres dans un même tiroir, en considérant que les livres sont petits, et que les tiroirs grands ? . Il n'y aucune précision
Re: Principe des tiroirs
il y a neuf années
Ce n'est plus des maths !
Comment peut-on répondre à cette question ?

Donne-nous l'énoncé complet, qu'on comprenne. Et éventuellement le contexte (quelle formation, quel niveau,...).

Cordialement.

Edit :
Citation
Serkan
Mais ce qui m’embête dans cette exercice c'est la question suivante: est ce qu'il est possible de mettre les 4 livres dans un même tiroir,
Après réflexion, le mot suivante ne veut probablement pas dire question suivante dans l'énoncé (ce que j'avais compris), mais question que je vais poser. Donc question de Serkan.



Edité 1 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par gerard0.
Re: Principe des tiroirs
il y a neuf années
Justement, l'énoncé complet est celui dont j'ai écris ! il n'y a aucune autres information. Je suis en 2eme année de BTS en Comptabilité et Gestion des Organisations.
Re: Principe des tiroirs
il y a neuf années
Vois avec ton prof.

Cordialement.
Re: Principe des tiroirs
il y a neuf années
La question n'est peut-être pas très bien formulée, mais je pense qu'on peut l'interprété de la manière suivante :

(livres petits et tiroirs grands) = on a le droit de mettre autant de livre que l'on veut dans n'importe quel tiroir. Ceci étant sans doute précisé pour éviter les : «Mais monsieur, dans mon tiroir je n'arrive pas à mettre plus de 2 livres moi !»
Re: Principe des tiroirs
il y a neuf années
Petit exercice pas spécialement impressionnant mais sympathique :)

On peint l'espace en trois couleurs. D une longueur, montrer qu'il existe au moins deux points distants de D qui soient de la même couleur.



Edité 1 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par MPPLF.
Re: Principe des tiroirs
il y a neuf années
avatar
Fastoche, je prends 2 points distants de D... et hop ils sont distants de D.

Mais alors pourquoi perdre son temps avec 3 pots de peinture ? spinning smiley sticking its tongue out
Re: Principe des tiroirs
il y a neuf années
Oula... Je modifie l'énoncé de ce pas, merci !
Re: Principe des tiroirs
il y a neuf années
Bonjour,

Je pense que cette fois j'ai trouvé la solution ! (grâce au détail que mon prof. m'a donné)

a) Déterminer le nombre de façons de rangers 4 petits livres différents dans 3 grands tiroirs.

Réponse: arrangement avec n=4 et p=3 soit A3.4= 24 façons de ranger ces 4 petits livres dans 3 grands tiroirs.

b) Réponde à la même question pour 2 livres différents dans 3 grands tiroirs

Réponse: arrangement avec n=3 et p=2 soit A2.3= 6 façons de ranger les 2 livres dans 3 grands tiroirs

N.B.: chaque tiroir ne peut recevoir qu'un seul livre

Est ce que c'est correct ?
Re: Principe des tiroirs
il y a neuf années
????

Citation

N.B.: chaque tiroir ne peut recevoir qu'un seul livre
24 façons de ranger ces 4 petits livres dans 3 grands tiroirs.
Essaie !

Tu as les livres A, B, C et B et les tiroirs 1, 2 et 3. Où mets-tu chacun des livres ?
Re: Principe des tiroirs
il y a neuf années
J'ai fait un arbre, est c'que c'est correct..?
Re: Principe des tiroirs
il y a neuf années
Donne un exemple de ces 4 livres rangés dans 3 tiroirs de façon qu'il y ait au plus un livre par tiroir :
Le livre A dans le tiroir ..
Le livre B dans le tiroir ..
Le livre C dans le tiroir ..
Le livre D dans le tiroir ..

Je n'ai fait que lire ce que tu as écrit !
Re: Principe des tiroirs
il y a neuf années
Oui, on auras donc un tiroir ou il n'y aurais pas de livre, si on prend en compte le nombre de façon de ranger 3 livres dans 3 tiroirs, cela nous feras

3!= 3x2x1=6 puis pour le 4eme on fait comment ..? 3!x3 ?
Re: Principe des tiroirs
il y a neuf années
avatar
Ne serait-ce pas plutôt un livre où il n'y aurait pas de tiroir ? :D

Bruno
Re: Principe des tiroirs
il y a neuf années
Oui, exact, je m'enlise dans cette exercice, je n'arrive pas a identifier si c'est une permutation, arrangement, ou combinaison... pouah !
Re: Principe des tiroirs
il y a neuf années
Bon j'essaie de reprendre du début. L'énoncé est :
1- Déterminer le nombre de façons de ranger quatre petits livres différents dans trois grands tiroirs.
2- Répondre à la même question pour deux livres différents dans trois grands tiroirs.

On est d'accord . Et aussi sur le fait qu'on peut ranger plusieurs livres, éventuellement tous dans le même tiroir, quel que soit le tiroir.

Dans ce cas :
1- On fait la liste des livres, et on attribue à chacun un numéro de tiroir, celui où il sera rangé. Donc on fabrique une liste ordonnée de numéros de tiroirs, avec répétition possible. Le nombre de ces listes est ..
2 - pas de changement, sauf que la liste n'a que deux termes.

Cordialement.

A noter qu'il n'y a rien à voir avec le principe des tiroirs dans cet exercice, comme le disait du début Eric (qui avait mieux décodé le message initial que moi).. Rien non plus avec le forum logique, puisque c'est du dénombrement.



Edité 1 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par gerard0.
Re: Principe des tiroirs
il y a neuf années
Justement la condition que mon prof. m'a donné c'est qu'on a : "chaque tiroir ne peut recevoir qu'un seul livre"

Mais sinon dans le cas que vous aviez cité, ce seras une "p liste" (j'ai appris cela comme ça) avec 4^3= 64, mais le problème est que chaque tiroir ne peut recevoir qu'un seul livre. Il y aura donc un livre qui ne sera pas dans un tiroir.



Edité 1 fois. La derni&egrave;re correction date de il y a neuf ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: Principe des tiroirs
il y a neuf années
C'est idiot ! Si un grand tiroir ne peut recevoir qu'un seul petit livre c'est que le tiroir n'est pas "grand" !

Bon, inutile de continuer. Si c'est un exercice pour la classe, tu verras la correction avec ton prof. De l'exercice qu'il voulait donner, puisque cet énoncé n'a pas de sens.

Cordialement.
Re: Principe des tiroirs
il y a neuf années
Je suis d'accord avec vous. Si on prenais la condition suivante: un tiroir doit contenir au moins un livre, dans ce cas ce seras la solution que j'ai donné au dessus ?
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: 145 937, Messages: 1 455 648, Utilisateurs: 27 459.
Notre dernier utilisateur inscrit LancelotCMoi.


Ce forum
Discussions: 2 412, Messages: 48 637.

 

 
©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