【小さな話題】『互いに素な2つの自然数が存在するための個数』『毒ワイン検出パズル』
最近YouTubeで視聴した数学関連動画2題のメモと考察。
- エレガントな解法もとむ 互いに素な2つの自然数が存在するための個数
おなじみの鈴木貫太郎先生の最近の動画。エレガントな解答をもとむ名作セレクション2000--2020 [プリント・レプリカ] Kindle版からの出題。「エレガントな解法もとむ」は私も高校生の頃に挑戦したことがあったがなかなかエレガントにはなれなかった。nがいくつになってもn個のベン図が作れるか？という問題に関連して投稿が紹介されたことはあったが。
さて、この問題は、以下の通り。
次の性質を満たす最小の自然数Nを求めよ。
600以下の自然数からどのN個を選んでも，その中に互いに素な2つの自然数の組が存在する。
ちょっと見ただけでは何のことか分からない問題だが、例えば600個の自然数から300個を選んだ場合、2〜600まですべて偶数が選ばれる可能性がある。この場合は互いに素な組は存在しないのでNは300ではダメであることが分かる。ではN＝301、つまり301個選べば互いに素な組が1組以上存在すると言えるのか？という問題。
ここでカギとなるのは、「隣り合う2つの自然数は、必ず互いに素になる」という定理。これは簡単に証明できる。もしnとn+1が互いに素でない場合があるとすると、共通の約数g（g>1)が存在し、n+1＝ga、n＝gbと表すことができる。ところが、左辺を引き算するとn+1-n＝1、右辺を引き算するとga-gb＝g（a-b)となるが、g(a-b)＝1となるようなg（g>1)は存在しないので、けっきょく隣り合う数はかならず互いに素となる。
そこで、Nが301の時に、どのように組を作っても決して互いに素にならないように選ぶためには、最低限、1つおきに選ぶ必要がある【「1、3、5、．．．」でも「2、4、6、．．．」でもよい】。しかしそのように選べる個数は600/2＝300個に限られる。301個目はどの数を選んでもすでに選んだ数のうちのどれかと隣り合ってしまう。これは題意を満たしているのでN＝301が正解。これは鳩ノ巣原理の応用でもある。
- 【ゆっくり解説】単純なのに難問...1本の毒ワインを見抜け！ 毒ワインのパラドックス
元の問題は、以下のように要約できる【長谷川のほうで一部改訂】。
王様のもとに1000本の高級ワインが届けられた。このうち1本にだけは毒が入っており、一口飲んだだけで24時間後に死亡する。王様は家来を集め、24時間後に1本の毒ワインを特定しろと命令した。10人の家来が毒味をすることで、毒入りワインを検出するにはどうすればよいか？
上記はいくら思考ゲームとはいえ「毒味をすることで家来の何人かが死んでしまう」という残酷な問題。もう少し穏便なクイズに言い換えができないかと思ったが、例えば、
1000枚の金貨がある。このうち1枚だけはニセ金であり重さが違っている。目盛りつきのバネばかりで10回計量することでニセ金を見つけるにはどうすればよいか？
【ここで使用するのは金貨1000枚まで計量できるバネばかりであって、天秤でニセ金を見つけるクイズとは異なる。ホンモノの金貨はすべて同じ重さとする。】
としても問題の本質は変わらないように思われるが、とりあえずオリジナルな問題の表現のままで考察を続ける。
動画で紹介されたのは、1000本のワインに0から999までの番号をつける。十進法の999は二進法では「1111100111」という10桁で表される。そして、10人の家来はその10桁それぞれの桁に割り当てられる。そしてn桁に対応する家来は、二進法でn桁目が「1」で表記されている番号のワインをすべて飲む。家来の何人かは死んでしまうが、このことから、死んだ家来に相当する桁が「1」で表されるワイン番号のワインが毒入りであると判定できる。なお、幸いにして家来が誰も死ななかった時は、0番のワインが毒入りとなる。
動画が紹介していたように、この方法を使えば、ワインが1万本に増えた場合でも毒味をしなければならない家来は14人、1億本では27人で済む。ま、現実にはこのような非人道的な毒味をすることはないが、この検出技術は、異常箇所の検出にも使えるはずだ。もっとも、上記の解法では「1つだけがクロ、残りはシロ」が大前提となっている。クロが2つ以上の場合は同定が難しくなるはずだ。
あと、元の問題では「24時間以内」という条件がついていたが、この条件を外した場合は。
- 1人の家来が1000本のうち500本を毒味【←現実にはそんなに飲めないが】。この家来が死んだ場合は、飲まなかった500本は安全なものとして除外。家来が生きていた時は、毒味したほうの500本を除外。
- 2人目の家来が、除外されなかった500本のうちの250本を毒味。その結果により250本を除外。
- 3人目の家来が、除外されなかった250本のうち125本を毒味。その結果により125本を除外。
- 4人目の家来が、除外されなかった125本のうち63本を毒味。その結果により、63本または62本を除外。
- 5人目の家来が、除外されなかった63本または62本のうち31本を毒味。その結果により、32本または31本を除外。
- 6人目の家来が、除外されなかった32本または31本のうち16本を毒味。その結果により、16本または15本を除外。
- 7人目の家来が、除外されなかった16本または15本のうち8本を毒味。その結果により、8本または7本を除外。
- 8人目の家来が、除外されなかった8本または7本のうち4本を毒味。その結果により4本または3本を除外。
- 9人目の家来が、除外されなかった4本または3本のうち2本を毒味。その結果、2本または1本を除外。
- 上記で残されたのは2本または1本となるが、残りが1本の場合は確定。残りが2本の時は10人目の家来がそのうちの1本を飲み、その結果により判定。
というオーソドックスな絞り込み方法も可能。元の解法と比べて、どちらのほうが毒で死亡する犠牲者が多いのかはケースバイケースになる。元の解法では、0番のワインが毒入りであった場合は家来は誰も死ななくて済むが、999番が毒入りの時は「1111100111」なので8人が死んでしまう【←犠牲者を減らすために1000番から1023番までのうちで「0」の多い番号に付け替えるとよいかも】。確率の計算はしていないが、期待値ばかりでなく、変動幅（分散の大きさ）も考慮する必要がありそうだ。
|
03月のインデックスへ戻る
