Un hôtel infini dont les chambres sont numérotées par les entiers 0, 1, 2, 3, … est complet pour la nuit.
a) Arrive un client : « pas de problème » lui répond le responsable de l’accueil, « installez-vous dans la chambre 0, je demande au client de la chambre 0 de passer dans la chambre 1, à celui de la chambre 1 de passer dans la chambre 2, etc. » Le nouveau client peut donc être accueilli, et cela sans qu’aucun client ne soit privé de chambre.
b) Dix minutes plus tard, arrive un auto- car infini de nouveaux clients qui demandent à passer la nuit dans l’hôtel. « Pas de problème » répond le responsable de l’accueil. Il demande au client de la chambre \(n\) de passer dans la chambre \(2n.\) Il indique alors au chauffeur du car que le voyageur numéro \(i(i=0,1,2,\ldots)\) de son autocar peut disposer de la chambre \(2i + 1\) – qui est effectivement libre puisque toutes les chambres de numéro impair ont été libérées. Chaque nouvel arrivant a trouvé à se caser et aucun de ceux qui occupaient l’hôtel n’a été chassé!
c) Une demi-heure plus tard arrive un groupe plus important encore, car constitué d’une infinité d’autocars chacun ayant à son bord une infinité de passagers. Le responsable affirme qu’il peut loger tout le monde. Comment fait-il?
La réponse – proposée par plusieurs lecteurs – consiste à utiliser une bijection entre \(\mathbb{N},\) l’ensemble des entiers et \(\mathbb{N} \times \mathbb{N},\) l’ensemble des paires de nombres entiers.
Très concrètement, le responsable de l’accueil téléphone au client de la chambre \(i\) et lui demande de passer dans la chambre \(2i + 1\) (ce qui libère toutes les chambres ayant un numéro pair) et donne la consigne suivante au responsable du groupe d’autocars : le passager numéro \(i\) du bus numéro \(j\) doit se rendre dans la chambre \(2^{j + 1} (2i + 1).\) En clair :
– Les passagers du bus 0 occupent les chambres :
\[2, 6, 10, 14, 18, \ldots, 2 \times (2i + 1), \ldots\]
– Les passagers du bus 1 occupent les chambres :
\[4, 12, 20, 28, 36, \ldots, 4 \times (2i + 1), \ldots\]
– Les passagers du bus 2 occupent les chambres :
\[8, 24, 40, 56, 72, \ldots, 8 \times (2i + 1), \ldots \]
etc.
Toutes les chambres sont occupées et jamais deux voyageurs différents ne se retrouvent dans la même chambre, car :
si \(2^{i+1} (2j + 1) = 2^{i’+1} (2j’ + 1)\)
alors nécessairement \(i = i’\) et \(j = j’.\)
