connecting...
Google translation for articles :
6 NEMBER donated to you!!

【数学】悪魔の証明 (追記:5/27)

nem7.29xem (6) 197 13 0

 



ミヤビちゃんは、元気な小学4年生。


ある日学校から帰ってくると、クッキーを買いに行くようお母さんからおつかいを頼まれました。


四角いクッキーを3枚、丸いクッキーを4枚、ハート形のクッキーを5枚、星形のクッキーを6枚
買ってくるように言われ、それぞれの枚数が書かれたメモを渡してもらいました。



家の近くにあるお菓子屋さんで、ミヤビちゃんはクッキーを買いました。


お金を払い、店を出て、お母さんから渡されたメモを再確認しました。


するとびっくり。ミヤビちゃんは、買うクッキーの枚数を間違えたことに気づきました。



このままではお母さんに怒られてしまう。新しくクッキーを買うためのお金もないし、返品もできなさそうです。


どうしよう・・・と途方にくれていると、

 

「おねえさん、どうしたの?」


と声をかけられました。ミヤビちゃんが声のした方を向くと、ミヤビちゃんより
一つか二つくらい年が小さい男の子が立っていました。名前を尋ねると、
男の子は のぼる と名乗りました。お菓子屋さんの店長の一人息子なんだそうです。


ミヤビちゃんが事情を話すと、


「あぁ、買う枚数を間違えちゃったの。僕、たくさんクッキーを持ってるから、交換してあげようか?」


と のぼる君。さすがお菓子屋さんの息子です。ミヤビちゃんは喜びました。


「ほんとぉ?ありがとう!」

「うん。でも、ただ交換してあげるわけじゃないよ。」



そう言うと、のぼる君は交換の ルール を話し始めました。


ルール①:四角いクッキー2枚と、ハート形のクッキー2枚が交換できる。
(逆に、ハート形のクッキー2枚と、四角いクッキー2枚を交換できる)

ルール②:「四角いクッキー1枚、丸いクッキー1枚」のペアと「ハート形のクッキー1枚、星形のクッキー1枚」のペアが交換できる。

(「ハート形のクッキー1枚、星形のクッキー1枚」と「四角いクッキー1枚、丸いクッキー1枚」を交換できる)

ルール③:丸いクッキー2枚と、星形のクッキー2枚が交換できる。
(星形のクッキー2枚と丸いクッキー2枚を交換できる)



ミヤビちゃんが「何それ!すごいめんどくさい!」と言いますが、のぼる君はニヤニヤしているだけ。

 


交換をお願いする立場のミヤビちゃんは、のぼる君の提案に、しぶしぶ従うことにしました。


さて、今ミヤビちゃんが持っているクッキーは、四角:6枚、ハート:2枚、丸:7枚、星:3枚です。
クッキーを交換して、お母さんに頼まれた枚数 四角:3枚、ハート:5枚、丸:4枚、星:6枚にすることを
目指します。

まず、星形のクッキーの枚数が足りないので、自分が持っている丸いクッキー枚を、
星形のクッキー枚と交換しました。そのため、丸いクッキーが枚減り、星形のクッキーが枚増えました。


これでミヤビちゃんが持っているクッキーの枚数は、四角:6枚、ハート:2枚、丸:5枚、星:5枚となりました。


次に、自分が持っている「四角いクッキー1枚、丸いクッキー1枚」のペアを
「ハート形のクッキー1枚、星形のクッキー1枚」のペアと交換しました。



最後に、自分が持っている四角いクッキー2枚を、ハート形のクッキー2枚と交換しました。



これでミヤビちゃんが持っているクッキーの枚数は、四角:3枚、ハート:5枚、丸:4枚、星:6枚となりました。
お母さんに頼まれた通りの枚数になったので、ミヤビちゃんは喜びます。


「やった!お母さんに言われた通りの枚数になったよ!」


「お、すごいね、おねえさん。」

「なんか楽しいね、このゲーム!」


そう言って、ミヤビちゃんは家にクッキーを持って帰りました。




ーーーーーーーー次の日




またまたお母さんにクッキーのおつかいを頼まれたミヤビちゃん。


そして、またまた買う枚数を間違えたミヤビちゃん。


「あぁぁ、なんで私は買う前にちゃんと確認しないの!」


そう言って頭を抱えていると、


