Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
10 février 2011 4 10 /02 /février /2011 12:00

Happy Birthday! Dans une année, il y a 52 semaines. Sur un calendrier, je note le nom de mes amis Facebook dans la semaine où il se produit. Avant d'avoir placé mes 70 amis je me rends compte que j'ai déjà noté le nom de deux de mes amis dans la même semaine. En effet, arrivé au 53è ami deux cas peuvent se produire :

  1. Cas 1  : pour chaque semaine, j'ai déjà un ami dont c'est l'anniversaire. Alors le 53è ami qui a forcément son anniversaire dans l'une de ses 52 semaines a le même anniversaire que la personne déjà notée pour cette semaine.
  2. Cas 2 :  il reste une semaine où aucun ami n'a son anniversaire. Dans ce cas, mon 53è ami peut avoir son anniversaire durant cette semaine-là et je vais montrer que parmi mes 52 premiers amis, au moins d'eux d'entre eux ont leur anniversaire la même semaine.

Seul le cas 2 pose problème. Plaçons nous dans ce cas. Alors 52 amis se partagent 51 semaines pour leur anniversaire.

Occupons nous du 52è amis, deux cas sont possibles :

  1. Cas 1 : les anniversaires de mes 51 premiers amis occupent les 51 semaines qui m'intéressent et nécessairement le 52è a son anniversaire durant l'une de ces semaines et c'est fini.
  2. Cas 2 : il reste une semaine  dans les 51 où aucun ami n'a son anniversaire et comme précédemment nous sommes ramenées à la situation où les anniversaires de mes 51 amis occupent 50 semaines.

Comme précédemment, seul le cas 2 pose problème. Ici 51 amis se partagent 50 semaines pour leur anniversaire. En raisonnant de la sorte encore une fois, le seul problème événtuel est que mes 50 premiers amis aient leur anniversaire étamés sur 49 semaines.

 

Succèssivement notre problème se ramène à

  • 49 amis ont leur anniversaire sur 48 semaines, puis
  • 48 amis ont leur anniversaire sur 47 semaines
  • .....
  • 3 amis ont leur anniversaire sur 4 semaines
  • 2 amis ont leur anniversaire la même semaine.

Cette démonstration n'est pas rigoureuse car j'ai passé 44 étapes. Pour une preuve irréprochable, j'aurai du utiliser un raisonnement par récurence.

 

J'aurai pu utiliser également le principe des tiroirs de Dirichlet :

 

 

Principe des tiroirs (Schubfachprinzip) 


Si l'on dispose de n tiroirs et d'au moins n+1 objets, alors au moins un tiroir contiendra 2 objets.

Dirichlet

 

 

 

En appliquant ce principe, on voit que si je range chacun de mes amis dans le tiroir correspondant à la semaine de son anniversaire, puisque 70 est strictement plus grand que 52. Au moins deux amis auront leur anniversaire la même semaine.

 

Le démonstration du principe des tiroirs peut se faire d'une manière analogue à la démonstration précédente.

 

En utilisant un raisonnement par récurence, cela devient beaucoup plus rapide.

 

Démonstration du principe des tiroirs par récurence :

 

m étant un nombre entier naturel, on définit la propriété

P(m) : si j'ai k objets et si k est au moins égal à m+1, alors en les rangeant dans m tirois au moins deux objets seront dans le même tiroir.

 

Initialisation :

P(1) est vraie car si j'ai 2 objets à ranger dans le tiroir, le tiroir contiendra deux objets.

 

Hérédité :

Supposons que la propriété P(m) soit vraie. Prouvons P(m+1). Je dispose d'au moins m+2 objets à ranger dans (m+1) tiroirs. Je ne vais m'occuper que de m+2 objets. Considérons un parmi ces objets, disons mon préféré. Comme pour mes amis Facebook, deux cas sont possibles : 

  1. Soit tout les autres (m+1) objets sont dans un tiroir différent et mon objet préféré ne sera pas seul dans l'un de ces (m+1) tiroirs (il n'y a pas d'autre tiroirs) et c'est fini,
  2. soit il y a au moins un tiroir vide et les m objets sont rangés dans m tiroirs et peu m'importe ou je rangerai mon objet préféré.

En effet, dans le cas 2, j'utilise l'hypothèse de récurence P(m) qui dit que parmi les m tiroirs, au moins un contient au moins deux objets. Cela prouve P(m+1).

 

Conclusion : Comme P(m) implique P(m+1) (hérédité) et que P(1) est vraie (initialisation), alors la propriété P(n) est démontrée pour tout n au moin égal à un.

 


Partager cet article

Repost 0
Published by Maths_Buchwald - dans Divers
commenter cet article

commentaires

Présentation

  • : Maths Otak'
  • Maths Otak'
  • : Au départ, j'ai créé ce blog pour y publier des articles reliant Maths et histoire de l'art et la culture. Maintenant, il me permet d'aborder des sujets simples de la culture mathématique. J'aime parler de jeux vidéos. Vous trouverez aussi sur ce site des fiches de maths et Histoire des Arts de 2009-2010 au format *.pdf. Je ne sais pas où me mène ce blog donc il ne sera sans doute plus le même si je continue à l'alimenter dans un an. N'hésitez pas à laisser des commentaires.
  • Contact

Twitter

Recherche

Mes vidéos

Catégories