15パズルは、4かける4の わくに、1から 15までの コマが 入って いて、あいた 1マスを つかって ならべかえる あそびです。1880年ごろに アメリカで 大はやりしたと 言われて います［5］。

きれいに ならんだ 形から、14と 15だけを 入れかえて みます。ここから 元に もどそうと しても、できません［4］。

ためさなくても 分かる わけは、こうです。コマを 1まい 動かすと、あいた マスと その コマが 入れかわります。ばんを 白と 黒の ましかくもようにぬると、あいた マスは 1手ごとに 白と 黒を いったりきたりします。だから 元の 場所に もどって くるときは、動かした 回数が ぜんぶで ぐうすうに なります。つまり、入れかわりも ぐうすう回の つみかさねに なるのです。

14と 15の 入れかえは、たった 1回。きすうです。あいた マスを 元の 場所に もどす なら、ぐうすう回の 動きでは、きすう回の 形は 作れません。

では、この「かわらない もの」は、15パズルだけの とくべつな ものなのでしょうか。

15パズルは、4×4の枠に1から15までのコマが入り、空いた1マスを使って並べ替える遊びです。ニューヨーク州の郵便局長ノイス・チャップマンが考えたとされ、1880年に米国で大流行しました［5］［6］。

きれいに並んだ形から14と15だけを入れ替えると、そこから元の配置に戻すことはできません［4］。何手動かしても、ではなく、やる前から決まっています。

ここに、題名の問いの答えの要点があります。コマを1枚動かすのは、空きマスとそのコマの入れ替え1回にあたります。盤を市松模様に塗ると、空きマスは1手ごとに白と黒のマスを移ります。だから元の場所に戻るときの手数は偶数になります。すると、完成形と同じ場所に空きマスを戻す場合、コマどうしの入れ替えも全部で偶数回の積み重ねです。ところが、14と15だけを入れ替えた形は、入れ替え1回、つまり奇数回の形です。偶数回の操作で奇数回の形は作れないので、動かす前から「できない」と分かるのです［4］。

この「操作しても変わらない性質」が不変量です［9］。では、同じ考え方は、ほかの問題にも通用するのでしょうか。

15パズルは、4×4の盤に15枚のコマと空きマス1つを置き、空きマスに隣接するコマを滑らせて並べ替える。ニューヨーク州の郵便局長ノイス・チャップマンが考案したとされ、1874年ごろに試作、1879年12月のボストンでの発売を経て、1880年に米国で大流行した［5］［6］。

この盤では、完成形から14と15だけを入れ替えた配置が、どんな手順でも作れない［4］。その理由が、不変量である。不変量とは、ある種の操作を加えても変わらない性質を指す［9］。

では、何が変わらないのか。コマを1枚滑らせることは、16マス全体の並びにとって、空きマスとコマの入れ替え1回、すなわち奇置換1回に当たる。一方、空きマスの位置にも偶奇がある。右下隅からの縦の差と横の差の合計を距離とすると、1手動かすたびに距離は1だけ増減するので（隅から左へ1手なら0から1へ）、偶奇が入れ替わる。この二つの偶奇は、必ず同時に変わる。したがって、空きマスが元の隅に戻った時点で、並びの偶奇も元と同じ偶数でなければならない［5］。14と15だけの入れ替えは1回、つまり奇数であり、条件を満たさない［4］。

ただし、この説明は資料の要点を整理したものであり、細部の証明は論文原典に当たる必要がある。では、この発想は盤を離れても使えるのか。

チェスの ばんは、8かける 8の 64マスで、白と 黒が かわりばんこに ならんで います。この ばんの、ななめに むかいあった すみを 2つ とると、のこりは 62マスです。2マス分の ドミノを 31まい、すきまなく ならべられるでしょうか。

やって みなくても、答えが 出ます。ドミノは どこに おいても、白を 1つ、黒を 1つ おおいます。ところが、ななめの すみは 同じ 色です。とると、白と 黒の 数が 32と 30に なります［7］。

ドミノを 31まい おいても、白と 黒は 同じ 数しか おおえません。だから、ならべるのは むりです。「色の数の ちがい」が、どんなに ならべても かわらない もの なのです。

