 |
カードが７枚ありそれぞれに数字が１個づつ書かれています。つまり １、２、３、４、５、６、７と書かれたカードが１枚づつあります。
この７枚をシャッフルして、３枚をアリスに、３枚をボブに、１枚をイブに配ります。
アリスもボブもイブも、１、２、３、４、５、６、７と書かれたカードのそれぞれが、誰に配られたのかについて完全に知りたいと思っています。すなわち、アリスがどのカードを持っているか、ボブがどのカードを持っているか、イブがどのカードを持っているか、について全てを知ることが、３人の共通の目的です。
アリスとボブとが協力し、互いにこの目的をかなえつつ、かつ、イブについては、イブが持っているカード以外の６枚のカードのそれぞれについて、それらのうち１枚でも誰が持っているかについてイブには一切わからないようにしたいです。
なお、アリスとボブは、カードを配られる前に事前協議は出来なかったとします。すなわち暗号とその解読方法の打ち合わせはできませんでした。
また、アリスとボブとの間の全ての情報交換について、イブには知る権利があり、アリスとボブにはその権利を完全に保証する義務があります。
アリスが１回発言し、ボブが１回発言することで、両名が全てのカードの配布先を知ることが出来、その際に、イブには、自分が持っているカード以外のカードを誰が持っているのかについて全くわからない、そのようなアリスの発言とボブの発言とを教えてください。
先生が言うには、ファノ平面を使えとのことでしたが、よくわかりません。
急ぎません。
|
No.23031 2022/01/21(Fri) 22:04:28
|
☆ Re: 第三者に知らせないで公然と伝えあうには？ / たけちゃん |
|
|
|
アリスとボブはそれぞれ，
「自分が持つカードの数字の合計を7で割った余り」
を表明すればよいと思います．
この結果，アリスとボブは，
「2人のカードの全体(6枚)の合計を7で割った余り」を知ることができ，
1+2+3+4+5+6+7=28は7の倍数であることから，イブのカードを知ることができます．
自分のカードとイブのカードが判明すれば，3人のカードがすべてわかります．
(実際，2人の表明から，傍観者もイブのカードだけは判断可能です．)
一方，イブにとっては，アリスの表明とボブの表明は，
「片方がわかればもう片方もわかる」情報であり，
例えば「自分のカードとアリスの表明」の情報しか得られていないことになります．
このとき，自分のカード以外のどれも，
アリス，ボブのどちらに配られたか判断できません．
イブが実際に「判断できない」ことを確かめるには，次のように考えればよいです．
アリスが「余りは0」と表明した場合は，(イブのカードを知らない立場で，)
アリスの3数は，1,2,3,4,5,6,7のうち，和が7の倍数となる3数であり，
[1,2,4],[1,6,7],[2,5,7],[3,4,7],[3,5,6]
の5組の可能性があります．
イブにとっては，「自分のカードの数はアリスは持っていない」とわかりますが，
自分のカードが何であれ，3数の組には3通りの可能性が残り，
その3通りの組には，自分のカードの数以外のすべての数が含まれます．
つまり，アリスが持っていることが確定するカードは1枚もありません．
和が7で割って3余る3数，6余る3数，2余る3数，5余る3数，1余る3数，4余る3数は，
3数の組の各数を，順に1ずつ増やす(ただし，7からは1にする)ことで得られるので，
アリスがどの余りを表明したときも，同様の議論が成立しますね．
つまり，イブには，どのカードも，アリスが持っていると確定することはできません．
「自分のカードとボブの表明」の情報しか得られていないとみなすこともできるので，
イブには，どのカードも，ボブが持っていると確定することはできません．
|
No.23033 2022/01/22(Sat) 05:07:22
|
|
☆ Re: 第三者に知らせないで公然と伝えあうには？ / 全銀手順透過モード |
|
|
 |
たけちゃんさん、らすかるさん。
おかげさまで問題の意味がよくわかりました。ありがとうございました。
参考にさせていただいた上で私なりに思いついたファノ平面を用いたやり方を書いてみます。
ファノ平面の一例の図解は、www.fan-o.com/rainbow_fano.png にあります。これを元に考えました。このファノ平面から以下を取り出します。縦読みすると面白いです。
[1,2,4]
[2,3,5]
[3,4,6]
[4,5,7]
[5,6,1]
[6,7,2]
[7,1,3]
これには、色と数とを対応させるやり方がたくさんありますので自由に替えてもよいと思います。ですから一般性を失うことなく、アリスに配られたカードは[1,2,4]であったとできます。
アリスは次のように発言します。
「私のカードは[1,2,4]か[2,3,5]か[3,4,6]か[4,5,7]か[5,6,1]か[6,7,2]か[7,1,3]のうちどれかです。
」
このときイブにはどのカードがだれのところにいっているかについては、自分の分しかわかりません。アリスが示した７通りのうち３通りについては自分に配られた数字がはいっているので消しこむことができますが残りの４通りについてどれであるかを決められません。またその４通り全てについて共通に含まれている数字もありません。（もしもそうならその数字をアリスが持っているとイブにわかってしまいますがそのような心配はいりません。）
アリスの発言を聞いたボブは、3,5,6,7のうち３枚をもっています。アリスの発言のなかの７通りの可能性のうち正解以外の６通りのどれもが3,5,6,7のうち２つを含んでいますから、イブが3,5,6,7のうちのひとつを押さえていても、ボブは正解以外の６通りに自分のカードの数のどれかが含まれていることが確実にわかります。 これを消しこむことでボブにはアリスがもっているカードの数字が全部わかります。また、同時にボブはイブに配られたカードの数も割り出せます。
次にボブは発言します。
「イブが持っているカードの数は□だ。」
イブにとってはボブのこの発言は既知ですから、なんらあらたな情報を得られず、あいかわらず全くわからない状態です。
一方アリスは、イブが何を持っているのかを知ったので、ボブが何を持っているのかにちいて確実にわかります。
ところで
[1,2,4]
[2,3,5]
[3,4,6]
[4,5,7]
[5,6,1]
[6,7,2]
[7,1,3]
の各組の和を７で割った余りが０から６まで全部揃っているのがちょっとだけ気になりました。偶然かもしれません。
|
No.23036 2022/01/22(Sat) 15:42:51
|
|
☆ Re: 第三者に知らせないで公然と伝えあうには？ / たけちゃん |
|
|
|
[1,2,4]
[2,3,5]
[3,4,6]
[4,5,7]
[5,6,1]
[6,7,2]
[7,1,3]
は，私のはじめのコメントにある
「3数の組の各数を，順に1ずつ増やす」
に該当しますので，
7で割った余りは(ある意味)3ずつ増えます．
「7で割った余りが0から6まで全部揃う」理由は，
このことを元に説明可能です．
|
No.23037 2022/01/22(Sat) 17:42:58
|
|
