パズルの国のアリス

双子への新しい協力課題(解答)

 ダムの1週目の要求額をS1,ディーの2週目の要求額をS2としよう。一般にnn≧3)週目に2人のどちらかがもらえる額SnSn−1Sn−2を割り切る最大の奇数だ。

 まず,nが十分に大きくなればSnは一定値に落ち着くことを示そう。これまで何度も見てきたように,その種のことを証明する標準的な手段は,状況に付随して一方向にのみ変化する量を見つけ,それがある限界を超えて変化する ことがないことを示すことだ。上のSnの場合,最初に注意しておくべきことは任意のn(≧3)においてSn−1Sn−2は偶数だから

だということだ。だから,数列{Sn}は単調に減少するわけではないが,問題の例でも見たように,だいたい減少傾向にある。だから,ある非負整数が存在してそれよりは小さくなれなくなるだろうということは容易に想像できるが,そのことは必ずしもSnが一定値になることを意味しないし,そもそも上の式は,直接,広義減少列を定義しているわけでもない。だが,少し考えるとSn−1≦max{Sn−1Sn−2}はいつでも成立するのだから

 max{SnSn−1}≦max{Sn−1Sn−2

となり,max{SnSn−1}がnに関して広義減少になることに気がつく。定義によりSn≧1だから,この量がいつまでも小さくなり続けることはできず,あるnと定数S≧1が存在して

 1≦S=max{Sn+1Sn}=max{Sn+2Sn+1}=max{Sn+3Sn+2}=…

である。したがってSn+1Snのうち少なくとも一方はSであるが,SnSとしてよい(なぜなら,そうでない場合,max{Sn+2Sn+1}=Sでもあるから,nを1つ先に進めればよいからだ)。よってSn+1Sであるが,仮にSn+1Sとしよう。するとSn+2Sでなければならないが,定義により,Sn+2SSn+1SnSn+1Sを割り切らねばならない。Sn+1Sだからそれは矛盾する。こうしてSn+1Sであることも示され,定義によりSSnSn+1Sn+2Sn+3=…となる。つまり,Snはやがて一定値Sになることが示された。

 ここまで来れば,その一定値Sがどういうものであるかも,そんなに難しくはないだろう。dSn−1Sn−2の公約数とすると,Sn−1Sn−2が奇数だからdも奇数である。dSn−1Sn−2の約数でもあるから,定義によりSnも割り切る。逆に,dSnSn−1の公約数であるとすれば,dSn−2cSnSn−1cは整数)の約数でもある。つまり,abの最大公約数をgcd{ab}と表すとすると,gcd{Sn−1Sn−2}=gcd{SnSn−1}だから,gcd{Sn+1Sn}はnを通じて不変である。nが十分大きければgcd{S2S1}=gcd{S3S2}=…=gcd{Sn+1Sn}=Sより,一定値SS1S2の最大公約数であることがわかる。

 以上より,2人がもらえる銀貨の枚数はやがて2人が1週目と2週目に得た銀貨枚数の最大公約数となり,以降は変化しなくなることがわかった。ということは,この最大公約数をなるべく大きくするのが2人にとって得策となる。50枚以下で異なる枚数というのが条件だから,この場合は45枚と15枚を選ぶと最大公約数が15となり,一番よい。つまり,1週目にダムが45枚を選び,2週目にディーが15枚を選ぶと,あとは毎週15枚の銀貨が小遣いとしてもらえる。

 ああ,そうだ。ディーは最初の週にダムがもらう45枚のうちから15枚を協力報酬として受け取っておくのがいい。もちろんダムがそれに応じないということもありうるが,その場合は,ディーは次週に15枚以外の枚数を選んで報復することが可能で,おそらくこの喧嘩は後手のディーのほうに分がありそうだ。

問題はこちらです