「また間違えたの?」


と声をかけられました。


「あ!のぼる君!ねぇ、またクッキーを交換してよ!」


「うん、いいけど。」


「昨日のクッキー交換ゲーム、楽しかったからまたやろうよ」

 

昨日、ゲームを見事クリアしたミヤビちゃんは、ちょっとノリノリです。

早速、どうやって交換すれば、お母さんに頼まれた枚数にすることができるか
を考え始めます。





その様子を見た のぼる君は、あることに気づきます。


「あれ?あれれ??ちょっと待って。おねえさん、これ絶対にクリアできないよ・・・」

 

問題 今回の場合、どんなに交換を繰り返しても、お母さんに頼まれた枚数にすることはできません
なぜでしょうか。交換のルールは、昨日と同じものです。

 

 



どうも、やってみよう です。
いつもと趣向を変えて、ストーリー形式で記事をスタートしてみました。


今回のテーマは、「悪魔の証明」です。

 

何かが「できること」を証明するには、実際にそれをやってみせて「ほら、できたでしょ」と言えばいいわけですが、
何かが「できないこと」を証明するのはとても大変。「がんばったけど、できませんでした」というのは
証明にならないわけです。


何かが「できないこと」を証明するのは難しいことが多く、「悪魔の証明」なんて言われたりするんですよね。


数学の世界には、そんな「悪魔」を倒す方法がいくつか存在します。その一つが、「不変量(ふへんりょう)
という強力な概念です。

 

今回は上の`クッキー問題' を例に、「不変量」が悪魔を追い払う様子を見てみましょう!



「変わらないもの」を探す



先の問題は、「どんなにクッキーの交換を繰り返しても、お母さんに頼まれた枚数にすること」は
できないこと」を証明する「悪魔の証明」問題です。これは、次のようにして解くことができます:


ポイントは、のぼる君が提示した3つの交換ルールのもとでは、
『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」の合計』が全く変わらないという点です。


交換のルールは、下図のようなものでした:



例えば交換ルール①だと、四角いクッキーの枚数が減りますが、その代わりにハート形のクッキーの
枚数が増えるので、結果的に『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」』の合計は変わりません

 

交換ルール②だと、四角いクッキーの枚数が減って、
ハート形のクッキーの枚数が増えるので、やっぱり「四角いクッキーの枚数」と
「ハート形のクッキーの枚数」の合計は変わりません


交換ルール③は、四角、ハート形のクッキーに関係ないものなので、当然変わりません




最初にミヤビちゃんが持っている『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」の合計』は
4+5=9枚でした。どのようにクッキーを交換しても、ずーっと 9 のまま。
『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」の合計が 9』という状態から抜け出せないんです。

一方、お母さんから頼まれた枚数における『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」』
の合計は 7+4=11 なので、どんなふうに交換したって、絶対に目標の枚数にはたどり着けない、ということが
証明されるのです。




今回のようなゲームを考えたとき、それぞれの交換(変換)ルールで変わらない量のことを
不変量」と言います。

今回は、『「四角いクッキーの枚数」と「ハート形のクッキーの枚数」の合計』不変量です。


(※ちなみに『「丸いクッキーの枚数」と「星形のクッキーの枚数」の合計』も不変量です。)



(1) 変換のルールで、「変わらない量」つまり不変量を探す
(2) その不変量が、スタートとゴールで違っていることを確認する

という2ステップで、「できないこと」を証明することができてしまうのです。

 

拡大・縮小の不変量


「不変量」は、いろいろな場所で姿を現します。

相似(そうじ) というお話を中学校で習いました。

2つの三角形があったとき、片方をコピー機で拡大、縮小してサイズを調整することで、もう片方とぴったり重ねることが
できるとき、二つの三角形は相似であると言いましたね。

つまり、片方の三角形を、

①拡大
②縮小

という二つの変形で、もう一方の三角形とぴったり重ねることができるか?
そんな問題を考えたわけです。



僕たちは、この①、②の変形で変わらない量、つまり不変量を習いました。
その一つが、「三角形の3つの角度」です。


上の図のように、拡大・縮小をしても、「三角形の3つの角度」は変わりません。
つまり、「三角形の3つの角度」は、拡大・縮小という変形に対する不変量ということになります。

なので、


のように、二つの三角形の3つの角度が異なっている場合、片方の三角形から、拡大・縮小によって、
もう片方と同じ形に変形することはできない、と結論付けられるわけです。



このように、何か`変化'が起こったとき、その変化のもとで`変わらないもの'に注目をしてみると、
新しいことがわかったりします。