この かわらない ものが 見つかると、ほかの パズルにも つかえるのでしょうか。

8×8のチェス盤から、対角にある隅のマスを2つ取り除くと、62マスが残ります。2マス分のドミノ31枚を、すきまなく並べられるでしょうか。

ためさなくても答えが出ます。盤を白黒に塗ると、ドミノは向きや場所にかかわらず、必ず白1マスと黒1マスを覆います。ところが、対角の隅は同じ色なので、取り除くと一方の色が32マス、もう一方が30マスになります［7］。31枚のドミノは白31マス、黒31マスを覆うはずなので、敷きつめは不可能です。

この問いは、哲学者のマックス・ブラックが1946年に出したとされ、のちに数学の読み物で広く知られるようになりました［7］。

ここでの不変量は、「ドミノをいくつ置いても、覆う白と黒の数の差は変わらない」ことです。15パズルは偶奇、こちらは色の数の差で、見かけは違っても、操作の前後で変わらないものを探す点は同じです。では、立体のパズルにも同じ手が使えるのでしょうか。

8×8のチェス盤から、対角の隅を2つ取り除いた62マスに、ドミノ31枚を敷きつめられるか。この問題は、ブラックが1946年に出したとされる［7］。

解法は塗り分けである。ドミノは置き方によらず白黒1マスずつを覆う。対角の隅は同色なので、取り除くと色別のマス数が32と30に分かれる［7］。31枚で覆えるのは白31、黒31であり、この差は崩せない。ドミノの枚数や置き方をどう変えても、覆う白と黒の個数の差は常に0のままで、盤の側の差2とは一致しない。ここでの不変量は、この「覆う色の数の差」である。

注意したいのは、不変量が分かるのは「できない」ほうだけだという点である。次の章で、この限界を扱う。

ルービックキューブにも、かわらない ものが あります。たとえば、角の 部分の むきを 0、1、2と 数に して 足すと、いつも 3で わりきれる 数に なります［10］。

だから、角を 1つだけ ねじった 形は、正しい 回しかたでは 作れません。ねじって あるように 見えたら、正しい 回しかたでは なく、ばらして 組みなおした 形だと 考えられます。

正しい 回しかたで 作れる 形は、43,252,003,274,489,856,000通りで、組み立て方の 全部の 組み合わせの 12分の1です［10］。のこりの 形は、かわらない ものの きまりに あわないので、作れません。

でも、「作れない」が 分かっても、「作れる」まで 分かるのでしょうか。

ルービックキューブでも、不変量が見つかっています。角のブロックの向きを0・1・2の数で表して足すと、合計はいつも3の倍数になります。辺のブロックは、反転が偶数個ずつ起きます。2個だけの入れ替えも、正しい操作では作れません［10］。

そのため、角を1つだけねじった状態は、正しく回していては到達できません。角だけがねじれて見えるキューブは、正しい操作ではなく、ばらして組み直した形と考えられます。

正しい操作で到達できる配置は、43,252,003,274,489,856,000通りです。これは、組み立て方の全組み合わせに対する12分の1にあたります［10］。逆算すると、全組み合わせは約5.2×10²⁰通りです。

15パズルも欠けた盤もキューブも、「ためすより、変わらないものを探す」という点で共通しています。では、この方法でどこまで言えるのでしょうか。

ルービックキューブでは、角キューブの向きの合計は常に3の倍数であり、辺キューブは偶数個ずつ反転し、2個だけの入れ替えも正しい操作では不可能である［10］。したがって、角を1つだけねじった状態は、正しい操作では作れない。

到達可能な配置は43,252,003,274,489,856,000通りである。これは組み立て方の全組み合わせの12分の1にあたる。12を掛けると約5.19×10²⁰通りになる［10］。

15パズルでは偶奇、欠けた盤では色の数、キューブでは向きの和と、見かけの異なる対象で同じ構造が現れる。ただし、不変量が一致することは到達可能の十分条件ではない。では、この方法は何を保証し、何を保証しないのか。

ばんの すみを とる もんだいで、白と 黒を 1つずつ とると、どう なるでしょう。こんどは、ドミノで ぴったり ならべられると、数学者の ゴモリーが しめし、その しょうめいは 1973年に 本に なったと 言われます［8］。

