Principe des tiroirs — Les-mathematiques.net The most powerful custom community solution in the world

Principe des tiroirs

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
«1

Réponses

  • 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?)
  • Il y a au moins deux chauves en France (Barthez + un autre). L'exemple est sans intérêt.
  • 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à)
  • 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
  • Nous sommes tous cousins...
  • 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.
  • Application : Soit P un polyêdre convexe. Il existe deux faces de P ayant le même nombre d'arêtes.
  • Bonjour,

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

    \lien{http://www.les-mathematiques.net/phorum/read.php?7,309592,309593#msg-309593}
  • La solution ici:
    \lien {http://www.les-mathematiques.net/phorum/read.php?8,347697,347697#msg-347697}

    (Ne cliquez pas si vous préférez chercher)
  • 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.
  • 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.
  • 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 8-)
  • 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
  • 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$.
  • 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.
  • 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.
  • 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).
  • Bonjour,
    Pouvez-vous être plus explicite?
  • Bonjour Personne

    Je me souviens de cette réponse (dans un autre forum (:P))
    http://www.espacemath.com/clubroi.htm

    Alain
  • 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.
  • $\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é?
  • \[\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.
  • 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.
  • 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.
  • 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
  • (:D(:D(:D

    Cet énoncé n'a rien à voir avec ce que l'on appelle le principe des tiroirs ...
  • 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$.
  • 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
  • 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 :
    Serkan a écrit:
    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.
  • 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.
  • Vois avec ton prof.

    Cordialement.
  • 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 !»
  • 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.
  • 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 ? (:P)
  • Oula... Je modifie l'énoncé de ce pas, merci !
  • 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 ?
  • ????
    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 ?
  • J'ai fait un arbre, est c'que c'est correct..?
  • 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 !
  • 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 ?
  • Ne serait-ce pas plutôt un livre où il n'y aurait pas de tiroir ? :D

    Bruno
  • Oui, exact, je m'enlise dans cette exercice, je n'arrive pas a identifier si c'est une permutation, arrangement, ou combinaison... pouah !
  • 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.
  • 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.
  • 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.
  • 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 ?
  • Je ne sais plus de quoi il s'agit.
    Redonne un énoncé précis et ta façon de le traiter.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!