Problème des bus infinis de l’hôtel de Hilbert
Le problème des bus infinis de l'hôtel de Hilbert demande comment attribuer des chambres lorsque des bus infinis, chacun transportant des passagers infinis, arrivent dans un hôtel complet. Trois méthodes fonctionnent : exposants premiers, entrelacement de chiffres et fonction de couplage de Cantor.
Hôtel de Hilbert bus infinis est l’un des plus frappants exercices de pensée en mathématiques. L’hôtel est déjà complet. Une ligne interminable de bus est arrivée. Chaque bus transporte un nombre infini de nouveaux passagers. Comment accueillir tout le monde sans refuser personne ?
Ce casse-tête, ancré dans les travaux de Georg Cantor sur les ensembles infinis, expose la différence entre trois types de fonctions mathématiques : injective, surjective et bijective. Chaque méthode ci-dessous vous enseigne quelque chose de différent sur le comportement de l’infini — et une méthode seule atteint une solution parfaite.
Qu’est-ce que l’hôtel de Hilbert et pourquoi les bus infinis compliquent-ils les choses ?
L’hôtel de Hilbert est un exercice de pensée où un hôtel avec un nombre infini de chambres (une pour chaque entier positif) est complètement plein, mais peut toujours accueillir plus de clients grâce à une réaffectation astucieuse. La version avec des bus infinis est plus difficile que le problème standard car elle nécessite de mapper une grille infinie à deux dimensions — chaque paire possible (bus, siège) — sur une seule ligne infinie de numéros de chambre.
Dans le cas classique d’un seul bus, vous déplacez chaque client actuel de la chambre n à la chambre 2n, libérant ainsi toutes les chambres à numéros impairs pour les nouvelles arrivées. Ce truc fonctionne pour un groupe infini dénombrable. Cela échoue lorsque vous avez une infinité de bus, chacun transportant un nombre infini de personnes, car le simple déplacement ne peut pas comprimer une infinité à deux dimensions en une dimension sans une stratégie de mappage délibérée.
Formellement, vous avez besoin d’une fonction f(bus, siège) → numéro de chambre qui est :
- Injective (un à un) : aucun passager ne partage une chambre.
- Surjective (sur) : chaque chambre est occupée.
- Bijective : les deux à la fois — un appariement parfait sans lacunes ni chevauchements.
La méthode des exposants premiers résout-elle le problème des bus infinis de l’hôtel de Hilbert ?
La méthode des exposants premiers attribue à chaque passager une chambre en utilisant la formule 2siège × 3bus, et bien qu’elle garantisse qu’aucun passager ne partage jamais une chambre, ce n’est pas une solution complète car elle laisse la plupart des chambres définitivement vides. Elle est injective mais pas surjective.
Voici comment cela fonctionne. Considérez les clients actuels comme le bus 0. Un client dans le siège s du bus b obtient le numéro de chambre 2s × 3b. Les clients originaux (bus 0) se retrouvent dans les chambres 2, 4, 8, 16, … — des puissances pures de 2. Un passager dans le siège 3 du bus 2 obtient la chambre 23 × 32 = 8 × 9 = 72.
La logique est infaillible : le théorème fondamental de l’arithmétique garantit que chaque entier positif a exactement une factorisation première. Ainsi, aucune paire différente (bus, siège) ne peut jamais produire le même produit. Les collisions sont impossibles.
Mais vérifiez la chambre 15. Sa factorisation première est 3 × 5. La formule ne produit que des nombres dont les facteurs premiers sont 2 et 3. Le premier 5 n’apparaît jamais comme base, donc la chambre 15 ne peut jamais être attribuée. Il en va de même pour chaque numéro de chambre contenant 5, 7, 11 ou tout autre premier. En pratique, une fraction négligeable des chambres est utilisée, et la capacité de l’hôtel est gaspillée à une échelle astronomique.
Point clé : Un mappage injectif évite les collisions. Cela ne garantit pas une occupation complète. L’injection et la surjection sont des propriétés indépendantes.
Comment l’entrelacement de chiffres remplit-il chaque chambre de manière séquentielle ?
L’entrelacement de chiffres — parfois appelé un chiffre d’entrelacement — remplit chaque chambre en tissant les chiffres du numéro de siège d’un passager et du numéro de bus en un seul entier, produisant une bijection en base 10 qui attribue chaque entier positif à exactement un passager et vice versa.
Prenez le siège 1234 dans le bus 0789. Complétez les deux à la même longueur et alternez leurs chiffres :
| Position | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Chiffre du bus | 0 | 7 | 8 | 9 |
| Chiffre du siège | 1 | 2 | 3 | 4 |
| Entrelacé | 01 | 72 | 83 | 94 |
Le numéro de chambre combiné est 01728394. Le processus se renverse proprement : extrayez chaque chiffre pour retrouver les numéros de bus et de siège d’origine. Aucune information n’est perdue, et chaque entier de la séquence correspond à un passager unique.
Cela résout le problème immédiat. Chaque chambre obtient un invité. Chaque invité obtient une chambre. Mais il y a une limitation cachée : la méthode est liée à la notation en base 10. Changez le système numérique et le schéma d’entrelacement doit être redessiné. C’est un truc computationnel astucieux, pas une vérité mathématique universelle. Pour une méthode qui fonctionne indépendamment de tout système numérique, vous avez besoin de la géométrie.
Dans notre expérience d’enseignement de ce matériel à Intellia Academy, les étudiants qui comprennent pourquoi l’entrelacement de chiffres dépend de la base ont tendance à saisir beaucoup plus rapidement la signification de la solution géométrique de Cantor — car ils ressentent déjà le besoin de quelque chose de plus fondamental.
Qu’est-ce que la fonction de couplage diagonale de Cantor et comment atteint-elle une bijection parfaite ?
La fonction de couplage diagonale de Cantor est un mappage géométrique qui balaie en diagonale une grille infinie à deux dimensions de coordonnées (bus, siège), attribuant à chaque point un entier positif unique dans une séquence fixe, produisant une bijection parfaite entre la grille et les nombres naturels sans dépendre d’aucune base numérique.
Visualisez chaque passager possible comme un point sur une grille. L’axe horizontal est le numéro de siège ; l’axe vertical est le numéro de bus. Chaque passager a une coordonnée (bus, siège). Le défi est de tracer un chemin à travers chaque point de cette grille infinie exactement une fois.
Le chemin de Cantor se déplace en diagonale. Il commence à (0,0), puis balaie le long des anti-diagonales :
- Diagonale 0 : (0,0) → chambre 1
- Diagonale 1 : (0,1), (1,0) → chambres 2, 3
- Diagonale 2 : (0,2), (1,1), (2,0) → chambres 4, 5, 6
- Diagonale 3 : (0,3), (1,2), (2,1), (3,0) → chambres 7, 8, 9, 10
La formule explicite pour le numéro de chambre du passager au bus b, siège s est :
chambre = ½(b + s)(b + s + 1) + b + 1
Remarquez le terme ½(b + s)(b + s + 1). C’est un nombre triangulaire — la somme des premiers (b + s) entiers positifs. Dans l’image géométrique, chaque diagonale complétée correspond à un nombre triangulaire. La formule ajoute b + 1 pour localiser la position exacte dans cette diagonale.
Essayez l’exemple travaillé de la vidéo : bus 2, siège 3.
- b + s = 5
- Partie triangulaire : ½ × 5 × 6 = 15
- Ajoutez b + 1 = 3
- Numéro de chambre : 15 + 3 = 18
Chaque entier positif apparaît exactement une fois dans cette séquence. Chaque paire (bus, siège) est mappée à exactement une chambre. C’est une bijection — la norme d’or mathématique pour apparier deux ensembles infinis de taille égale.
Quelle est la différence entre les mappages injectifs, surjectifs et bijectifs ?
Un mappage injectif est celui où aucun des deux entrées ne partage une sortie ; un mappage surjectif est celui où chaque sortie est utilisée par au moins une entrée ; un mappage bijectif satisfait les deux conditions simultanément et prouve que deux ensembles infinis ont la même cardinalité.
| Propriété | Exposants premiers | Entrelacement de chiffres | Diagonale de Cantor |
|---|---|---|---|
| Injectif (pas de collisions) | ✓ | ✓ | ✓ |
| Surjectif (pas de chambres vides) | ✗ | ✓ | ✓ |
| Bijectif (appariement parfait) | ✗ | ✓ (base-10) | ✓ (universel) |
| Indépendant de la base | ✓ | ✗ | ✓ |
Le casse-tête de l’hôtel de Hilbert rend ces définitions abstraites concrètes. Lorsque votre mappage est uniquement injectif, de vastes étendues de l’hôtel restent vides. Lorsqu’il est bijectif, chaque entier est apparié à chaque passager dans les deux sens. C’est aussi ainsi que les mathématiciens prouvent que l’ensemble de tous les nombres rationnels a la même taille que l’ensemble de tous les nombres naturels — en exhibant une bijection entre eux en utilisant exactement cet argument diagonal.
Si vous appréciez ce genre de structures de preuves logiques, vous pourriez également apprécier comment les conditions nécessaires et suffisantes apparaissent dans les preuves de carrelage de damier — un autre domaine où une condition peut sembler convaincante mais échouer à fournir une solution complète.
Comment ce sujet apparaît-il dans les compétitions mathématiques ?
Le problème des bus infinis de l’hôtel de Hilbert se connecte directement aux sujets de la combinatoire, de la théorie des ensembles et des mathématiques discrètes. Les problèmes de concours ne vous demandent que rarement de réciter la formule de Cantor, mais ils testent régulièrement si vous pouvez construire des bijections explicites, prouver qu’un mappage est ou n’est pas surjectif, et raisonner sur l’infini dénombrable.
Les apparitions courantes en compétition incluent :
- Prouver qu’une fonction entre deux ensembles infinis est une bijection.
- Montrer que ℕ × ℕ (toutes les paires de nombres naturels) est dénombrable.
- Construire une correspondance un à un explicite entre les rationnels et les entiers.
- Des problèmes qui demandent pourquoi un schéma astucieux échoue à être surjectif (une variante du piège des exposants premiers ci-dessus).
Le paradoxe de l’anniversaire est un autre résultat de probabilité où l’intuition vous induit en erreur jusqu’à ce que vous construisiez le compte combinatoire exact — la même discipline nécessaire pour vérifier si un mappage couvre vraiment tous les cas.
Au niveau olympique, la théorie de Ramsey et le raisonnement combinatoire partagent une profonde connexion avec les idées ici : les deux domaines demandent quand une structure doit émerger, et tous deux exigent des preuves soignées qu’une construction est complète plutôt que simplement suggestive.
Les étudiants préparant des olympiades peuvent explorer l’ensemble de la gamme de cours fondamentaux en économie et en mathématiques d’Intellia Academy pour développer la fluidité en écriture de preuves que les juges de compétition recherchent.
Pourquoi le résultat de Cantor sur l’infini dénombrable est-il si surprenant ?
La fonction de couplage diagonale de Cantor prouve que l’ensemble de toutes les paires de nombres naturels a exactement la même taille que l’ensemble des nombres naturels seuls, ce qui semble impossible mais est un fait mathématique rigoureux — car deux ensembles infinis ont la même cardinalité si et seulement si une bijection existe entre eux.
Ce résultat a choqué les mathématiciens du dix-neuvième siècle. Ajouter une seconde dimension d’infini à une première dimension d’infini donne toujours la même infinité — ce que Cantor a appelé ℵ₀ (aleph-nul), la cardinalité des nombres naturels. L’hôtel ne manque jamais de place, peu importe combien de bus infinis arrivent, car la grille à deux dimensions de passagers n’est prouvablement pas plus grande que la ligne à une dimension des numéros de chambre.
Qu’est-ce qui produit une infinité strictement plus grande ? Cantor a montré séparément que les nombres réels ne peuvent pas être mis en bijection avec les nombres naturels — un autre argument diagonal le prouve. Les nombres réels forment une infinité non dénombrable, ℵ₁, et aucun truc d’hôtel ne peut les accueillir. Comprendre cette frontière entre l’infini dénombrable et l’infini non dénombrable est l’une des idées les plus profondes de toutes les mathématiques et apparaît dans des problèmes avancés d’olympiade et des évaluations d’entrée à l’université.
Pour les étudiants intéressés par la façon dont ces idées se connectent à des mathématiques de compétition plus larges, la discussion sur le nombre de Ramsey R(3,3) à Intellia Academy montre un autre domaine où la pensée combinatoire sur la structure conduit à des résultats surprenants et prouvables.
Questions Fréquemment Posées
Qu’est-ce que le problème des bus infinis de l’hôtel de Hilbert ?
Il demande comment attribuer des numéros de chambre en nombres naturels à chaque passager à travers des bus infiniment nombreux, chacun transportant infiniment de personnes, lorsque l’hôtel a déjà des invités infinis. La solution nécessite une fonction qui associe chaque paire (bus, siège) à un numéro de chambre unique sans lacunes — une bijection de ℕ × ℕ à ℕ. La fonction de couplage diagonale de Cantor fournit la réponse universelle.
Pourquoi la méthode des exposants premiers échoue-t-elle à résoudre complètement le problème ?
Attribuer la chambre 2siège × 3bus est injectif — aucun passager ne partage une chambre — mais ce n’est pas surjectif. Les numéros de chambre qui contiennent un facteur premier autre que 2 ou 3 (par exemple, 5, 7, 15, 35) ne peuvent jamais être attribués. La grande majorité des chambres restent vides, donc la capacité de l’hôtel n’est pas réellement utilisée.
Comment calculer un numéro de chambre en utilisant la fonction de couplage de Cantor ?
Utilisez la formule : chambre = ½(b + s)(b + s + 1) + b + 1, où b est le numéro de bus et s est le numéro de siège. Pour le bus 2, siège 3 : b + s = 5, partie triangulaire = ½ × 5 × 6 = 15, ajoutez b + 1 = 3, donnant la chambre 18. La formule fonctionne pour toutes les valeurs d’entiers non négatifs de b et s.
Sources
- La méthode des exposants premiers 2^siège × 3^bus est injective — pas de collisions — mais laisse la plupart des chambres vides car les nombres avec des facteurs premiers autres que 2 et 3 sont inaccessibles.
- Un mappage injectif et un mappage surjectif sont des propriétés indépendantes ; une fonction peut satisfaire l'une sans satisfaire l'autre.
- L'entrelacement de chiffres atteint une bijection en tissant les chiffres de siège et de bus en un seul entier, mais la méthode dépend de la notation en base 10 et n'est pas une vérité mathématique universelle.
- La fonction de couplage diagonale de Cantor — chambre = ½(b+s)(b+s+1) + b + 1 — est une bijection géométrique indépendante de la base qui associe chaque paire (bus, siège) à un numéro de chambre unique sans lacunes.
- Le fait que ℕ × ℕ bijecte avec ℕ prouve qu'ajouter une seconde dimension d'infini ne produit pas une plus grande infinité ; les deux ensembles partagent la même cardinalité ℵ₀.
Transcription complete de la video
L'hôtel de Hilbert est déjà complet, mais une ligne infinie de bus anciens vient d'arriver, chacun transportant un nombre infini de nouveaux passagers. Pour accueillir tout le monde, nous pouvons essayer une solution algébrique en utilisant des nombres premiers. Chaque passager se voit attribuer une chambre en calculant 2 à la puissance de leur siège multiplié par 3 à la puissance de leur bus. Dans ce modèle, nous considérons les invités originaux comme le bus 0, ce qui les associe à des puissances simples de deux. Les nouvelles arrivées utilisent à la fois les valeurs de siège et de bus comme exposants pour trouver leur numéro de chambre spécifique. Étant donné que chaque entier a une factorisation première unique, aucune combinaison de siège et de bus ne produira jamais le même résultat. Les attributions de chambres ne se chevaucheront jamais. Cet état sans collision est ce que les mathématiciens appellent une application injective.
Bien que l'algèbre fonctionne, cette méthode crée un énorme problème invisible. En nous appuyant uniquement sur les nombres premiers 2 et 3, nous laissons la grande majorité de l'hôtel vide. Si nous vérifions le registre pour la chambre 15, nous constatons qu'elle n'a pas d'occupant. Le nombre 15 est le produit de 3 et 5. Comme notre formule n'utilise que des puissances de 2 et 3, le facteur premier de 5 est mathématiquement inaccessible. Ce vide n'est pas un cas isolé. Chaque numéro de chambre qui inclut un autre premier — comme 5, 7 ou 11 — reste un vide. Nous avons évité les collisions, mais nous avons gaspillé des millions de chambres. Cela prouve qu'une application injective n'est pas nécessairement surjective. Nous n'utilisons pas réellement la pleine capacité de l'hôtel.
Pour résoudre véritablement l'infini, nous devons trouver une méthode qui ne laisse aucun vide. Nous devons aller au-delà des exposants premiers. Notre deuxième tentative utilise une approche algorithmique. Nous désignons les invités actuels comme le bus 0 pour nous assurer qu'ils sont intégrés dans la nouvelle séquence de numérotation dès le départ. Nous utilisons un chiffre d'entrelacement des chiffres. Cela prend les coordonnées de siège et de bus d'un passager et les tisse physiquement en un seul entier. Si nous prenons le siège 1234 dans le bus 0789, nous empilons les nombres et alternons leurs chiffres. Le résultat est un numéro de chambre unique, 01728394. Nous pouvons inverser le processus tout aussi facilement. Extraire les chiffres alternés fait réapparaître les numéros de siège et de bus d'origine. Cette méthode remplit chaque chambre de manière séquentielle. Chaque entier correspond à un passager, et chaque passager a un entier.
Mais ce truc est lié aux règles de notre système de numération décimale. Pour trouver une vérité universelle, nous avons besoin d'une solution basée sur la géométrie pure. Nous pouvons visualiser l'infini non pas comme une chaîne de chiffres, mais comme une carte structurelle. Tout d'abord, nous plaçons les invités originaux dans des chambres qui correspondent à des nombres triangulaires. Cela remplit les chambres 1, 3, 6 et 10, créant un squelette géométrique pour notre hôtel. Les bus et les sièges infinis sont ensuite tracés sur une grille bidimensionnelle. Chaque passager possible a maintenant une coordonnée spécifique. Pour attribuer les chambres restantes, nous utilisons la fonction d'appariement diagonale de Cantor. Cette méthode balaie la grille de coordonnées, attribuant un numéro unique à chaque point dans une séquence précise. Ce chemin géométrique cible les espaces laissés vides par nos nombres triangulaires. Il associe chaque combinaison de bus et de siège à une chambre vacante, sans sauter un seul entier.
En utilisant la géométrie spatiale au lieu de trucs arithmétiques, nous créons un plan qui prend en compte chaque dimension du problème. La grille bidimensionnelle des bus et des sièges commence à se plier — elle s'effondre physiquement en une seule ligne infinie. La formule de Cantor est conçue pour mapper les passagers aux numéros de chambre exacts laissés vacants par la séquence triangulaire. À mesure que ces deux ensembles de valeurs se combinent, ils remplissent chaque entier consécutif de un à l'infini sans exception. Cet état, où chaque chambre est remplie et aucun invité n'est dupliqué, est une bijection parfaite. Cet agencement géométrique garantit que chaque passager, peu importe sa position dans la grille, a un emplacement prévisible et équilibré. Dans cette structure, l'échelle écrasante des bus et des sièges est résolue en une seule adresse calculable pour chaque individu. À travers ce prisme, les mathématiques cartographient un champ bidimensionnel entier en une seule séquence gérable.
Maintenant, essayez d'appliquer cette géométrie vous-même. Si vous utilisez la fonction d'appariement pour le bus 2, siège 3, quel est leur numéro de chambre exact ? Calculez la réponse et laissez-la dans les commentaires.