「かわらない ものが 合っている」だけでは、「できる」とは 言えません。「できる」ことは、べつに たしかめなければ いけません。

15パズルでも 同じです。1879年に、ジョンソンと ストーリーという 人たちが 論文ろんぶんを 出し、「できない 形」と「できる 形」を 分けました。それで、スタートの 形の 半分は とけない ことが わかりました［5］。

さて、ここまでは「できない」ことを 見つける 話でした。ずっと 先まで 正しい ことを 見せるには、べつの 道具が いります。

先ほどの欠けた盤で、今度は色の違う2マスを取り除くと、必ずドミノで敷きつめられます。ゴモリーの証明は1973年に出版されたとされます［8］。つまり、色の数がそろっているだけで安心はできず、「できる」ことには別の証明が必要です。

15パズルでも事情は同じです。1879年にジョンソンとストーリーが論文を出し、奇置換には到達できないこと、偶置換にはすべて到達できることが示されました［5］。分担は資料で書き方が揺れるので、ここでは二人が示したとだけ書きます。その結果、スタート配置の半分は解けません［5］［6］。

不変量は、「できない」を言うのに強い道具ですが、「できる」までは保証しません。では、「ずっと先まで正しい」を言うには、何が使えるのでしょうか。

不変量が一致しても、構成が可能とは限らない。欠けた盤で色の異なる2マスを取り除くと、必ずドミノで敷きつめられることが、ゴモリーによって示され、その証明は1973年に出版されたとされる［8］。つまり、色の数の一致は必要条件であって、十分条件ではない。可能性を言うには、別の構成的な証明が要る。

15パズルでも二段階になっている。1879年にジョンソンとストーリーが『アメリカ数学雑誌』に二つの論文を発表した。ジョンソンは奇置換に到達できないこと、ストーリーは偶置換にはすべて到達できることを示したと紹介されるが、分担の記述は資料で揺れるので、二人が示したと読むにとどめる［5］。結果として、開始配置の半分が解けず、残る半分はすべて解ける。盤が2×2以上なら、偶置換がすべて解けるという構造は同じである［6］。

不変量は「不可能」を宣言する道具であり、「可能」の宣言には使えない。では、全体や無限を言い切る方法は何か。

こんどは、かぎりなく ならんだ ドミノを 考えます。ぜんぶが たおれる ことを、一つずつ たしかめるのは できません。

でも、二つの ことが 言えれば、ぜんぶが たおれます［1］。

一つめは、いちばん はじめの ドミノが たおれる こと。二つめは、どれか 1まいが たおれたら、その となりも かならず たおれる こと。これで、ずっと 先まで たおれます［2］。

この 考え方を、数学では 「すうがくてき きのうほう」と いいます。たとえば、おはじき 1こで 正方形を 作り、3こを L字に 足すと 2かける 2の 4こ、5こを 足すと 3かける 3の 9こに なります。ここまでは たしかめれば 分かりますが、この 先もずっと つづくのかは、ドミノの 考え方で しめせます。

無限に並んだドミノの列が、すべて倒れることを、一枚ずつ確かめることはできません。それでも、次の二つが言えれば、1枚目、2枚目、3枚目…と順に倒れていくので、どの番目の一枚も倒れると結論できます。

一つめは、最初の一枚が倒れること。二つめは、どれか一枚が倒れたら、次の一枚も必ず倒れること。数学的帰納法は、この二つを証明する方法で、最初の自然数で成り立つこと（基底段階）と、kで成り立てばk+1でも成り立つこと（帰納段階）を示します［1］。ドミノにたとえて説明するのは、教科書でよく見られる方法です［2］。

具体例を見ます。最初のn個の奇数の和がn²になる、という性質です。1は1、1+3は4、1+3+5は9、1+3+5+7は16で、確かに2乗の数です。これを「ずっと」成り立つと示すには、「n個の和がn²なら、次の奇数2n+1を足した和は、n²+2n+1で(n+1)²になる」と確かめます。これが「次へ渡せる」の中身です。最初の一枚と、次への連鎖。二つがそろうので、無限の先まで届きます。

