アルクメデスのケーキ等分問題を難しく考える
NHKのクイズ？番組アルクメデス9月16日回の
resolve dogsというコーナーでのクイズが面白かった。
http://www.nhk.or.jp/medes/quiz/resolve/20100916.html
秤の類を用いずに、５人でケーキを切り分ける平等な方法は何か？というもの。
番組では、
というのを正解としていた。
これを理屈で説明してみようと思った。
まず、全員の能力は同じとしよう。（★仮定１）
番組では参加者の能力差は提示されていないから、仕方ない。
出来レース的だが以下の２つが言える。
A. 複数の参加者が同じ場所でストップをかけようとした場合、誰が勝者になるかはランダム
B. 全員が同じ方法を選ぶ
Aは、たとえば同着の場合くじ引きと考えるといい。
Bは全員の思考ロジックがまったく同じだから。
Bからこれが導ける。
C. どのターンでも、そのターンの参加者は皆同じ場所でストップをかける
ターンごとの場所には言及していない。あるターンで参加者の一人が位置Sでとめるなら、他の参加者も位置Sでとめるということだ。
これとAをあわせると、
D. どのターンでも、そのターンの参加者のうちからランダムに一人が勝つ
となる。
おっと重要な前提を忘れていた
E. 全員、貰えるケーキの量を最大化したい（できるだけ沢山のケーキを欲しい）と思っている。（★仮定２）
F. ケーキはプレーンなやつで、どこを切っても質は同じ。（★仮定３）
ここまでで結果は見えたようなもんだが、
ちょっとマジメにやってみる。
さて、 n 人でのターンを考えてみよう。
当然ながら n は２以上だ。
そのターンの参加者はスタートする前に「どこでストップをかけるか」を決める。
これを、残りケーキに対する割合 S(n) としよう。0<=S(n)<=1だ。
0.5 で「残りケーキの半分」のところになる。
S(n) はこのターンで勝ったときに貰える割合になる。
次のターンに持ち越される割合は 1 - S(n) になる。
C. によると全員同じ S(n) を選ぶことに注意して欲しい。
また、 D. によると誰が勝つかはランダムだ。
S(n) は大きいほうがよいように思われるが、負ける場合を考えると、次ターン以降の勝負で分け合う「残りケーキ」が減ってしまう。無闇に大きくはできない。
逆に S(n) を小さくすると、仮に勝ち抜けしたとしても、次ターン以降の残り参加者が分け合う「残りケーキ」は大きくなることになる。残り参加者が最終的に得る量よりも少なくするわけにはいかない。
この辺のロジックは E. から来るものだ。
量のみを問題にしているのは、 F. による。
さてどのように考えるか・・・
前回のターン、つまり n+1 人での勝負はどうだっただろうか。
勝者は S(n+1) の割合の位置でストップをかけたはずだ。
勝者が S(n+1) だけ切り取ったということは
前回の開始時点のケーキの量を x とすると
勝者の取り分(n+1) = x * S(n+1)
残り = x * (1 - S(n+1))
となる。
今回のターンでの勝者の取り分は、残りのうちの S(n) なので
勝者の取り分(n) = 前回の残り * S(n)
よって
勝者の取り分(n) = x * (1 - S(n+1)) * S(n)
となる。
D.によるとどのターンにおいても勝ち負けがランダムであるため、参加者は、
とすると、少なくとも
勝者の取り分(n+1) = x * S(n+1)
勝者の取り分(n) = x * (1 - S(n+1)) * S(n)
は等しいはずだ。
等号で結んで
x * S(n+1) = x * (1 - S(n+1)) * S(n)
x は明らかに 0 より大きい（ケーキの量だ！）ので割ってよい。
S(n+1) = (1 - S(n+1)) * S(n)
変形して S(n+1) について解くと
S(n+1) = S(n) / (1 + S(n)) .... 式1
となる。
ここである霊感が働いて
T(n) = 1 / S(n)
と置き換えよという。
式1を置換して
1/T(n+1) = (1/T(n)) / (1 + 1/T(n))
逆数にして
T(n+1) = (1 + 1 / T(n)) * T(n)
結局
T(n+1) = T(n) + 1 ... 式2
猛烈にすっきりした。
S(n)>0よってT(n)>0であることは自明だからいいよね？
ここから仕上げ。
n=2 つまり二人での勝負を考えてみよう。
勝ったときに貰える割合は S(2)
負けたときに貰える割合は 1 - S(2)
勝っても負けても同じだけ欲しいので
S(2) = 1 - S(2)
よって
S(2) = 0.5
はんぶんこだ。
S,Tの関係式より
T(2) = 1 / S(2) = 2
ここで式2より
T(n+1) = T(n) + 1
なので結局
T(n) = n (n >= 2)
となる
Sに戻すと
S(n) = 1 / n (n >= 2)
解けた！
結論
n人でのターンでは 1/n を狙え
じゃあ最初からn等分しろよ、と言いたい。
しかし、直感的にわかっても、言葉で説明するのって難しいねえ。
仮定４から等分になるのは当然という気もするけども、端折らずに説明するとしてもっといい説明ないかなあ？
resolve dogsというコーナーでのクイズが面白かった。
http://www.nhk.or.jp/medes/quiz/resolve/20100916.html
秤の類を用いずに、５人でケーキを切り分ける平等な方法は何か？というもの。
番組では、
円周方向に角度が少しずつ増えるようナイフを動かし、 各人が欲しいと思ったところでストップをかける。 最初にストップを掛けた人がその時点でのナイフの位置分だけ貰える。
というのを正解としていた。
これを理屈で説明してみようと思った。
まず、全員の能力は同じとしよう。（★仮定１）
番組では参加者の能力差は提示されていないから、仕方ない。
出来レース的だが以下の２つが言える。
A. 複数の参加者が同じ場所でストップをかけようとした場合、誰が勝者になるかはランダム
B. 全員が同じ方法を選ぶ
Aは、たとえば同着の場合くじ引きと考えるといい。
Bは全員の思考ロジックがまったく同じだから。
Bからこれが導ける。
C. どのターンでも、そのターンの参加者は皆同じ場所でストップをかける
ターンごとの場所には言及していない。あるターンで参加者の一人が位置Sでとめるなら、他の参加者も位置Sでとめるということだ。
これとAをあわせると、
D. どのターンでも、そのターンの参加者のうちからランダムに一人が勝つ
となる。
おっと重要な前提を忘れていた
E. 全員、貰えるケーキの量を最大化したい（できるだけ沢山のケーキを欲しい）と思っている。（★仮定２）
F. ケーキはプレーンなやつで、どこを切っても質は同じ。（★仮定３）
ここまでで結果は見えたようなもんだが、
ちょっとマジメにやってみる。
さて、 n 人でのターンを考えてみよう。
当然ながら n は２以上だ。
そのターンの参加者はスタートする前に「どこでストップをかけるか」を決める。
これを、残りケーキに対する割合 S(n) としよう。0<=S(n)<=1だ。
0.5 で「残りケーキの半分」のところになる。
S(n) はこのターンで勝ったときに貰える割合になる。
次のターンに持ち越される割合は 1 - S(n) になる。
C. によると全員同じ S(n) を選ぶことに注意して欲しい。
また、 D. によると誰が勝つかはランダムだ。
S(n) は大きいほうがよいように思われるが、負ける場合を考えると、次ターン以降の勝負で分け合う「残りケーキ」が減ってしまう。無闇に大きくはできない。
逆に S(n) を小さくすると、仮に勝ち抜けしたとしても、次ターン以降の残り参加者が分け合う「残りケーキ」は大きくなることになる。残り参加者が最終的に得る量よりも少なくするわけにはいかない。
この辺のロジックは E. から来るものだ。
量のみを問題にしているのは、 F. による。
さてどのように考えるか・・・
前回のターン、つまり n+1 人での勝負はどうだっただろうか。
勝者は S(n+1) の割合の位置でストップをかけたはずだ。
勝者が S(n+1) だけ切り取ったということは
前回の開始時点のケーキの量を x とすると
勝者の取り分(n+1) = x * S(n+1)
残り = x * (1 - S(n+1))
となる。
今回のターンでの勝者の取り分は、残りのうちの S(n) なので
勝者の取り分(n) = 前回の残り * S(n)
よって
勝者の取り分(n) = x * (1 - S(n+1)) * S(n)
となる。
D.によるとどのターンにおいても勝ち負けがランダムであるため、参加者は、
どのターンで勝とうが、全敗しようが、取り分が同じになるように調節するに違いない。（★仮定４）
とすると、少なくとも
勝者の取り分(n+1) = x * S(n+1)
勝者の取り分(n) = x * (1 - S(n+1)) * S(n)
は等しいはずだ。
等号で結んで
x * S(n+1) = x * (1 - S(n+1)) * S(n)
x は明らかに 0 より大きい（ケーキの量だ！）ので割ってよい。
S(n+1) = (1 - S(n+1)) * S(n)
変形して S(n+1) について解くと
S(n+1) = S(n) / (1 + S(n)) .... 式1
となる。
ここである霊感が働いて
T(n) = 1 / S(n)
と置き換えよという。
式1を置換して
1/T(n+1) = (1/T(n)) / (1 + 1/T(n))
逆数にして
T(n+1) = (1 + 1 / T(n)) * T(n)
結局
T(n+1) = T(n) + 1 ... 式2
猛烈にすっきりした。
S(n)>0よってT(n)>0であることは自明だからいいよね？
ここから仕上げ。
n=2 つまり二人での勝負を考えてみよう。
勝ったときに貰える割合は S(2)
負けたときに貰える割合は 1 - S(2)
勝っても負けても同じだけ欲しいので
S(2) = 1 - S(2)
よって
S(2) = 0.5
はんぶんこだ。
S,Tの関係式より
T(2) = 1 / S(2) = 2
ここで式2より
T(n+1) = T(n) + 1
なので結局
T(n) = n (n >= 2)
となる
Sに戻すと
S(n) = 1 / n (n >= 2)
解けた！
結論
n人でのターンでは 1/n を狙え
じゃあ最初からn等分しろよ、と言いたい。
しかし、直感的にわかっても、言葉で説明するのって難しいねえ。
仮定４から等分になるのは当然という気もするけども、端折らずに説明するとしてもっといい説明ないかなあ？
コメント 0