Le principe des tiroirs

Placez plus d'objets que de boîtes dans ces boîtes, et l'une d'elles en contiendra deux. C'est là tout le principe. Le vrai talent consiste à bien choisir ses boîtes. Voici trois problèmes où elles sont cachées : choisissez les nombres ou colorez les liens vous-même, et la page vous montrera quelle boîte a débordé.

Exemple résolu — Le principe des tiroirs

Nombres face aux boîtes	une collision est forcée
Boîte en contenant deux	5 \| 10
boîte 9	9
boîte 11	11
boîte 13	13
boîte 15	15

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Le principe des tiroirs

Le principe des tiroirs : si N objets sont placés dans k boîtes et que N > k, une boîte en contient au moins deux. Plus précisément, une boîte contient au moins ⌈N/k⌉, le plus petit nombre entier supérieur ou égal à N/k.

Ce que signifie chaque symbole

N: le nombre d'objets placés
k: le nombre de boîtes
⌈N/k⌉: N/k arrondi à l'entier supérieur : le minimum que la boîte la plus remplie doit contenir

D’où vient la formule

Pourquoi ⌈N/k⌉. Si chaque boîte contenait moins de N/k objets, les k boîtes ensemble contiendraient moins de k × N/k = N objets. Pourtant, elles contiennent la totalité des N objets. Une boîte en contient donc au moins N/k. Puisqu'elle renferme un nombre entier d'objets, c'est au moins ⌈N/k⌉. Cinq liens en deux couleurs donnent ⌈5/2⌉ = 3 liens d'une couleur ; seize liens en trois couleurs donnent ⌈16/3⌉ = 6.
Choisir les boîtes pour les diviseurs. Chaque nombre entier s'écrit, d'une seule façon, comme un nombre impair multiplié par une puissance de 2, m × 2ᵃ. Placez-le dans la boîte m. Deux nombres dans une même boîte sont m × 2ᵃ et m × 2ᵇ avec a < b, et le premier divise le second. Les nombres impairs de 1 à 2n sont 1, 3, …, 2n − 1, ce qui fait n boîtes. Ainsi, n + 1 choix forcent deux nombres dans une seule boîte. La limite est exacte : n + 1, …, 2n représentent n nombres, un par boîte, et aucun n'en divise un autre. Doubler le plus petit d'entre eux dépasse en effet déjà 2n.
Des sommes égales aux groupes disjoints. Deux groupes différents A et B ayant la même somme peuvent partager certains nombres. Retirez les nombres partagés des deux. Chaque somme diminue de la même quantité, les sommes restent donc égales. Aucun groupe ne devient vide. Si A était entièrement inclus dans B, B aurait la plus grande somme, tous les nombres étant positifs. Il reste deux groupes disjoints, non vides et de sommes égales. C'est ce que la page dessine.

Neuf nombres de 1 à 16 : l'un en divise toujours un autre 🖖

Écrivez chaque nombre comme un nombre impair multiplié par une puissance de 2 : 12 = 3 × 4, 10 = 5 × 2. Les nombres ayant la même partie impaire vont dans la même boîte. Le plus petit divise le plus grand, car ils ne diffèrent que par des puissances de 2. De 1 à 16, il y a huit nombres impairs, donc huit boîtes, et neuf choix en placent deux dans une seule boîte. Appuyez sur 9 à 16 pour voir huit nombres qui s'échappent, un par boîte : seules 10 des 12 870 sélections de huit nombres y parviennent. Appuyez ensuite sur 9 à 16 et 5. Les 11 440 sélections de neuf nombres contiennent toutes une paire dont l'un divise l'autre. Les boîtes le prouvent sans avoir à en vérifier une seule.

Parmi six personnes, trois sont des amis mutuels ou trois sont des inconnus 🖖

Appuyez sur Six personnes et prenez la personne 1. Ses cinq liens sont de deux couleurs. Au moins trois partagent donc la même : disons qu'ils sont amis. Si deux de ces trois-là sont amis entre eux, ils forment avec la personne 1 trois amis mutuels. Si aucun ne l'est, ces trois personnes sont des inconnus mutuels. Dans les deux cas un triangle apparaît, et l'argument n'a jamais examiné la coloration. Cinq personnes peuvent l'éviter, avec des amis sur les côtés d'un pentagone et des inconnus sur ses diagonales. Sur les 1 024 façons de colorer les liens de cinq personnes, 12 évitent un triangle unicolore, et chacune correspond à ce pentagone dans une certaine configuration. Aucune des 32 768 façons pour six personnes n'y parvient. Greenwood et Gleason ont présenté cet argument en 1955.