では、この二つのうち一つが欠けると、どうなるのでしょうか。

無限に続く自然数全体について、すべての値で成り立つことを、一つずつ確かめるのは不可能である。数学的帰納法は、二つの有限な確認で全体を言い切る方法である。最小の自然数で成り立つこと（基底段階）と、任意の自然数kで成り立てばk+1でも成り立つこと（帰納段階）を示す［1］。ドミノの連鎖を使った説明は、教科書の定番として知られる［2］。

例として、最初のn個の奇数の和がn²であることを考える。基底段階では、n=1で和は1、1²と等しい。帰納段階では、n個の和がn²であると仮定し、次の奇数2n+1を加えると、n²+2n+1=(n+1)²となる。n=1で成り立ち、n=1の次はn=2、その次はn=3…と順に渡されるので、どの自然数nでも成り立つと結論する。この形の帰納的証明は、マウロリコが『算術二巻』（1557年執筆、1575年刊行）で行い、最初の本格的な証明と主張されている［3］。ただし、これを発明者と断定するのは避け、「最初とされる説」と読むのが妥当である。

では、二つの確認のうち、片方が崩れるとどうなるのか。

「どんな 馬の あつまりでも、ぜんぶ 同じ 色」と 言う、まちがった 話が あります。すうがくてき きのうほうに にせて 作られた 話です［2］。

どこが まちがいかと言うと、「となりに わたせる」の ところです。馬が 1頭の とき、「同じ 色」は 正しいです。次に、2頭に うつる ところで、「1頭目と 2頭目に どちらにも いる 馬が いる」と かんがえて しまいます。でも、1頭ずつ わけると、二つの グループは かさなりません［2］。

つまり、「次へ わたせる」は、うまく つながって いなければなりません。1つ ぬけると、ドミノは たおれません。

では、この やり方は、なぜ 「きのう」と よばれるのでしょうか。

「どんな馬の集まりでも、全部の馬は同じ色だ」。数学的帰納法に似せた、もっともらしい偽の証明があります［2］。

最初の「馬が1頭なら同じ色」は正しいです。問題は、n頭からn+1頭へ渡す部分です。n+1頭のうち最初のn頭と、最後のn頭を、それぞれ「同じ色」と仮定し、真ん中の馬が共通だから全部同じだと結論します。ところが、n+1=2のとき、最初の1頭の組{1}と最後の1頭の組{2}に、共通の馬がいません。「真ん中の馬」がいないので、二つの組を同じ色とつなげられず、同じ色だと渡せません［2］。

この例は、帰納段階が最初の一歩から先で、すべて成り立たなければならないことを教えてくれます。一つだけ穴があっても、ドミノは倒れません。

では、この「帰納法」という名前の意味は何でしょうか。

「すべての馬は同じ色」という有名な偽の証明は、帰納段階の欠陥を示す例である［2］。基底段階はn=1で、1頭なら当然同じ色。帰納段階では、n+1頭を最初のn頭と最後のn頭に分け、共通する馬を橋にして全体が同じ色だと結論する。

欠陥はn+1=2の場合にある。このとき部分集合は{1}と{2}で、重なりがない。共通の馬が存在しないのに、存在すると仮定している［2］。すなわち、帰納段階は基底から先の「すべてのk」で成り立たなければならず、k=1からk=2への移行が1か所崩れていれば、連鎖全体が成立しない。

この例が教えるのは、「帰納段階」が条件つきの推論であって、証明には細部の確認が必要だという点である。では、そもそもこの方法に、なぜ「帰納」という名がついたのか。

ふつうの 「きのう」は、いくつかの ためしを 見て、全体は こうだろうと 考える ことです。この 考え方だと、たまたま ためしが そろっただけかも しれません。

でも、ドミノの 考え方は ちがいます。一つめと 二つめを 数学で しっかり しめす ので、答えは かくじつです。ほんとうは 「えんえき」という ちがう 考え方の なかまと されて います［1］。

それなのに 「きのう」と つくのは、正しさが 次々と つたわって いくように 見えるから、と いわれます［1］。

