ペルーのコイン投げ

概要

この学習では、信頼し合っていない二人が、電話だけで、コイン投げによる公平で無作為な選択をするよう な、一見不可能に見える仕事を簡単にしてしまうやり方を紹介しています。

技能

• ブール理論
• 関数
• パズル解き

年齢

• 9 歳以上

必要な能力

• 数を数えること
• 偶数と奇数の理解。
• and と or の考え方の理解が役に立つ。
  • 子供たちが2進数表現(学習1:点を数える)、パリティの概念(学習4:カード交換の手品)、一方向関数の例(学習14:ツーリストタウン)を学習しているならこの学習からさらに多くのものを得るだろう。

時間

• 約30分

教材

• 子どもごとに必要なもの
  • ワークシートのコピー　PDF
  • 約 24 個の 2 種類の色の小さいボタンまたはおはじき

• ワークシート
  • 応用と解説　PDF

• 授業用補足資料　PDF

活動

はじめに

この学習はそもそも著者の1人(MRF)がペルーで子供たちと作業をしているときにひらめいたので、ペルー の名が付いています。あなたは、このストーリーをそれぞれの状態に合わせて作り変えてもかまいません。

リマとクスコの女子サッカーチームが決勝戦をどちらのホームグラウンドでやるか決める必要がありました。 一番簡単な方法はコイン投げでしょう。 しかし、2つの都市が遠く離れていて、リマの代表アリシアとクスコの代表ベニートはコイン投げのために、時間とお金をかけることはできませんでした。

電話でコイン投げをすることはできるでしょうか。
アリシアがコインを投げ、ベニートが表か裏を当てることはできました。
だけど、ベニートが「表」と言ったら、アリシアは「ごめんなさい、裏でした」と言うこともできるので、ベニートは納得できません。 アリシアが嘘をつく気がなかったとしても、大切な試合なので、アリシアにとって誘惑はとても強いでしょう。 たとえ、アリシアが真実を言ったとしても、ベニートは自分が負けたことを信じられるでしょうか。 これは彼らがやると決めたことです。

一緒に作業しながら、彼らは以下に説明するような and 回路と or 回路からなる回路を作ります。 基本的には、電話で行うことはできますが、実際にやってみると正直なところかなり退屈であることがわかります。(ファックスは助けになります!)。 作成していく過程を通じて、それぞれがずるをすることができないぐらい回路が複雑であることに興味を持つでしょう。

最終の回路は公知になります。
AND 回路と OR 回路の規則はシンプルです。
それぞれの回路には2つの入力と1つの出力があります(下の図)。 入力のそれぞれは0か1に当たり、偽か正と解釈することができます。
AND 回路の出力は両方の入力が1(真)の場合に限って、1(真)になり、それ以外は 0(偽)になります。
よって下の図では、OR 回路の出力は1で入力は0と1です。

もっと複雑な効果を得るために、1つの回路の出力を、ほかの回路(または複数の回路)の入力に繋げることができます。
たとえば、下の図の左の回路では2つの OR 回路の出力が 3 つ目の OR 回路の入力につながっているので、どの4つの入力も1であるならば、その出力は 1 になるでしょう。

図の右の回路では、上 2 つの AND 回路の出力が下の2つの回路に送り込まれ、その結果回路全体とし て2つの出力値を得ます。
ペルー人のコイン投げのために、私たちはさらに複雑な回路を必要とします。
ワークシートには6つの入力と6つの出力からなる回路があります。

上の図はある 6 ケタの値を入力して動く例を示しています。 電話でコイン投げをするためにこの回路を使うには、次のようにします。
アリシアは 6 ケタの 2 進数(1か0)のでたらめな入力する値を選び、秘密にしておきます。
彼女は 6 ケタの数字を回路に通し、ベニートに出力された値を送ります。 ベニートは出力された値を聞いたらすぐに、アリシアが入力した値が偶数か奇数かを当てなければなりません-言い換えると、彼 (女) はアリシアの入力のパリティを当てなければなりません。もし回路がベニートが答えを出すことができないほど複雑なら、彼の推測はどうしてもでたらめな選択になってしまいます(事実、彼は選ぶためににコインを投げさえするかもしれません)

