無限ホテルのパラドクス

ウィキペディア

ヒルベルトの無限ホテルのパラドックス

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/12/15 09:43 UTC 版)

ヒルベルトホテル

ダフィット・ヒルベルト:「現代数学の父」と呼ばれた。

ヒルベルトの無限ホテルのパラドックス（ヒルベルトのむげんホテルのパラドックス、英: Hilbert's Infinite Hotel Paradox）とは、無限集合の非直観的な性質を説明する思考実験である。無限個の客室があるホテルは「満室」でも（無限人の）新たな客を泊めることができ、その手順を無限に繰り返せることを示す。論理的・数学的に正しいが、直観に反するという意味でのパラドックス（擬似パラドックス）である。ヒルベルトのグランドホテルのパラドックス（英: Hilbert's paradox of the Grand Hotel）、ヒルベルトホテル（英: Hilbert's Hotel）とも。1924年にダフィット・ヒルベルトが論文「Über das Unendliche（無限について）」で導入し、1947年のジョージ・ガモフの著書「1、2、3…無限大」によって広まった。

簡単のため、以下の記述では無限とは可算無限を意味するものとする。しかし選択公理を仮定すれば、任意の無限集合は可算無限集合を部分集合にもつため、非可算無限の場合でも少し議論を修正するだけでよい。

パラドックスの内容

無限個の客室があり、「満室」である仮想的なホテルを考える。客室数が有限の場合、「満室であること」と「新たに来た客を泊められないこと」は同値だが（鳩の巣原理）、無限ホテルではそうはならない。

有限人の新たな客

1人の客が来てホテルに宿泊を希望したとする。そこで1号室の客を2号室に、2号室の客を3号室に、n号室の客を(n + 1)号室に（同時に）移動させる。すると1号室は空室になり、1人の客を泊めることができる。この手順を繰り返すことで、任意の有限人の新たな客の部屋を作れる。

無限人の新たな客

無限を表す記号

また、無限人の新たな客を泊めることも可能である。1号室の客を2号室に、2号室の客を4号室に、n号室の客を2n号室に移動させれば、すべての奇数号室（可算無限個ある）が新たな客に解放される。

それぞれ無限人の客を乗せた無限台のバス

いくつかの方法で、それぞれ無限人の乗客を乗せた無限台のバスの団体客を泊めることが可能である。ほとんどの方法はバスの座席が番号付けされていること（可算選択公理）を仮定する。一般にこの問題を解くには任意の対関数が使える。それぞれの方法で、乗客の座席番号をn、乗っているバスの号車番号をcとすると、nとcが対関数の2つの引数になる。

素数冪を用いる方法

i号室の客を2ⁱ号室に移動させて奇数号室を空け、1号車の団体客を3ⁿ号室に、2号車の団体客を5ⁿ号室に、一般にc号車の団体客を、c番目の奇素数をpとして、pⁿ号室に泊める。この方法ではいくつかの客室が空室になる（それがホテルにとって有益かはともかく）。具体的には15や847などのすべての素数冪でない奇数号室は誰も泊まっていない状態になる（よって厳密な議論では、これは来客者数が最初に空けた客室数に等しいかそれより少ないことを示している。正確に合うようにアルゴリズムを修正するよりも、これとは独立に、来客者数が最初に空けた客室数に等しいかそれより多いことを示し、したがってそれらが等しいことを示す方が簡単である）（このアルゴリズムはnとcを入れ替えても成り立つが、どちらかを選んで固定し、一貫して適用しなければならない）。

素因数分解を用いる方法

座席s、号車cの乗客を2^s3^c号室に泊める（元のホテルの客はc = 0、1号車はc = 1、…とする）。すべての正の整数は一意的に素因数分解できるので（算術の基本定理）、すべての客が部屋に入り、同じ部屋に2人入らないことがわかる。たとえば2592 (2⁵3⁴) 号室の客は、4号車の5番目の席に座っていた乗客である。素数冪を用いる方法と同様に、この方法ではいくつかの客室が空室になる。

この方法は無限の夜に、無限の入り口に…などの問題に簡単に拡張できる (2^s3^c5ⁿ7^e)。

Interleaving method

それぞれの乗客について、十進法などの任意の位取り記数法で表したnとcの桁数を比較し（元のホテルの客はc = 0とする）、桁数が異なる場合、同じ桁数になるまで桁数の少ない方の先頭に0を付け加える。そして[号車番号の1桁目]-[座席番号の1桁目]-[号車番号の2桁目]-[座席番号の2桁目]-…と各桁の数字をinterleaveして部屋番号を生成する。元のホテルの（0号車の）1729号室の客は、01070209号室（すなわち1,070,209号室）に移動する。789号車の1234番目の座席の乗客は01728394号室（すなわち1,728,394号室）に入る。

素数冪を用いる方法とは異なり、この方法は客室を完全に埋め、interleaving processを逆にすることで、元の号車と座席を復元することができる。まず部屋番号が奇数桁の場合、先頭に0を追加する。すると号車番号は奇数桁目の数字からなり、座席番号は偶数桁目の数字からなる。もちろん元の符号化の方法は任意であり、一貫して適用する限り、2つの数字の役割を逆にすることができる（座席を奇数桁目にして号車を偶数桁目にする）。

三角数を用いる方法

元のホテルの客を(n² + n)/2（すなわちn番目の三角数）号室に移動する。バスの団体客を[(c + n - 1)² + (c + n - 1)]/2 + n（すなわち(c + n - 1)番目の三角数 + n）号室に泊める。これですべての客室が重複なく埋まる。

この対関数は、ホテルを1部屋分の奥行きがある無限に高いピラミッドとして構造化することでイメージできる。ピラミッドの最上段に1号室があり、次の段に2号室と3号室があり、以下同様に続く。右端の客室の集合からなる列が三角数号室に対応する。それらの客室が（元のホテルの客が移動して）埋まると、空になった部屋は元の形と厳密に等しいピラミッドの形になる。よって、この手順を各無限集合（バス）ごとに繰り返すことができる。これを1台ずつ行うには無限のステップ数が必要になるが、事前の計算式を用いることで、手順の中で自分のバスの順番が来た時点で乗客は自分の部屋が何番に「なる」か決定でき、ただちにそこに行くことができるようになる。

任意の列挙方法

$S:=\{(a,b)\mid a,b\in \mathbb {N} \}$