解答だよ
当記事は、"目黒ワンニャンパーク Advent Calendar 2021”の23日目の記事です。
Welcome.
雄太一です。
前回の記事で、論理問題を二問ほど出題しました。
当記事は、その解説と振り返りとなります。
まだご覧になっていない方は、先にそちらをご一読ください。
さてさて。
さあさあ!解答編だよ。
それでは早速いってみましょ~
①コインと天秤の問題 解答編
\結論からいくぞ!/
A.29524枚
「は?こんなん手計算無理なんだが?」とお怒りの方,まあまあ落ち着いて…
今から数学的に結果を求める手法をお教えします。
まず、求めるべきは天秤を用いた時の一回の測定による情報量です。
天秤の両皿に同じ枚数のコインを載せた時に得られる結果は三つ。
①左に傾く ②右に傾く ③釣り合う
です。
逆に言えば、一回の測定により上①~③のいずれか一つの結果が導き出せる事から、パターンの総数を三分の一にできる事がわかります。
例として、コインABCの三枚があったとします。
この中の一枚は偽造通貨であり、正規品より少し重い事がはじめからわかっているとします。
天秤の左皿にA、右皿にBを置いた時、得られる結果は先程示したとおり、三パターンです。
そしてそれらのパターン毎に、偽造コインを三枚から一枚に絞り込む事ができます、
①左に傾く→Aが偽物のパターンに絞り込める
②右に傾く→Bが偽物のパターンに絞り込める
③釣り合う→Cが偽物のパターンに絞り込める
こんな感じですね。
このことから、天秤一回の使用で、最大三枚までのコイン群から偽造コインを特定できる事がわかります。
では、天秤を二回使える場合は?→上記の処理を二回→三分の一を二回なので九分の一です。つまり、天秤二回の使用により特定できる最大の枚数は九枚!
以上のことを一般化すると、天秤n回の操作により絞り込む事の出来る最大の枚数は3のn乗(3^n)となります。
続いては、偽造コインの重さがわからないケースが与える影響について考えます。
偽造コインの重さが重いのかわかっている場合は、先程のコインABCの例でも述べましたが、偽造コインのパターン数を三分の一に絞り込む事ができます。しかしながら、当問題で考えなければならないのは、偽造コインの重さが重いのか軽いのかわからない場合です。
①左に傾く→Aが偽物(重い)かBが偽物(軽い)のパターンに絞り込める
②右に傾く→Bが偽物(重い)かAが偽物(軽い)のパターンに絞り込める
③釣り合う→Cが偽物(重いか軽いかわからない)のパターンに絞り込める
このように、天秤の測定により絞り込めるパターン数が、先程のパターンと比べ二倍に増えている事がわかります。
これを逆に言うと、天秤により求めることのできるコインの最大枚数を半分にする(n/2)、と言い換える事ができます。
以上の二点を踏まえた上で、改めて問題を一般化します。
:重さの違う偽造コイン一枚を含めたコイン群に天秤をn回使用した時に偽造コインを検出可能な最大枚数Nを求めよ。
→ N=(3^n)/2
となります。そして、今回は天秤を十回使用する為、n=10を代入します。
→ N=(3^10)/2
→ N=59049/2=29524.5
(計算がめんどい人は検索バーに上の数式をそのまま突っ込んでみよう!)
つまり答えは29524.5枚です!・・・とは、なりません。解を枚数で求めなければならないため、自然数で求められない端数は切り捨てます。
よって答えは29524枚です!
②爆弾処理班の問題
まず、この問題を考えるにあたり最も重要な事は、マスとコインの配列から、座標を絶対的に算出する事です。
それを行う為には、知っておかなければならない前提知識があります。
それが記数法の三進法です。(滅茶苦茶重要です)
三進法とは、0,1,2の三種類の数字だけを用いた記数法です。ちなみに我々が日々使っている0~9までの数字を用いた記数法を十進法と言います。
十進法の3は、三進法では10と記します。つまり、一の位では3毎に桁が一つ繰り上がるのです。
0123456789を三進法で表すと、0,1,2,10,11,12,20,21,22,100となります。
以上を踏まえた上で、説明に入ります。
①マスへの数の割り振り
※説明の間は手間を省く為、将棋盤を3×3まで簡略化して説明します
まず、それぞれのマスに数を割り振っていきます。左上から右下まで、0~8までの数字を割り振ります。
そしてそれらを三進法で記します。
②コインの変数
次に、コインの持つ性質を定義します。例えば以下のような感じです。
・何も置かれていない→×0
・表のコインが置かれている→×1
・裏のコインが置かれている→×2
③マスの評価値を算出
例えば、初期状態がこのような状態だったとします。
(何も書かれていない所には、何も置かれていない)
①で定義したマス01(左上から二番目)と、11,22に表のコインが、02,10,21に裏のコインが置かれている状況です、
これらのマスに②で定義した変数を掛け、評価値を算出します。例えばマス01のコインは表なので、01×1をします。
すると以下のようになります。
④座標の算出
先程算出したすべてのマスの評価値を位毎に足し合わせて求めていきます。
例えば上記の図の場合、十の位と一の位の数字を十進法でそれぞれ足し算します。
十の位:2+1+4+2=9
一の位:1+4+1+2+2=10
→9,10
9と10という数字が求められました。
更に、求められた数字を3で割り、あまりを求めます、
9 mod 3 =0
10 mod 3 =1
→0,1
0、1=01という数字が求められました。
これが、現在上記の図でコインが示している座標です。
座標の特定ができました。
⑤座標の修正
ここまで来ればあともう少し!
今度は、指定されたマス(ピカリと光ったマス)の座標を確認します。
例えば左下の”20”のマスが光ったとしましょう。その場合、現在の座標”01”をコインの操作により、20のマスを示すように修正する必要があります。
式に表すとこんな感じ
・現在地+【修正値】=目的地
両辺から現在地の値を引いて、
→【修正値】=目的地-現在地 (mod 3)
現在の座標が01であるため、20へ到達するための修正値は、
十の位:2-0 mod 3 = 2
一の位:0-1 mod 3 = 2
→修正値:22
22という数字が出てきました。これが修正値です。
あとは修正値に対応したコインの操作を行うだけです。
22または11のマスをそのマスのコインの状況に応じて操作すれば修正が可能です。
・22のマスを操作する場合
・マスが無→表
・マスが表→裏
・マスが裏→無
・11のマスを操作する場合
・マスが無→裏
・マスが表→無
・マスが裏→表
今回であれば、22のマスは表のコインが置かれているので、これを裏にするか、あるいは11のマスに置いてある表のコインを取り除けば、操作はOKです。上記のいずれの操作でも、現在地が修正され、目的地と一致するはずです。
以上の方法により、爆弾を解除可能! Q.E.D.!!!!!!!!!!!!!!!!!!!!!!!!!
また今回は簡略化し3×3で行いましたが、マスの総数が3^n(n=自然数)であれば
、あらゆるパターンのこの問題を解く事ができます。
・別解
こちらの問題を出題したところ、なんと僅か2日でうーねこさん(Twitter:@unecochan)にこの問題を解かれてしまいました。すごいねうにゃこちゃん!
その際に用いられた技法が”パリティ”と”排他的論理和”を利用した解法、との事で、こちらが想定していた解法とちょっとだけ違ったので、ここに紹介させていただきます。
全文僕が解説する体力がなくなっちゃったので、URL省略。簡素でキレイにまとめてくれているので是非とも読んでみてください!(あと、オマケでシミュレーターまで作ってくれました)
https://gist.github.com/uneco/949a33051148ad69c44b1493855369d3
解除法全文 作:うーねこ
シミュレーター 作:うーねこ ←!?
以上です!
みんなは目黒ワンニャンパークの爆発を免れたかな?
楽しんでいただけましたでしょうか!?もし、楽しんでいただけたのであれば、とても嬉しい!(・∀・)
最後になりますがご覧いただきありがとうございました。
質問等あれば雄太一のTwitter:@_kiwinz1までどうぞ!フォローもよろしくね。
またこのように、筆者である雄太一は数学とか論理問題とか麻雀とか頭を使う事が大好きなので、是非とも遊んでやって下さい。喜びます。
あと余力があれば、今回の出題意図や裏テーマなどを語るかもしれません。
では。皆様良いお年を。
メリークリスマス!!!!!!!!!!!!!!!!