Calculateur du principe des tiroirs

Bienvenue sur le Calculateur du principe des tiroirs, un outil interactif qui calcule le nombre minimum d'éléments garantis de partager un contenant lors de la distribution de N éléments dans M contenants. Ce calculateur propose des visualisations animées, des preuves étape par étape, des analyses généralisées et des applications concrètes de l'un des principes les plus puissants mais les plus simples de la combinatoire et des mathématiques discrètes.

Qu'est-ce que le principe des tiroirs ?

Le Principe des tiroirs (également connu sous le nom de principe des boîtes de Dirichlet) est un argument de comptage fondamental en combinatoire. Dans sa forme la plus simple, il stipule :

Plus précisément, si N éléments sont répartis entre M contenants, au moins un contenant doit en contenir au moins \(\lceil N/M \rceil\), où \(\lceil \cdot \rceil\) désigne la fonction plafond (arrondi à l'entier supérieur).

Le principe des tiroirs généralisé

Le Principe des tiroirs généralisé étend la version de base pour déterminer combien d'éléments sont nécessaires pour garantir k éléments dans au moins un contenant :

Cela signifie que pour garantir qu'au moins un contenant a k éléments ou plus, vous avez besoin d'un total d'au moins \((k-1) \times M + 1\) éléments. Si vous avez moins d'éléments, il est possible (mais pas certain) qu'aucun contenant n'atteigne k éléments.

Comment utiliser ce calculateur

1. Entrez les éléments (N) : Saisissez le nombre total d'éléments (pigeons, chaussettes, personnes, objets) que vous distribuez.
2. Entrez les contenants (M) : Saisissez le nombre total de contenants (tiroirs, catégories, jours) disponibles.
3. Cliquez sur Calculer : Visualisez le nombre minimum garanti d'éléments par contenant, l'animation, la preuve étape par étape et l'analyse généralisée.

Comprendre les résultats

Résultat principal

• Minimum par contenant (\(\lceil N/M \rceil\)) : Le nombre minimum d'éléments qui doivent se trouver dans au moins un contenant, quelle que soit la manière dont les éléments sont répartis.

Analyse de la distribution

• Base par boîte (N ÷ M) : Nombre d'éléments que chaque contenant reçoit dans une distribution uniforme.
• Reste (N mod M) : Éléments supplémentaires qui font que certains contenants en détiennent un de plus.
• Contenants avec surplus : Combien de contenants détiennent le nombre maximum d'éléments.

Tableau généralisé

Affiche le nombre d'éléments nécessaires pour garantir k éléments dans au moins un contenant, pour diverses valeurs de k.

Applications concrètes

Problèmes classiques utilisant le principe des tiroirs

Problème 1 : Poignées de main lors d'une fête

Dans toute fête comptant 2 personnes ou plus, au moins deux personnes ont serré le même nombre de mains. Les nombres possibles de poignées de main vont de 0 à (n-1), mais 0 et (n-1) ne peuvent pas se produire simultanément, ce qui donne n personnes pour (n-1) valeurs possibles.

Problème 2 : Points dans un carré

Placez 5 points à l'intérieur d'un carré de 2×2. En divisant en 4 carrés unitaires (les contenants), au moins deux points doivent se trouver dans le même carré unitaire, ce qui les place à une distance maximale de \(\sqrt{2}\) l'un de l'autre.

Problème 3 : Somme de sous-ensembles

Parmi n'importe quels 10 entiers distincts de 1 à 100, il existe deux sous-ensembles disjoints non vides ayant la même somme. La preuve repose sur le comptage des sommes possibles de sous-ensembles par rapport au nombre de sous-ensembles non vides.

Preuve mathématique

Le principe des tiroirs est prouvé par l'absurde :

1. Supposer le contraire : Supposons que chaque contenant contient au plus \(\lceil N/M \rceil - 1\) éléments.
2. Calculer le maximum : Total des éléments \(\leq M \times (\lceil N/M \rceil - 1) < N\).
3. Contradiction : Nous avons N éléments mais nous ne pouvons en loger que moins de N, ce qui est impossible.
4. Conclusion : Au moins un contenant doit contenir \(\geq \lceil N/M \rceil\) éléments. ◼

Foire aux questions

Qu'est-ce que le principe des tiroirs ?

Le principe des tiroirs est un argument de comptage stipulant que si N éléments sont placés dans M contenants et que N > M, au moins un contenant doit contenir plus d'un élément. Plus précisément, au moins un contenant contient au moins \(\lceil N/M \rceil\) éléments.

Comment calculer le nombre minimum d'éléments par contenant ?

Utilisez la fonction plafond : \(\lceil N/M \rceil\). Cela équivaut à \(\lfloor N/M \rfloor + 1\) lorsque N n'est pas divisible par M, ou exactement \(N/M\) lorsqu'il se divise uniformément. Par exemple, 13 éléments dans 5 contenants donnent \(\lceil 13/5 \rceil = 3\).

Qu'est-ce que le principe des tiroirs généralisé ?

La version généralisée stipule que pour garantir au moins k éléments dans un contenant parmi M contenants, vous avez besoin d'au moins \((k-1) \times M + 1\) éléments. Par exemple, pour garantir 3 éléments dans l'un des 5 contenants, vous avez besoin de \((3-1) \times 5 + 1 = 11\) éléments.

Quelles sont les applications concrètes du principe des tiroirs ?

Les applications incluent : le problème des anniversaires (367 personnes garantissent un anniversaire partagé), les collisions de hachage en informatique, la démonstration des limites de compression, les conflits d'horaire, l'analyse du routage réseau, les preuves cryptographiques et de nombreux problèmes de programmation compétitive.

Quelle est la différence entre le principe des tiroirs et le problème des anniversaires ?

Le principe des tiroirs garantit une collision de manière déterministe (367 personnes doivent partager un anniversaire parmi 366 jours). Le problème des anniversaires interroge la probabilité : seulement 23 personnes donnent 50 % de chances d'un anniversaire partagé. Le principe des tiroirs fournit une certitude ; le problème des anniversaires fournit une analyse probabiliste.

Ressources supplémentaires

• Principe des tiroirs - Wikipédia
• Paradoxe des anniversaires - Wikipédia