NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 26/12/2016

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Dénombrement

 

Débutants

Général

Principe des TIROIRS

 

Glossaire

Général

 

 

INDEX

 

Dénombrement

Débutant

Exemples

Connaissances

Nb en 00 ..01

Introduction

Divisibilité 10

Divisibilité 2n

Divisibilité n

 

Sommaire de cette page

>>> Principe

>>> Généralisé

>>> Utilisation

>>> Énigme des croix dans le carré

>>> Un peu de théorie

>>> Anglais

 

 

 

 

 

Aussi simple que cela, a priori

*    Renter 2 voitures dans quatre garages, facile! Mais 4 voitures dans deux garages, il y en aura sans doute 2 par garage.

*    Si je dois placer 4 statuettes dans 4 niches, je peux mettre chaque statuette dans sa niche. Avec une de plus, soit 5 statuettes, l'une des niches recevra deux statuettes.

*    Si je dois ranger plus de chaussettes que je n'ai de tiroirs,
alors l'un des tiroirs contiendra deux chaussettes ou plus.

*    En escalade, la règle des trois appuis est impérative pour la sécurité. Alors, c'est certain, j'aurai soit deux mains soit deux pieds en prise.

Voir Pensées & humour

 

 

 

PRINCIPE DES TIROIRS

ou principe des tiroirs de Dirichlet-Schläfli

ou principe des boîtes

ou principe du trou de pigeon

 

 

De nombreux raisonnements en combinatoire utilisent le principe des tiroirs.

 

Pas toujours aussi évident qu'il y paraît!

 

Si je place 4 outils dans 3 tiroirs,

l'un des  tiroirs contiendra

2 outils, ou peut-être plus, mais pas moins.

 

OUPS ! Je suis vraiment  débutant

Voir un exemple simple et illustré du principe des tiroirs

Voir développements complets sur ce principe des tiroirs

 

 

Anglais:  The pigeon hole principle (PHP);

Allemand: Schubfachprinzip (das Schubfach: le tiroir)

 

 

 

PRINCIPE

 

 

Si n tiroirs sont occupés par n + 1 objets

alors, il y a au moins un tiroir occupé par plus d'un objet

 

 

 

Exemples

 

n

Tiroirs ou

Trous de pigeon

n + 1

Objets ou

Pigeons

Conclusions

2 sexes : homme et femme.

3 personnes

*    2 au moins sont du même sexe.

12 mois dans l'année.

13 personnes

*    2 au moins sont nées le même mois.

  2 types de chaussures: droite et gauche.

  3 chaussures

*    Il y en a 2 droites ou 2 gauches.

  3 couleurs de chaussettes: roses, bleues et vertes.

  4 chaussettes

*    Il y a forcément 2 de la même couleur.

   Les 9 chiffres (avec 5 couples dont la somme est 10).

  6 couples de nombres

*    Il y a en a au moins 1 dont la somme est 10:
Les couples qui donnent 10 sont: {1,9} {2,8} {3,7} {4,6} {5,5}. Il y en a 5. Avec 6 couples on a forcément un de ceux-ci.

 

 

 

Extension

 

Si m objets sont placés dans n tiroirs

alors au moins un des tiroirs contient

plus de [m / n]> objets

[ ]> désignant l'arrondi à l'entier supérieur

 

 

Exemples avec n = 3 tiroirs

 

m

m/n

[m/n]>

Il y a 1 tiroir

avec  au moins

 

Illustration

 

Cas de 7 objets dans 3 tiroirs

Il y a au moins un tiroir

qui contient 3 objets

0

0

0

/

1

0,333…

1

1 objet

2

0,666…

1

"

3

1

1

"

4

1,333…

2

2 objets

5

1,666…

2

"

6

2

2

"

7

2,333…

3

3 objets

 

 

 

 

 

 

 

 

GÉNÉRALISÉ

 

Si n tiroirs sont occupés par k.n + 1 objets

alors, il y a au moins un tiroir qui contient

k + 1 objets, ou plus

k est un entier

 

Exemples

 

 

n

Tiroirs ou

Trous de pigeon

k.n + 1

Objets ou

Pigeons

Conclusions

12 mois dans l'année

25 personnes

*    3 au moins sont nées le même mois

*    k.n + 1 = 25 = 2 x 12 + 1

*    k = 2 & k + 1 = 3 personnes

