日々知的刺激を求める社会人駈け出しが好きなことを綴るブログです。〜匿名性を守る投票の方法〜2016-11-24雑記帳##10人の暗号学者に、「宝くじが当たったからご馳走をしたい」という招待状が、差出人不明で届いた。10人は招待状に従って集まり、円卓で豪華な食事を堪能したのだが、招待状の差出人が誰なのかわからず、もやもやしていた。招待状を送った主催者は正体を隠したいのであろうことは理解できるが、この10人の中に主催者がいるのか、いないのか、それだけでも知りたいというのが全員の総意だった。主催者本人も、正体をばらすことはせずとも、「10人の中にいること」自体は表明しても良いと思っているはずだ。主催者がいるのか、いないのかを、主催者が誰かということが全く特定できない方法で明らかにする方法はあるだろうか?##※「誰が主催者である可能性が高いか」ということすら見当がつかないような方法、つまり、「主催者がいるのか、いないのか」ただそれだけが情報としてわかる方法が求められています。これは、「食事をする暗号学者」と呼ばれる問題で、ITの勉強をしているときにたまたまwikiepdiaで見つけたものです。区別できない紙でもあれば、主催者は◯を、主催者でなければ×を書くことにして、混ぜて開票すればよいのでしょうが、この問題ではそういった「匿名性を守る道具」を、使わない方法を考えます。wikipediaの解説には、全員が全員と「秘密のやりとり」をして解決する方法が書かれていました。解説を読んだ私は、ふーむ、なるほど、とも思いましたが、同時に思いました。「ちょっと面倒くさすぎない??」と。円卓に座っているのに、わざわざ向かいの人とも秘密のやりとりをするなんて、現実的ではありません。10人となってはなおさらですね。簡便にならないでしょうか??・・・考えてみたら、全然簡単な方法がありました。考えたのは、次の2種類です。(1)皆、隣の席の人とだけ内緒話ができる場合の方法(2)任意の人と内緒話をするのは2人だけで、あとの8人は全員に向けた発言しかしない方法これらをご紹介したいと思います。クイズとして解いてみたい方は、下を読む前に、考えてみてください。それでは、ご紹介します。内緒話というより、耳打ちだけで可能です。代表者を決め、代表者が1人で隠れてコイントスをして、表だったか裏だったかを左隣りの人に耳打ちで伝えます。耳打ちされた人は、自分が主催者でなければ受け取った情報をそのまま隣の人に、自分が主催者であれば情報をすり替えて(「表」だったら「裏」に。「裏」だったら「表」に。)隣の人に、耳打ちします。これを続け、1周して最初の代表者に情報が戻ってきたら、代表者は主催者の有無を判定します。伝えたはずの情報が変わっていたら「主催者はいる」、伝えたはずの情報がそのままだったら「主催者はいない」、ということがわかりますから、代表者はわかった結果を発表します。(ここでもちろん、代表者自身が主催者だったら、情報が変わっていなくても「主催者はいる」、と発言します。情報が変わるのは主催者がいた場合に限るので、当然といえば当然ですね。誰が情報をすり替えたのかは、誰にもわかりません。符号の誤り検出に似ているところがありますね。面白いのが、この方法の発展として、同じようにして、ある質問にYESの人が何人いるかを調べる方法があります。内緒話だけで投票を行う方法もあるということです。代表者は、コインの表裏ではなく、0から9の数字をランダムに決めて、隣の人に耳打ちします。耳打ちを受けた人は、自分がYESなら伝えられた数字に1を足し、YESでなければ伝えられた数字をそのまま、次の人に耳打ちします。1を足して10になる場合は、「0」と伝えます。して一周すると、YESである人の数だけ数字が加算されるので、代表者が最後に、初めに耳打ちした数字と、受け取った数字との差を発表します。(ここでもちろん、自分がYESである場合はさらに1を足します。)たとえば、初めに耳打ちした数が8で、受け取った数が2ならば、YESである人の数は4人です。(8→9→0→1→2と、4人分増えた)紙と鉛筆がないときに、ぜひお試しください。全員が誠実であることは前提です。(勝手に数字を変えられちゃったら、たまったものではありませんね。)(2)任意の人と内緒話をするのは2人だけで、あとの8人は全員に向けた発言しかしない方法これは少し高度ですが、面白いです。要するに、2人さえ、秘密の意思伝達が可能であれば、主催者の存否を匿名で明らかにすることができる、ということです。秘密の意思伝達ができる2人はそれぞれ、残りの8人に対して「1」か「0」の情報を秘密裏に送ります。・それぞれの人について、「1」を送るか「0」を送るかは、ランダムに決めます。・ただし、自分が主催者でない場合は、「1」を送った人数が偶数になるようにし、自分が主催者である場合は、「1」を送った人数が奇数になるようにします。※たとえば、7人目まではコイントスなどでランダムに決め、8人目は「奇数」か「偶数」かが正しくなるように数字を決めればよいです。8人はそれぞれ2人から「1」か「0」の情報を受け取ることになります。この受け取った情報と、自分が主催者であるか否かに基づき、次のように数字を全員に向けて発言します。・2人から受け取った情報を足し合わせる。・自分が主催者であれば、さらに「1」を足す。自分が主催者でなければ、そのまま。・合計値が奇数ならば「1」、偶数ならば「0」と発言する。これにより8人からそれぞれ「1」か「0」の情報が発信されます。これらの合計を足して、合計値が奇数であれば、主催者はいるということになり、合計値が偶数であれば、主催者はいないということになるはずです。目的を達成できる理由は以下の通り。・誰も主催者でなければ、この方法の結果は偶数になるはずです。秘密の意思伝達ができる2人が「1」を送る数は偶数であり、8人はそれぞれそれを足し合わせるだけだからです。ここで、2人のどちらかが主催者であれば、「1」が送られる数は奇数になるし、8人のうち誰かが主催者であれば、合計値は、1ずれるので奇数になります。・そして、この方法では誰が主催者であるかの見当をつけることは誰にもできません。秘密の意思伝達ができる2人(A,B)のうちAにとっては、「1」を送ったはずの人(C)が「0」と発言していても、Bがその人に「1」を送ったからかもしれないし、その人(C)が主催者だからかもしれないので、区別できません。「1」を送ったはずの人(C)が「1」と発言していても、Bがその人に「1」を送ってさらにその人(C)が主催者なのかもしれないし、Bがその人に「0」を送ってその人(C)が主催者でないかもしれないので、区別できません。要するに、Bが「0」と「1」どちらをCに対して送ったかがわからないため、Cが主催者であるかはわからないのです。8人にとっては、「0」と「1」が送られてくるだけで、それ自身からは何の情報も得られないので、誰が主催者であるかは見当のつけようがありません。8人が発言する「1」と「0」の合計値も、元々はランダムに決められた数に基づくものなので、いくつになる傾向があるということもなく、合計値からは何も推測はできません。〜シミュレーション〜たとえばAの立場で考えてみます。Aが主催者でないとき、たまたま8人に送る信号がすべて「0」であったとします。8人(C,D,E,F,G,H,I,J)の発言が、(1,1,1,1,1,1,1,0)であったとします。信号がこのようになる確率→1/2^8この通り、どの事象も、同じ確率で起こりえたことですから、事後確率を考えても、B〜Jの誰が主催者である確率が高いかはわかりませんね。以上の方法は、10人でなくとも可能です。主催者(犯人)がいるか、いないか、を、匿名性を維持しながら調べることができます。これも、皆が作業を誠実に行い、インチキも結託もないことが前提です。誰もこれ以上の情報を公表しないことを約束する必要があります。(たとえばCが「Aからは0を受け取ったよ」などと言ってしまうと、それが真実であるかどうかはAやBには分かっているのでCの無実が証明されてしまいます。)以上、2つの簡便な方法を紹介してみました。どちらも裏切り者が少しでもいると匿名性を守るという目的を達成できなくなってしまう点では、wikipediaで説明される面倒くさい方法には劣るようです。この辺は「安全性」という項目に関わるお話みたいですね。情報理論はまだまだ勉強途上ですが、ときどきこういったパズルじみたお話が出てくると、わくわくするものです。〜Wordで穴埋め問題を作ってみた2015-07-15学習関連記事こんなものをつくってみました。(リンク先は自作htmlです)特許法の勉強をしている人はあまりいないかもしれませんが...↓スクショこんな風に条文の一部を穴埋めにして、カーソルを重ねると答えが見える仕様。条文に限らず、PCで暗記ものを勉強するならば何でも、こんな風に作ればはかどること間違い無しです!もともと「こんなのがほしい!」と思っていたものですが、Wordと、ちょっとhtmlを調べれば簡単にできちゃうんですね。href=""></a>に置換する。5リンク(a)の背景色、文字色等をCSSで設定。マウスオーバー(a:hover)による色変化の設定。6細かいものを微調整して完成。とまあこんな風にして作りました。リンクならばマウスオーバーだけで色が変わってくれるのがミソですね。(ちなみにリンクは押しても何もないです)ドラッグ反転で表示される方法なら3まででできて楽チンなんですけどね。(これはこれで、一字ずつ確認できるという特長がありますね。)スマホのアプリでも穴埋めが作れるものはありますが、特に条文のような長いものはパソコンのほうが圧倒的に視認性が良いし、応答も早くて良いです。何より共有しやすいです。(※著作権には注意)来年の弁理士試験に向けて(今年もだめだった;;)、不競法や著作権法なども作ってみようかと思います。0Pagetopオリジナルパズルゲーム2015-04-07面白いもの3月までお世話になっていた研究室のPCで作ったパズルゲームがあるので、よければと思い投稿します。こんなやつ↓ダウンロード先https://www.dropbox.com/s/papvk76o19tr26w/%E3%83%91%E3%82%BA%E3%83%AB.exe?dl=0(Windows用の実行ファイルです。遊べないバージョンがあるかはわかりません。遊べなかったらすみません。)ルールは独自のものです。シンプルで、パズル好きの方には楽しんでいただけるかと思います。盤面上には何本かの棒が並んで、いくつかの正方形を形作られていますが、いずれの正方形も、その中心にあるボタンを押すと90度右回転します。色のついている棒が正方形を形作ると色が消えます。すべての色を消せばステージクリアです。次に右上のボタンを押せばこのようにピンク色の棒で正方形ができ、(色が消え)ステージクリアです。大きな正方形も回転することができます。周囲の8本の棒が90度回転移動し、正方形が作れます。どんな挙動をするか、実際にお試しください。レベルが上がると、色の種類が増えたりします。盤面が大きくなるととても難しくなります。ボタンを長押しすると一回り大きな正方形を回すこともできます。ダイナミックな動きになって面白いです。開発環境がなくなってしまったので修正できませんが、その点ご了承ください。重要な点として、4×4のレベル6は6手ではなく9手が最短かと思われます。4×4のレベル7は何も考えず鬼畜問題として作ってみたもので、作者自身もまだ解けていません。万が一できた方はご一報ください(笑)。楽しんでいただければ幸いです。0Pagetop脈絡のない二つの言葉を組み合わせる遊び2015-03-15面白いものちょっと脳トレをしてみましょう。『まったく脈絡のない二つのもの・言葉を組み合わせて、斬新なものを生み出す』遊びです。頭を真っ白にして、何でもよいので物か言葉を頭に思い浮かべる。「まったく脈絡がない」ものを選ぶ。その組み合わせがどんなに意味わからないものでも、最低10秒は「この組み合わせからどんなものができるか」を考える。→コップの人形...あるいは、コップに使う人形!?こうして「コップのふち子さん」が生まれる。→コーンポタージュ味のアイス...ありえないだろと思いつつも、ガリガリ君コーンポタージュ味は大ヒットしましたね。こんな風に、一見組み合わさりそうにないものを組み合わせることによって、思わぬアイデアやヒット商品が生まれる可能性があるものです。様々な発明やデザインも、このような「意外な組み合わせ」が功を奏している事例があり、なかなか侮れません。(笑)需要から考えるニーズ志向に対し、アイデアから物を生み出すシーズ志向というやつですね。→冷蔵庫に足が生えたら面白いな。冷蔵庫くん...?なんかいそうなキャラクターだ。うーん、あんまり突飛じゃないな。