2022年4月の記事一覧

ジョン・コンウェイの魔法使い

コンスタンチン・ノップ,「クバント」«КВАНТ»No8,2020 の記事より
ただし,原文の説明は分かりにくいので,訳者が説明をすこし変えました.

ジョン・ホートン・コンウェイは著名な数学者で,組み合わせゲーム理論だけではなく,面白​​い数学への多大な貢献をしています.

パズル-------ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
■私はバスに乗っていて,2人の魔法使の会話を聞きました:

A:私には子供が何人かいて,それぞれの年齢は正の整数であり,それらの合計はこのバス番号に等しく,それらの積は私自身の年齢です.
B:面白い! もし,あなたの年齢と子供の数を教えていただければ,私は彼らの年齢を計算することができますか?
A:いいえ,できません.
B:ああ! ついにあなたの年齢がわかりました.
ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

問:  私たちの乗っていたバス番号はいくつですか?

■このパズルの背景
パズルの作者であるジョン・コンウェイが,バス内という場面を設定したのは,魔法使いAの年齢aと彼の子供の数cの他に,もう1つの変数が必要だからで,それがバス番号bです.
(a,b,c)の三つ組数は,aは魔法使いAの年齢,bはバス番号,cは魔法使いAの子供の数を表すとします.
bのバス番号は,私たちにはわかりませんが,魔法使いBにはわかっています.

魔法使いAの「いいえ,できません」という意味は,魔法使いBの知的能力に関することではなく,三つ組数(a,b,c )が完全にわかっても,子供の年齢を明確に決めることができないということです.言い換えれば,同じ総和と積を与える[子供の年齢集合]で異なるものが存在することです.そのような年齢の集合をコンウェイ集合と呼びましょう.
訳者注)条件を満たす子供の年齢集合はc組数です.はじめの三つ組数と区別するために,私は[]で表示することにしました.

このパズルがめちゃくちゃ美しいのは,何から始めればよいかわからない.アプローチが非常に難しいからです.もし,魔法使いAの年齢aが分かれば,その約数を調べて,その和のバリエーションをすべて見つけることができる.もし,バス番号bがわかれば,いろいろな方法でそれを総和に分解し,それらの積のバリエーションを求めることができる.もし,子供の数cだけ分かった場合でも,探索量はずっと少なくなる.
候補探索のプログラミングに数時間を費やし,ようやく正しい解に近づく方法を見出した人もいます.

この問題は,完全に定義されておらず,つまり,さまざまな解決策が存在するのです.

■例を示します:
21番のバス(b=21)内の会話で,魔法使いAは96歳(a=96),子供は3人(c=3)だとします.この状態を三つ組数(96, 21, 3)と書きます.
子供たちの年齢は,和が21,積が96で,この場合c=3のため,たまたまですが,[3つ組数]になります.この条件を満たす子供の年齢は,[1,8,12]と[2,3,16]の2つがあり,確かに,魔法使いBが(96,21,3)と完全な数字を知ったとしても,子供たちの具体的な年齢を割り出すことはできません.

魔法使いの会話から,条件を満たす子供の年齢が決まらないのは何故か?

同じbで異なるaを持つ数字のコンウェイ集合は他にないでしょうか?
この問いに答えるために,別の言い方をしましよう.bが小さく,aが異なるコンウェイ集合は他にないのでしょうか?なぜなら,もし見つけることができれば,それに1歳児を加えて,出来上がったコンウェイ集合の数の合計bを21になるようにすればよいからです.

[訳者注]子供の年齢集合に1歳を一人加えるとb(子どもの年齢の総和)は1つ増加しますが,積a(これは魔法使いAの年齢)は変わりません.ただし,cは1つ増加します].実際,このようなコンウェイ集合は簡単に見つかります.例えば,(40,14,3)の場合,[1, 5, 8] や [2, 2, 10] がそうで,これに1歳児を加えると[1,1,5,8]や[1,2,2,10]で(40,15,4)に対応するコンウェイ集合が得られます(この両者で,魔法使いAの年齢は40歳で変わりません).
また,(36,13,3)の場合,コンウェイ集合 [1, 6, 6] と[2, 2, 9]があり,同様の操作で[1,1,6,6]と[1,2,2,10]のコンウェイ集合が得られ,これは(36,14,4)に対応します.この両者では魔法使いAは36歳で変わりません.
この2つの例で,バス番号b=14が同じとき,魔法使いAの年齢が40と36のように異なるものが作れます.

ここから,説明は冗長になり混乱しますから,ここで一息入れましょう.ここから先は,まず,自分でトライアンドエラーしてみた方が理解が深まります.各自試みてください.要するに,この問題は,[子供の年齢の集合]で,総和と積が一致する集合(コンウェイ集合)の中身に異なるものが複数存在し,子供の具体的な年齢が決まらない場合のb(子どもの年齢の総和でバス番号)を聞いているのです.「ああ! ついにあなたの年齢がわかりました.」と言う発言があるので,そのとき,aの数値は定まらなければいけません.

0