*    le minimum de personnes pour être sûr que 3 sont nées le même mois est de 25

3 couleurs de chaussettes: roses, bleues et vertes

10 chaussettes

*    4 au moins sont de la même couleur

*    k.n + 1 = 10 = 3 x 3 + 1

*    k = 3 & k + 1 = 4 chaussettes

*    le minimum de chaussettes pour être sûr que 4 sont de la même couleur

 

 

 

 

UTILISATION avancée

 

Ce principe est utilisé, en particulier, pour démontrer

le théorème de Gelfond-Schneider sur les nombres transcendants.

 

Utilisé pour prouver qu'un algorithme de compression avec un certain taux de compression ne perd pas d'information.

 

Une forme particulière est utile pour résoudre les grilles de Sudoku.

 

 

 

Énigme des croix dans le carré

Parfois appelée énigme du parking

 

Voici un exemple d'application du principe des tiroirs à une énigme classique.

 

Énigme

Un carré de N x N cases. On dessine autant de croix que l'on veut dans ce carré.

Affirmation: il existe au moins un cas où deux lignes ou deux colonnes ou une ligne et une colonne possèdent la même quantité de croix.

 

Exemple

 

Sur cet exemple particulier, les lignes sont différentes, les colonnes sont différentes. Très bien! Mais il existe six couples de lignes et colonnes avec même quantité de croix.

 

Solution

Dans une ligne, on peut placer: 0, 1, 2, … N croix, soit N + 1 possibilités.

Considérons que chaque possibilité est un tiroir.

 

La première ligne compte une croix, elle rentre dans le tiroir 1.

La deuxième ligne compte deux croix, elle rentre dans le tiroir 2.

Etc. et même chose pour les colonnes.

 

Bilan: je dois ranger N lignes puis N colonnes dans N+1 tiroirs.

 

Il y a bien plus de choses à ranger (2N) que de tiroirs (N+1), alors, un des tiroirs contiendra au moins deux lignes ou colonnes.

 

 

Voir Carrés magiques

 

 

Un peu de théorie

 

Un lemme évident: soit deux ensembles finis A et B:

*    il existe une bijection f : A  B si et seulement si n(A) = n(B);

*    c'est-à-dire si les deux ensembles ont le même cardinal;

*    et plus simplement dit: on peut associer un à un les éléments de deux ensembles s'ils ont la même quantité d'éléments;

*    ou encore, comme dirait la fermière: je peux les ranger s'il y a autant d'œufs que d'alvéoles de rangement.

Un élément (un œuf) de plus et, il faut forcément le mettre là où il y en a déjà un.

 

Théorème

Si n objets sont placés dans k boites, alors il y a au moins une boite qui contient au moins q objets, avec :

q égal à la valeur plafond de n divisé par k.

 

Exemple classique

Dans tout groupe de 367 personnes, au moins deux personnes sont né le même jour de l'année.

 

Théorème généralisé

Plaçons au hasard n objets dans m boites. La probabilité de placer un objet dans une boite est de 1/m. Alors, au moins une boite contiendra plus d'un objet avec une probabilité:

 

Exemple des anniversaires

Quelle est la probabilité d'avoir la même date d'anniversaire parmi 10 personnes

On retrouve évidemment le passage à 50% avec 23 personnes (valeur exacte: 22,7677 …).

 

 

 

 

English corner

 

The pigeonhole principle states that if there are more pigeons than there are roosts (pigeonholes), for at least one pigeonhole, more than two pigeons must be in it. This is a fundamental tool of elementary discrete mathematics. It is also known as the Dirichlet Drawer Principle.

 

Pigeonhole Principle

If k + 1 or more objects are placed into k boxes, then there is at least one box containing two or more objects.

 

 

 

 

 

 

Suite

*    Principe des tiroirsExemples

*    Sudoku et les tiroirs

Retour

*    Principe des tiroirsDébutants

*    Outils (principes additifs, multiplicatif …)

*    CombinatoireRubriques

*    D'un coup d'œil

Voir

*    Cartes

*    Compter les nombres

*    Dés

*    Dominos

*    Échecs

*    Factorielle et ses cousines

*    Grenouilles

*    Inventaire des outils mathématiques

*    Jeux

*    Probabilités

*    Triangle de Pascal

Cette page

http://villemin.gerard.free.fr/Denombre/CombTiro.htm