ベニートの答えが正しいなら、彼は勝ち決勝戦はクスコで行います。ベニートの答えが間違いなら、アリシアが勝ち、決勝戦はリマで行います。 ベニートがアリシアに答えを伝えたらすぐ、アリシアは秘密にしておいた入力値を明かすので、ベニートが言った答えの正しさを確認することができます。

1. 子供たちを小さなグループに分け、それぞれに回路図とおはじきを渡し、ストーリーを説明します。もし彼らのスポーツチームのキャプテンがライバルの学校とコイン投げをすることがイメージできるなら、この状況は子供たちにとってより意味のあるものになるでしょう。
   赤は0、青は1のようにおはじきの色に意味を決め、子供たちが覚えていられるようにワークシートの上部の説明書きに書いておきます。
2. 子供たちにアリシアが選んだ数桁の数をどうやって入力の場所に置くかを示します。 それからワークシートの下部に書いてある and 回路と or 回路の規則を説明します。(子供たちにどの色が入るか考えさせるとよいでしょう)
3. ノードにおはじきを置き、対応した出力を引き出すために回路をどのように動けばよいかを示します。 これはきちんと注意深くやらなければなりません。次の表は不安になったら確認するための参考資料でありすべての入力に対しての出力が示されています。
   
4. さあ、それぞれの班からアリシアとベニートを選びましょう。 班を2つに分け、アリシア側とベニート側に分けます。
   アリシアは回路に入力する乱数を選び、出力をはじき出し、ベニートに伝えます。 ベニートは入力した値のパリティをあてます。(奇数か偶数で) この過程を通して、ベニートの推測は基本的にでたらめであることが明らかになります。 次にアリシアは全員に入力した値を伝え、そのパリティが正しいならベニートが勝ちます。 ベニートは、回路の出力を点検することでアリシアが入力値を変えていないことを確かめることができます。 今、コイン投げが終わりました。 出力した値から入力した値を見つけることができるなら、ベニートはだますことができます。 だから、ベニートがだますことを防ぐために、学習14で述べてあるのと同様に、アリシアは回路の関数が一方向であることを確認することに関心を向けます。
   一方向関数は入力する値がわかっていれば、出力を計算するのが簡単ですが、出力された値から入力を計算するのは大変難しいのです。 アリシアが相手の出したパリティから、(2つの)入力値を見つけることができるなら、ベニートをだますことができます。
   そのとき、ベニートがどんな推測をしても、アリシアはベニートの間違いを示す入力値を発表することができます。
   だからベニートは、回路はたくさんの異なった入力値に対して同じ出力値を対応づけないことを確かめることに興味をもちます。
5. 子供たちがアリシアかベニートのためにだます方法を思いつくか見てみましょう。
   表 17.1 の 1 行目を見ると、たとえば 000001,000011, 000101 など、いくつかの異なった入力が 010010 という出力をしていることがわかります。
   だから、アリシアが出力値 010010 を示したとき、パリティが偶数であるとベニートが推測したならアリシアは入力値 000001 を言うことができ、奇数と推測したなら、アリシアは入力値 000011 を言うことができます。 この回路を使うと、ベニートをだますのは難しいのです。
   しかし、出力が偶然 011000 になったなら入力は必ず 100010 です。それ以外の可能性はありません。(表で正しいことを確認することができます)

だから、もしこの数をアリシアが偶然思いついたなら、ベニートは偶数とあてることができ、しかも正しいと確信できるのです。
コンピュータシステムを使うと、もっとたくさんのビットを使って、非常にたくさんの可能性を試すことがで きます。(ビットを増やすと数の可能性は 2 倍になります)
さあ、子供たちのグループにこのゲームのための彼ら自身の回路を発明させましょう。
アリシアのために、そしてもう一方はベニートのために簡単にだます回路をみつけることができるでしょうか。

回路がなぜ6つの入力を持つかどうかは問題ではなく、違った数の入力と出力でもできるでしょう。