THE CATCHER IN THE LIE ～嘘ありの数当てマジック ハミング符号を添えて～

THE CATCHER IN THE LIE ～嘘ありの数当てマジック ハミング符号を添えて～ 第25回日曜数学会 ヘカテー@HKTmine

嘘ありの数当てマジック ▪ 0~15までの整数を1つ思い浮かべる。 ▪ 思い浮かべた整数がスライドに表示される8個の数字に含まれているかをYES/NOで回答する。 ▪ 回答は7回行うが、このうち一回までは嘘をついてもよいとする。 回答終了後、思い浮かべた整数を私が当ててみせます！ 2

嘘ありの数当てマジック Q1. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 3

嘘ありの数当てマジック Q2. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 4

嘘ありの数当てマジック Q3. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 5

嘘ありの数当てマジック Q4. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 6

嘘ありの数当てマジック Q5. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 7

嘘ありの数当てマジック Q6. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 8

嘘ありの数当てマジック Q7. 思い浮かべた数は以下の8個の数字の中に含まれていますか？ 9

嘘ありの数当てマジック 実演 嘘をついたのは 思い浮かべた数は 番目の質問で、 ですね？ 10

嘘ありの数当てマジック 仕組み 7回の質問はそれぞれ何を聞いているのか？ 11

嘘ありの数当てマジック 仕組み ～二進数表記～ Q1. Q3⊕Q5⊕Q7？ Q2. Q3⊕Q6⊕Q7？ Q3. 1***ですか？ Q4. Q5⊕Q6⊕Q7？ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 8 9 10 11 10 11 10 11 12 13 14 15 12 13 14 15 12 13 14 15 Q5. *1**ですか？ Q6. **1*ですか？ Q7. ***1ですか？ 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 10 11 12 13 14 15 10 11 12 13 14 15 10 11 12 13 14 15 (奇数ですか？と同じ) 10 11 12 13 14 15 ■はスライドに表示 されていた8個の数 同時に ■は質問に対して YESとなる数 12

嘘ありの数当てマジック 仕組み ～二進数表記～ Q1. Q3⊕Q5⊕Q7？ Q2. Q3⊕Q6⊕Q7？ Q3. 1***ですか？ Q4. Q5⊕Q6⊕Q7？ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 8 9 10 11 10 11 10 11 12 13 14 15 12 13 14 15 12 13 14 15 Q5. *1**ですか？ Q6. **1*ですか？ Q7. ***1ですか？ 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 10 11 12 13 14 15 10 11 12 13 14 15 10 11 12 13 14 15 (奇数ですか？と同じ) 10 11 12 13 14 15 嘘が無ければ Q3, Q5, Q6, Q7で 数を当てられる Q1, Q2, Q4で 嘘を当てる 13

嘘ありの数当てマジック 仕組み ～パリティ(偶奇性)～ Q5. *1**ですか？ Q6. **1*ですか？ Q7. ***1ですか？ 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 10 11 10 11 10 11 12 13 14 15 12 13 14 15 12 13 14 15 NO NO NO Q4, Q5, Q6, Q7に もし嘘があれば、 Q4, Q5, Q6, Q7に 嘘があったことは分かる Q4. Q5⊕Q6⊕Q7？ →Q5とQ6とQ7の質問をしたとき、 YESと答える回数の合計は奇数？ 0 1 2 3 (Q4はQ5,Q6,Q7のパリティチェックマン) 4 5 6 7 例：YES→1、NO→0とする。 8 9 10 11 質問に対する回答が以下の場合 12 13 14 15 Q5：0 Q6：0 Q7：0 Q4：1 (Q5⊕Q6⊕Q7)≠Q4→ 不一致！ YES →この中の誰かが嘘をついている！ ■はスライドに表示 されていた8個の数 同時に ■は質問に対して YESとなる数 Q4の■は Q5,Q6,Q7 の■ の対称差 14

嘘ありの数当てマジック 仕組み ～ベン図～ Q3. 1***ですか？ Q5. *1**ですか？ Q6. **1*ですか？ Q7. ***1ですか？ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 8 9 10 11 12 13 14 15 Q1. Q3⊕Q5⊕Q7？ 10 11 10 11 12 13 14 15 12 13 14 15 Q2. Q3⊕Q6⊕Q7？ Q4. Q5⊕Q6⊕Q7？ 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 10 11 10 11 12 13 14 15 12 13 14 15 Q1≟Q3⊕Q5⊕Q7を確認 Q2≟Q3⊕Q6⊕Q7を確認 10 11 12 13 14 15 10 11 12 13 14 15 ↓一致or不一致 を書く Q1 Q3 Q2 Q7 Q5 Q6 Q4≟Q5⊕Q6⊕Q7を確認 ↝結果を書き込む Q4 15

嘘ありの数当てマジック 仕組み ～ベン図～ 整数０, 嘘が２番目の例 Q3. 1***ですか？ Q5. *1**ですか？ Q6. **1*ですか？ Q7. ***1ですか？ 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 8 9 10 11 12 13 14 15 10 11 12 13 14 15 12 13 14 15 NO NO NO Q2. Q3⊕Q6⊕Q7？ 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 9 8 9 8 9 10 11 ↓結果を二進数 0 表記で読む Q4. Q5⊕Q6⊕Q7？ 0 10 11 10 11 12 13 14 15 NO Q1. Q3⊕Q5⊕Q7？ 10 11 10 11 12 13 14 15 12 13 14 15 12 13 14 15 NO YES NO 0 Q1 Q3 ０ Q2 １ １ Q7 ０ ０ Q6 Q5 ０ Q4 0 0 16 010→2番目が嘘！！

嘘ありの数当てマジック 仕組み ～ハミング符号～ ▪ 今回紹介した仕組みはハミング符号と呼ばれていて、 通信の誤り訂正に応用がある。 他にも……… ▪ 帽子パズル(帽子の色を当てるやつ) ▪ 悪魔とチェス盤のパズル(高難易度論理パズル) ▪ 天秤パズル(偽物のコインを当てるやつ) に応用出来る！！ す ご い ！ ！ 17

嘘ありの数当てマジック ～参考文献～ ▪ SITA2019ワークショップ「Guessing ～基礎と広がり～」：「後半 (広がり) 編 」スライド https://www.ieice.org/ess/sita/forum/article/2020/20200525 0839.pdf ▪ 数当てゲーム （「誤り訂正符号」に関連した話題） https://slidesplayer.net/slide/11235171/ ▪ しょうがくせい向けハミング符号 https://kanasys.com/tech/221 18

• https://www.ieice.org/ess/sita/forum/article/2020/202005250839.pdf
• https://slidesplayer.net/slide/11235171/
• https://kanasys.com/tech/221