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

コンウェイ集合

$$ \begin{split} 6 &= 2 + 2+2\ &(a=8) \\ \rhd 7 &= 2 + 2+ 3\ &(a=12) \\ \rhd 8 &= 2 + 2 + 2 + 2\ &(a=16) \\ \rhd 8 &= 2 + 2+ 4\ &(a=16) \\ \rhd 8 &= 2 + 3 + 3\ &(a=18) \\ \rhd 9 &= 2 + 2 + 2 + 3\ &(a=24) \\ 9 &= 2 + 2 + 5\ &(a=20) \\ \rhd 9 &= 2 + 3 + 4\ &(a=24) \\ 9 &= 3 + 3 + 3\ &(a=27) \\ \rhd 10 &= 2 + 2 + 2 + 2 + 2\ &(a=32) \\ \rhd 10 &= 2 + 2 + 2+ 4\ &(a=32) \\ \rhd 10 &= 2 + 2 + 3 + 3\ &(a=36) \\ \rhd 10 &= 2 + 2+ 6\ &(a=24) \\ \rhd 10 &= 2+3 + 5\ &(a=30) \\ \rhd 10 &= 2+4+4\ &(a=32) \\ \rhd 10 &= 3 + 3+ 4\ &(a=36) \\ \rhd 11 &= 2 + 2 + 2 + 2+ 3\ &(a=48) \\ 11 &= 2 + 2 + 2 + 5\ &(a=40) \\ \rhd 11 &= 2 + 2+ 3 + 4\ &(a=48) \\ \rhd 11 &= 2+3 + 3 + 3\ &(a=54) \\ 11 &= 2 + 2 + 7\ &(a=28) \\ \rhd 11 &= 2+3 + 6\ &(a=36) \\ 11 &= 2+4 + 5\ &(a=40) \\ 11 &= 3 + 3 + 5\ &(a=45) \\ \rhd 11 &= 3 + 4 + 4\ &(a=48) \\ 12 &= 2 + 2 + 2 + 2 + 2 + 2\ &(a=64) \\ 12 &= 2+2+2+2+4\ &(a=64) \\ 12 &= 2+2+2+3+3\ &(a=72) \\ \rhd 12 &=2+2+2+6\ &(a=48) \\ 12 &=2+2+3+5\ &(a=60) \\ 12 &= 2+2+4+4\ &(a=64) \\ 12 &=2+3+3+4\ &(a=72) \\ 12 &= 3+3+3+3\ &(a=81) \\ \rhd 12 &=2+2+8\ & (a=32) \\ 12 &=2+3+7\ &(a=42) \\ \rhd 12 &=2+4+6\ &(a=48) \\ 12 &= 2+5+5\ &(a=50) \\ \rhd 12 &= 3+3+6\ &(a=54) \\ 12 &=3+4+5\ &(a=60) \\ 12 &=4+4+4\ &(a=64)\end{split} $$

 

 

$$\begin{split}2 &= 2\ &(a=2) \\ 3 &= 3\ &(a=3) \\ \ldots \\ 11 &= 11\ &(a=11) \\ 4 &= 2+2\ & (a=4) \\ \rhd 5 &= 2+3\ &(a=6) \\ \rhd 6 &= 3+3\ &(a=9) \\ \rhd 6 &= 2+4\ &(a=8) \\ \rhd 7 &= 3+4\ &(a=12) \\ \rhd 7 &= 2+5\ &(a=10) \\ \rhd 8 &= 4+4\ &(a=16) \\ 8 &=3+5\ &(a=15) \\ \rhd 8 &= 2+6\ &(a=12) \\ 9 &= 4+5\ &(a=20) \\ \rhd 9 &=3+6\ &(a=18) \\ 9 &= 2+7\ &(a=14) \\ 10 &= 5+5\ &(a=25) \\ \rhd 10 &=4+6\ &(a=24) \\ 10 &=3+7\ &(a=21) \\ \rhd 10 &=2+8\ &(a=16) \\ \rhd 11 &=5+6\ &(a=30) \\ 11 &=4+7\ &(a=28) \\ \rhd 11 &=3+8\ &(a=24) \\ \rhd 11 &=2+9\ &(a=18)\end{split}
$$

 

 

$$\begin{split} \rhd 5 &= 2 + 3\ &(a=6) \\ \rhd 6 &= 6\ &(a=6) \\ \\ \rhd 6 &= 2 + 2 + 2 = 2 + 4\ &(a=8) \\ \rhd 8 &= 8\ &(a=8) \\ \\ \rhd 6 &= 3 + 3\ &(a=9) \\ \rhd 9 &= 9\ &(a=9) \\ \\ \rhd 7 &= 2 + 5\ &(a=10) \\ \rhd 10 &= 10\ &(a=10) \\ \\ \rhd 7 &= 2 + 2 + 3 = 3 + 4\ &(a=12) \\ \rhd 8 &= 2 + 6\ &(a=12) \\ \\ \rhd 8 &= 2 + 2 + 2 + 2 = 2 + 2+ 4 = 4 + 4\ &(a=16) \\ \rhd 10 &= 2+8\ &(a=16) \\ \\ \rhd 8 &= 2+3 + 3\ &(a=18) \\ \rhd 9 &= 3 + 6\ &(a=18) \\ \rhd 11 &= 2 + 9\ &(a=18) \\ \\ \rhd 9 &= 2 + 2 + 2+ 3 = 2+3+4\ &(a=24) \\ \rhd 10 &= 2+2 + 6\ &(a=24) \\ \\ \rhd 10 &= 2+3 + 5\ &(a=30) \\ \rhd 11 &= 5 + 6\ &(a=30) \\ \\ \rhd 10 &= 2 + 2 + 2 + 2 + 2 = 2 + 2 + 2+ 4 = 2+4 + 4\ &(a=32) \\ \rhd 12 &= 2+2 + 8\ &(a=32) \\ \\ \rhd 10 &= 2 + 2+ 3 + 3 = 3 + 3 + 4\ &(a=36) \\ \rhd 11 &= 2+3 + 6\ &(a=36) \\ \\ \rhd 11 &= 2 + 2 + 2 + 2 + 3 = 2 + 2+ 3 + 4 = 3 + 4 + 4\ &(a=48) \\ \rhd 12 &= 2 + 2 + 2 + 6 = 2+4 + 6\ &(a=48) \\ \\ \rhd 11 &= 2 + 3 + 3 + 3\ &(a=54) \\ \rhd 12 &= 3+3 + 6\ &(a=54)\end{split}
$$

 

 

$$ \begin{split} \rhd 11 &= 3+4 + 4\ &(a=48) \\ \rhd 12 &= 2+2 + 2 + 6\ &(a=48)\end{split} $$

0