この やり方を 本に 書いた 人として、1575年に 本が 出た マウロリコが、「さいしょの ほんかくてきな しょうめい」と 言われて います［3］。ただし、さいしょかどうかは、人に よって 考えが ちがいます。

「帰納」と聞くと、いくつかの例から全体を推測する方法を思い浮かべます。ところが、数学的帰納法は、自然数の構造に基づく演繹の一種とされます［1］。例が増えても全体は保証されませんが、基底と帰納の二つの段階が証明されれば、結論は確実です。

名前の由来は、命題の正しさが次々と伝わっていくように見えることです［1］。この名前をつけたのはウォリスだという説明もあります［1］。

歴史を見ると、最初のn個の奇数の和がn²になる帰納的証明は、マウロリコが1575年に刊行した『算術二巻』で行ったとされ、「最初の本格的な証明」と主張されています［3］。パスカルは『算術三角形論』で、帰納法の原理をはっきり書いたとされます［2］。刊行年は資料により1654年ごろ、1655年、1665年と揺れます。

名称には逆説がある。通常の帰納は、個別の事例から一般則を推測するため、結論は確実ではない。数学的帰納法は、例から全体を推測する帰納とは違い、純粋に自然数の構造に依存する演繹論理の一種とされる［1］。名前は、命題の正しさが次々と伝わっていく様子に由来する。ウォリスが"induction"と呼んだという説明もある［1］。

歴史面では、マウロリコが『算術二巻』（1557年執筆、1575年刊行）で、最初のn個の奇数の和がn²になることを帰納的に証明し、「最初の本格的な証明」と主張されている［3］。パスカルは『算術三角形論』で原理を明示したとされるが、年は資料により1654年ごろ（執筆）、1655年、1665年（刊行）と揺れる［2］。パスカルがマウロリコを知っていたかも資料で食い違うため、ここでは扱わない。

「最初」を誰とするかは学説であり、断定しないほうが安全である。

きょう できる こと

紙に 8かける 8の ばんを かいて、白と 黒を ぬりわけます。ななめの すみの 2マスを けします。つぎに、2マスぶんの 紙を 31まい 作って、ならべて みます。うまく いかない のは、色の 数が ちがうから、です。

つぎに、おはじきを 1こ おきます。まわりに 3こを L字に 足すと 2かける 2、さらに 5こを L字に 足すと 3かける 3の 正方形に なります。7こ足すと どうなるかも ためして みましょう。

気を つける こと

はさみを つかう ときは、おうちの 人と いっしょに します。

今日できること

紙に8×8のマスを書いて、白黒に塗り分けます。対角の隅の2マスを消し、2マス分に切った紙片31枚で敷きつめてみます。うまくいかない理由は、色の数が32と30だからだ、と確かめられます。

次に、おはじき1個の正方形から始めます。できた正方形の右と下に、次の奇数個（3個、5個、7個）をL字に並べ足すと、1個、4個、9個、16個の正方形になることを見ます。「次の奇数を足せば次の正方形になる」が、帰納段階の姿です。

気をつけること

はさみを使うときは、大人と一緒に使います。

資料を読むなら

本文に出てきた年号（1557年、1575年、1879年、1946年、1973年）を紙に書き出し、人名と線で結んでみます。どの出来事が先で、どれが後か、ならべ直すと見えてくるものがあります。

家で再現する

8×8の盤を書いて、対角の隅を2つ消し、2マス分の紙片31枚で敷きつめを試す。色の数が32と30になることを数え、不変量の考え方を確かめる。次に、おはじき1個から始め、できた正方形の右と下に次の奇数個をL字に足すと、1・4・9・16個の正方形になることを見て、帰納段階の形を手で追う。

原典に当たる

15パズルの不可能性は、ジョンソンとストーリーの1879年の二つの論文（アメリカ数学雑誌）に当たれる［5］。マウロリコの『算術二巻』とパスカルの『算術三角形論』は、年や分担が資料で揺れる点を、自分で比べると見えてくる［3］［2］。ゴモリーの結果の読み方は、ミューティレイテッド・チェスボードの解説にある［8］。

ここで使った資料は主に二次資料なので、論文の原典で確かめることを勧める。