Dix nombres à deux chiffres cachent toujours deux sommes égales, tout comme neuf 🖖

Appuyez sur Dix nombres. Dix nombres distincts à deux chiffres forment 2¹⁰ − 1 = 1 023 groupes non vides. L'un de ces groupes ne peut avoir pour somme qu'une valeur comprise entre 10 et 90 + 91 + … + 99 = 945, soit 936 valeurs. Deux groupes partagent donc une somme. Retirez les nombres qu'ils ont en commun : les sommes restent égales tandis que les groupes deviennent disjoints. C'était le premier problème des Olympiades internationales de mathématiques de 1972. Avec neuf nombres distincts, il y a 511 groupes pour au plus 846 sommes, et le décompte ne révèle rien. La vérité va plus loin que le simple calcul : neuf nombres dont les sommes de chaque groupe sont différentes nécessitent que l'un d'eux vaille au moins 161 (calcul de J. P. Grossman). Neuf nombres à deux chiffres entrent donc toujours en collision eux aussi. Huit peuvent s'échapper ; appuyez sur Huit qui s'échappent.

Problème entièrement résolu

Combien de personnes forcent un triangle unicolore avec trois couleurs ? 4 étapes
Chaque paire de personnes est désormais constituée d'amis, d'inconnus ou de rivaux : trois couleurs au lieu de deux. Combien de personnes garantissent que trois d'entre elles seront toutes liées par une seule couleur ?

Ouvrez ce problème dans l'outil
1. Avec deux couleurs, l'argument de la page part des liens d'une personne :
  
  $6 people : 5 links, 2 colours \Rightarrow ⌈ \frac{5}{2} ⌉ = 3 share a colour$
2. Avec trois couleurs, prenez une personne parmi 17. Ses 16 liens se répartissent en trois couleurs :
  
  $17 people : 16 links, 3 colours \Rightarrow ⌈ \frac{16}{3} ⌉ = 6 share a colour$
3. Si deux de ces six personnes sont liées par cette même couleur, elles forment avec la première personne un triangle unicolore :
  
  $a link of that colour among the 6 \Rightarrow a triangle through person 1$
4. Si aucune ne l'est, les six n'utilisent que les deux autres couleurs. La soirée de six personnes de la page garantit déjà un triangle parmi elles :
  
  $no such link \Rightarrow the 6 use 2 colours \Rightarrow a triangle, since R (3, 3) = 6$
Réponse

Dix-sept personnes suffisent toujours. Greenwood et Gleason ont montré en 1955 que seize ne le sont pas : ils ont coloré les liens de seize personnes en trois couleurs sans triangle unicolore. Avec quatre couleurs, personne ne connaît la réponse. Elle se situe entre 51 et 62.

$R (3, 3, 3) = 17; 51 \leq R (3, 3, 3, 3) \leq 62$

Parcours

Méthodes de démonstration

Références (5)

The party problem solved exactly as this page solves it, the pentagon with red sides and blue diagonals for five and one person's five links for six, and Theorem 4, three colours need exactly 17 people, which is the worked problem: R. E. Greenwood and A. M. Gleason, "Combinatorial Relations and Chromatic Graphs", Canadian Journal of Mathematics 7, 1–7 (1955).
The equal-sums problem as it was set, ten distinct two-digit numbers, with the count of 1,023 groups against sums of at most 945: 14th International Mathematical Olympiad, 1972, Problem 1; problem and solution in J. Scholes's IMO archive (Kalva).
Why nine two-digit numbers cannot escape either: nine numbers with all their subset sums different need one at least as large as 161: OEIS Foundation, "A276661: Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum", The On-Line Encyclopedia of Integer Sequences.
Three colours are settled at 17; four are not, and the answer lies between 51 and 62: OEIS Foundation, "A003323: Multicolor Ramsey numbers R(3,3,...,3), where there are n 3's", The On-Line Encyclopedia of Integer Sequences.
The principle stated and used, including its generalised form, ⌈N/k⌉ in some box: E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §15.8, The Pigeonhole Principle.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.