不変量の考え方は、数学以外でも活かされるんじゃないかな?とか思っています。
以上「不変量」概説でした。

あぺんでぃくすの欄に、もう一つ、不変量に関する問題を書いておきました。レッツチャレンジ!

ということで今日はここまで!


あぺんでぃくす


クッキーの交換ルールが次のように変更されました:

ルール(i) 四角いクッキー2枚と、ハート形のクッキー2枚が交換できる。
ルール(ii) 「四角:1枚、星形:2枚」のペアが、「丸:1枚、ハート:2枚」と交換できる。
ルール(iii) 「丸:1枚、ハート形:1枚」のペアが、「星形:2枚」と交換できる。  

(ルール(i)について、ハート形のクッキー2枚と四角いクッキー2枚も交換可。(ii),(iii)も同様。)

間違えたクッキーの枚数と、頼まれたクッキーの枚数は以下の通りです。ルール(i)~(iii)のもとでは、
お母さんに頼まれた枚数にすることはできません。なぜでしょうか。不変量を見つけて、説明してみてください:




(追記 5月27日)



`あぺんでぃくす' に載せた問題の解答です。

コメント欄でも載せましたが、ルール(i)-(iii) におけるクッキーの枚数の変化は、それぞれ

(i) 四角 -2、ハート +2、丸0、星0
(ii) 四角 -1、ハート +2 、丸 +1、星 ー2
(iii) 四角 0、ハート ー1 、丸 ー1、星 +2

となります。あぺんでぃくす の前に本文中に書いた問題での不変量は
四角の枚数+ハートの枚数」でした。

あぺんでぃくすの問題では、「四角の枚数+ハートの枚数」は(i)の交換ルールで不変ですが、
(ii), (iii) の交換ルールで変わってしまいます:

(ii)のルール、『「四角:1枚、星形:2枚」を、「丸:1枚、ハート:2枚」と交換する』を行うと、
四角が1枚減ってハートが2枚増えるので、「四角の枚数+ハートの枚数」は、増えることになります。

(iii)
のルール、『「丸:1枚、ハート形:1枚」を、「星形:2枚」と交換する』を行うと、ハートが1減るので、
四角の枚数+ハートの枚数」は、減ることになります。

このように、(ii), (iii)の交換で、±1の変化が出てしまうのです。 

ここで注目するのが、(ii)のルールのもと、丸の枚数が増え、(iii)のルールのもと、丸の枚数が減ることです。

そこで、新しく「(四角の枚数)+(ハートの枚数) - (丸の枚数)」という式を考えてみましょう。
これが、あぺんでぃくすの問題における一つの不変量です。ちょっと確かめてみましょう。

(i) の交換ルールだと、 (四角の枚数)が2減って、(ハートの枚数) が2増えて、丸の枚数は変化しないので、
(四角の枚数)+(ハートの枚数) - (丸の枚数)」の変化は0です。

(ii) の交換ルールだと、「(四角の枚数)+(ハートの枚数)」が増えることは上で言いましたが、
(丸の枚数)増えるので、「(四角の枚数)+(ハートの枚数) - (丸の枚数)」の変化は0になります。

(iii)
の交換ルールだと、「(四角の枚数)+(ハートの枚数)」が減ることは上で言いましたが
(丸の枚数)減るので、やっぱり「(四角の枚数)+(ハートの枚数) - (丸の枚数)」の変化は0になります。

なので、「(四角の枚数)+(ハートの枚数) - (丸の枚数)」は(i)-(iii)の交換ルールでの不変量なのです。

問題の中の「間違えて買った枚数」における「(四角の枚数)+(ハートの枚数) - (丸の枚数)」は、
5 + 7 - 4 = 8 ,  「お母さんに頼まれた枚数」における「(四角の枚数)+(ハートの枚数) - (丸の枚数)」は、
4 + 8 - 6 = 6 なので、不変量が異なるため、何回交換しても「お母さんに頼まれた枚数」に辿りつくことはできない
ことが示されます。

別解として、「2×(丸の枚数)+(星の枚数)」というのも不変量となります。
コメント欄でオーウェンさんが鋭い指摘をしてくださいましたが、丸と星のみに注目すると、
(ii) のルールも(iii)のルールも、『丸1枚と星2枚を交換する』というルールになっているんですね。
丸の数が枚減って、星の数が枚増えても、「2×(丸の枚数)+(星の枚数)」の変化量は、
2×(-1) + 2 = 0 なので、変わりません。((i)は丸、星に関係ない交換なので、当然変わりません。)
なので、「2×(丸の枚数)+(星の枚数)」は(i)-(iii)の交換ルールでの不変量です。


「間違えて買った枚数」における「2×(丸の枚数)+(星の枚数)」は、2 × 4 + 8 = 16,
「お母さんに頼まれた枚数」における「2×(丸の枚数)+(星の枚数)」は、2 × 6 + 6 = 18
なので、不変量が異なります。よって、何回交換しても「お母さんに頼まれた枚数」に辿りつくことはできない
ことが示されます。



難しい問題でしたが、ご回答いただいた皆様、ありがとうございました。コメントを通じて、この問題
に関する新しい考え方を教えていただきました。ほんの気持ち程度ですが、ネムを投げさせていただきます。

それでは!

Why don't you get crypt currency 'nem' by posting your blog article?

nemlog is blog posting service which has donation feature by crypt currency nem.
nemlog was launched to create environment which can be donated nem among NEMbers via blog articles.
Let's get nem by posting good blogs.

Nem prize event is being held frequently, Please join us on this opportunity!

nemlog registration from here
Register
Comments from NEMber
やってみよう
2019-05-28 20:12:12ID:121041

>>やそ::さん

確かにややこしいですね。不変量は一般に複雑なものになることが多いんですが、
それをどうやって見つけ出すか、というのも一つの研究対象になります。

>>オーウェン::さん

ありがとうございます。
本物のクッキーを使って、ちびっこに挑戦してもらうのもいいかもしれませんね。
最後に「これが不変量なんだよぉ^^」って。

やそ
2019-05-28 06:26:06ID:120913

なるほど!ややこしいけど理解が深まりました!

オーウェン
2019-05-27 23:55:50ID:120857

>>やってみよう::さん
クッキーの交換っていうキャッチーな題材なんで、子供も取っつきやすく楽しめそうな良問だと思いました。
ただ、なんで出来ないの?っていう証明に関しては難しいと思うので、そこは子供向きでは無いような気も(^^;

やってみよう
2019-05-27 21:58:53ID:120780

>>やそ::さん>>YUTO::さん>>目指せ北海道::さん>>オーウェン::さん

みなさま、記事にコメントをしていただき、ありがとうございました。
追記で、あぺんでぃくすの問題の解答を載せてみました。
わかりづらい箇所がありましたら、ご指摘いただければ幸いですー!

やってみよう
2019-05-24 00:08:24ID:119727

>>オーウェン::さん

お答えありがとうございます。

>>b一つに対して、d二つの交換しかこのルールには存在しない?

すばらしい視点です!問題を作っておいて、僕がこのことに気づいていませんでしたw
不変量を使わない、問題の別解ですね。正解です!

おっしゃる通り、(丸の枚数、星の枚数)は、最初(4枚、8枚)ですが、
「丸一つに対して、星二つの交換しかない」ことに注目すると、
(丸の枚数、星の枚数)がとりうる値は、
(0,16), (1,14), (2,12), (3,10), (4,8), (5,6), (6,4), (7,2), (8,0)
しかないので、目標の(6,6) にはたどり着けませんね。
交換の回数に応じて、「丸の枚数、星の枚数の合計」が+1、+2、+3、・・・またはー1、-2、-3になるので、
合計が12なのは (4,8) しかない、という指摘はその通りですね。

この視点からも不変量を作ることができます(これも僕が用意していたものと異なる別の不変量です!)
あぺんでぃくすの問題で、丸と星の変化のみに注目すると、
(i) 丸0、星0
(ii) 丸 +1、星 ー2
(iii) 丸 ー1、星 +2
となりますね。丸と星の合計:b + d は、(ii)で -1,(iii)で +1 変化してしまいますが、b, d に適切な係数を付けると、
(i)(ii)(iii)で変化しない不変量が完成します。

やってみよう
2019-05-23 23:36:19ID:119722

>>目指せ北海道::さん

お答えありがとうございます!
仰る通り、四角と丸だけにすると、「四角16、丸8」と「四角15、丸9」
になって、無理な可能性が濃厚になりますよね!
あぺんでぃくすの前の本文中にのせた問題だと、交換ルール①~③におけるそれぞれの
クッキーの枚数の変化は、
①四角 -2、ハート +2 、丸 0、星 0
②四角 -1、ハート +1 、丸 -1、星 +1
③四角 0、ハート 0、丸 -2、星 +2
というものなので、「四角とハートの合計」の変化は、①だとー2+2=0、②だと、-1+1=0、③だと0+0=0
で、「四角とハートの合計」の変化量は①~③のどの場合も0になります。

あぺんでぃくすの問題だと、
(I) 四角 -2、ハート +2、丸0、星0
(II) 四角 -1、ハート +2 、丸 +1、星 ー2
(III) 四角 0、ハート ー1 、丸 ー1、星 +2
となります。「四角とハートの合計」は(II)だと -1+2 = +1,
(III)だと 0-1 = -1 変化するので、「四角とハートの合計」に更に
「丸の数」も考慮に入れて微調整してあげると、不変量ができあがります!

オーウェン
2019-05-23 22:43:58ID:119697

確かに何となく無理なのは分かるw

四角=a, 丸=b, ハート=c, 星=d として見たら、
ルール(i) 2a ⇔ 2c
ルール(ii) a + 2d ⇔ b + 2c
ルール(iii) b + c ⇔ 2d

となります?よね。

丸(b)と星(d)だけに注目
b一つに対して、d二つの交換しかこのルールには存在しない?

・間違えて買った丸と星の総和は4+8=12
・お母さんから頼まれた枚数の総和6+6=12

この総和12を保ったまま、丸(b)と星(d)の数を変更することは出来ない。
交換すると必ずbとdの総和は1ずつ増えてしまうか減ってしまう。

で、不変量は?というと分からないw

この交換方法だと、丸と星の総和12は4+8でしか成し得ないということ?は分かる。

目指せ北海道
2019-05-23 07:28:25ID:119466

ルールiiとiiiを組み合わせると、四角1枚とハート1枚交換できるので、四角とハートは自由に交換できる(不変量ではない)。またルールiはIIとIIIを使って実現できるので、取り除いても良い。

問題を単純化するために、ハートを全部四角に交換してから、考える。この場合どちらも四角12からスタートになり、四角12+丸4+星8 > 四角12, 丸6, 星6 を以下の2つのルールで実現する問題になる。
ii 四角1, 星2 <> 丸1, 四角2 = 星2 <> 丸1, 四角1
III 丸1, 四角1 <> 星2
あ、同じになった!

よって、星2 <> 丸1+四角1、というルールを使って、星を全部丸と四角にしてみる。

間違えて買った数は、四角12+丸4+星8 = 四角12+丸4+丸4+四角4 = 四角16+丸8
頼まれた数は、四角12+丸6+星8 = 四角12+丸6+丸3+四角3 = 四角15+丸9

あれー?いつまでたっても不変量がでてこない。でもなんとなく無理っぽいというのはわかるw

やそ
2019-05-23 05:50:15ID:119450

>>やってみよう::さん
なるほど!難しいですね。
答え待ってます!

やってみよう
2019-05-23 01:22:30ID:119434

>>YUTO::さん

あ!確かにそうですね!物理変化における「エネルギーの総量」とか、
化学反応における「質量の総和」は、まさに不変量ですね。
そう考えると、「不変量」ってサイエンス全般で重要になりそうだなって
思えてきました。新しい考えに気づかせてもらえるコメントをありがとうございました!

NEMber who posted this article

「やってみよう」は、プログラマであるタノウエと、数学を勉強しているカナクボが、共同で管理しているアカウントです。
勉強をして身に付けた NEM の知識や数学の話題を、随時投稿していく予定です。
23718
0

Why don't you read following articles?

17.3907 XEM
250 12 2

15.39 XEM
248 10 1

19 XEM
247 8 0

130.4586 XEM
338 3 3

17.55 XEM
153 4 1

7.155 XEM
231 7 1


13.4521 XEM
186 7 0