Fussy's Diary

この間の雨で桜もだいぶ散ってしまいました。先週に散歩がてら満開の桜の木が撮影できたので載せておきます。



数学問題botから昔拾った問題です。うまい解き方が見つかったので公開。しかし、合っている保証なしです。

-----

正十角形の各頂点に 1 ～ 3 のいずれかの数を割り当て、それらの総和を S とする。1 が付けられた頂点が 5 個以上あり、かつ S ≤ 19 のとき、1 から S のどの自然数 n も連続する何頂点か ( 1 頂点でもよい ) に付けられた数の和として表せることを示せ ( 第 29 回シュプリンガー数学コンテスト )

1 が 5 つ以上あるので、残りの頂点は S ≤ 14 の範囲で割り当てる必要があります。従って、残りの頂点が全て 3 になる場合は除外できます。
まず、1 だけで構成された場合を考えると明らかに成り立ちます。次に、1 と 2 だけで構成されている場合を考えます。但し、1 は少なくとも 1 つは存在するとします。全体での和は S になるので、この中からどれか一つだけ 1 の頂点を除外すると、和が S - 1 になる連続した部分が得られます。その部分の両端には 1 か 2 が存在するので、

1) 1 があればその頂点を外し、
2) 2 しかかなければいずれかを外して前に除外した 1 を復活する

ことを繰り返します。このとき、最初に除外した頂点が 1 で、手順から少なくとも片側には前に 1 を除外したか、1 が復活して残っているので、前者なら 2) の手順が可能であり、後者なら 1) の手順が可能です。従って、1), 2) の手順は必ずできることが保証され、この場合は少なくとも一つの 1 があれば成り立ちます。

次に、3 を含めた場合を考えます。3 は最大でも 4 つしか含められないので、S が最大となる場合は 2 が一つ、3 が 4 つ含まれる場合です。そのため、必ずどこかに 1 が連続して二つ並んだ部分 { 1 1 } か 2 が 1 に挟まれた部分 { 1 2 1 } が存在します。なぜなら、1 以外の数を x としたとき、1 が連続しない並べ方は { 1 x 1 x 1 x 1 x 1 x } しかなく、x の少なくとも一つは 2 だからです。

まず、{ 1 1 } の場合を考えると、最初にこの部分を除外すれば残り 8 つの頂点が残ります。両端のうち片側のみに着目し、1 ならそれを除外すると和が一つ少ない部分が得られます。また、2 の場合はそれを除外して { 1 1 } を復活させると和が同数の部分になります。この後、1 を一つずつ除外すれば、和が 2 つ少ない部分まで得られることになります。3 だった場合はそれを除外して { 1 1 } を復活させると和が一つ少ない部分が得られ、2 の場合と同様の手順で和が 3 つ少ない部分まで得られます。端に除外された { 1 1 } があることが保証されているので、これは最後まで進めることができ、成り立つことが確認できます。

最後に { 1 2 1 } を持つ場合、除外する代わりに、この部分から片方向に順番に生成する方向で考えます。このとき、最初は 1 以外の数で、その後 1 とそれ以外の数が交互に得られることを考慮すると、次の数が 2 だったときは { 1 2 1 } の端の 1 を除外してからもう片側の 2 をつなぎ、次に先ほど除外した 1 をつなげば順番に 2 だけ大きな和まで生成することができます。また、3 の場合は端の { 1 2 } を除外して 3 をつなぎ、3 の次にある 1 をさらにつなぎます。今度は今つないだ 1 を除外して { 1 2 } の中の 2 だけをつなぎ、次は両端に残った 1 を順番につないでいきます。この操作によって、全ての和について連続した部分を生成することが可能となります。

以上から、命題が成り立つことが示されました。