平成１８年３月１２日
[流れ星]
第16９回数学的な応募問題解答
＜解答募集期間：３月１２日〜４月２日
［糸かけ］
皆さん、ここにベニヤ板があり、円周上に適当にｎ本の釘を打ちます。このｎ本の釘にもれなく糸で結び、どの糸も交わることのないように糸をかけていきます。ただし、逆向きにたどってかけた場合は同じと考えます。
例えば、釘が３本のときは、順に釘に番号をつけて、１→２→３ 、１→３→２ 、２→１→３ の３通りに糸かけができます。
では、ここで問題です。
問題１：ｎ＝４のとき、何通りになるか。
問題２：ｎ＝５のとき、何通りになるか。
問題３：ｎ＝６のとき、何通りになるか。
問題４：一般に、ｎ本の場合は、何通りになるか。
次に、円周上に等間隔にｎ本の釘を打ちます。このｎ本の釘にもれなく糸で結び、どの糸も交わることのないように糸をかけていきます。ただし、逆向きにたどってかけた場合は同じと考えます。
さらに、ベニヤ板を回転したり、裏返したりして同じ形の糸かけの場合は同じ種類と考えて、異なった形の糸かけが全部で何種類できるか考えます。例えば釘が３本のときは、１種類しかありません。ここから問題です。
問題５：ｎ＝４のとき、何種類になるか。
問題６：ｎ＝５のとき、何種類になるか。
問題７：ｎ＝６のとき、何種類になるか。
問題８：一般に、ｎ本の場合は、何種類になるか。 作問にあたりヒントになった作品は「糸かけ」です。
NO1「MK」 3/13 19時52分受信 更新4/2
＜コメント：今週も何とか解答だけできました。他の解答者の方々のように、詳しい解説を入れるだけの力もないため、毎回、本当に解答だけです。＞
問１．８通り
問２．２０通り
問３．４８通り
問４．ｎ×２n−3通り
問５．２通り
問６．３通り
NO2「kashiwagi｣3/16 08時31分受信
更新4/2
169回解答
問1
8
問2
20
問3
48
問4
点3 2-1
点4 4-3-1
点5 8-7-4-1
点6 16-15-11-5-1 と俵積みで増えるので
点がｎ個の時は ｎ・2ｎ-3 となる。
問5 2通り
問6 3通り
問7 6通り
問8 ｎが奇数の時 
（ｎ-2） 但し、ｎ≧5
ｎが偶数の時 
（ｎ-3） 但し、ｎ≧6
NO3「Toru」 3/16 14時30分受信 更新4/2
＜コメント：第１６９回解答を送ります。 逆からたどったり、裏返したりとかなり混乱しました。
もっとスッキリした解答もありそうですが＞
糸が交差しないことから、すでに糸でつながっているところを一固まりに考えて、
その両隣りのどちらかに、糸をのばすことになります。
問題１ 1-2-3-4,1-2-4-3,1-4-2-3,1-4-3-2,2-1-3-4,2-1-4-3,2-3-1-4, 3-2-1-4の８
通り
問題２ 1からはじまるものだけ数えると
1-2-3-4-5,1-2-3-5-4,1-2-5-3-4,1-2-5-4-3,1-5-2-3-4,1-5-2-4-3,1-5-4-2-3,1-5-4
-3-2
の８通り、2,3,4,5からはじまるものも同様で8x5=40通りだが、逆向きに数えるもの
がペアになっているから、２で割って ２０通り
問題３ 1からはじまる場合 次は2,6の２通り、それぞれについて、次も２通りと考
えて行くと最後の一つ前までは２通りで最後のものは1通りに決まる。
すなわち２x２x２x２x１=16通り 2,3,4,5,6からはじまる場合も同様で
6x16=96通り 逆向きのものを重複して数えているから96/2=48（通り）
問題４ 問題３と同じに考えて
最初がn通り 以下２番目〜(n-1)番目までは２通り n番目は1通り、重複を２で割っ
て、 n・2^(n-2)／2=n・2^(n-3) （通り）
問題５ 回転してよいので、問題１の答えのうち１からはじまるものだけ、さらに裏
返してよいから1-2のものだけ考える、、1-2-3-4、1-2-4-3は明らかに違う形だから、
この２通り
問題６ まず向きのある場合で考えてみると、
回転してよいので５個のうちの先頭の３つの位置を、かたまりとして、1,2,3の位置
に固定してよい３番目は１or３位置になるが、裏返してもよいことから、3番目のも
のを３の位置に固定してよい。
これより1-2-3-4-5,2-1-3-4-5,1-2-3-5-4,2-1-3-5-4の４種類が考えられる。3をと
おる直径を軸に裏返すと逆からたどったものにできる。
これにより、対称型でない2-1-3-4-5は、1-2-3-5-4となるので重複して数えているこ
とになり、これを除いて３通り
問題７ まず向きのある場合で考える、問題６同様、先頭の３つをかたまりとして、
1,2,3の位置に固定、さらに３番目を３の位置に固定してよい。これで
1-2-3-4-5-6,2-1-3-4-5-6,1-2-3-4-6-5,2-1-3-4-6-5,1-2-3-6-4-5,2-1-3-6-4-5,1-
2-3-6-5-4,2-1-3-6-5-4の８通りが考えられるが、このうち3-4のものは3-4の中点を
とおる直径を軸に裏返す、3-6のものは3-6を１８０度回転させることで、逆からたどっ
たものにできる。 このどちらかで、同型になるもの
は1-2-3-4-5-6,1-2-3-6-5-4,2-1-3-4-6-5,2-1-3-6-4-5で、残りは２回ずつ重複して
数えていることになるので、4+4/2=6 (通り)
問題８
n=2m+1の時(m=1,2,---) 問題６と同様に考えて,m+1個目をm+1の位置、その前の最
初のm個を1〜mにならべる方法が、2^(m-1)通りのそれぞれに対し、残りm個の
２^(m-1)通りうち、対称型となるのは1通りで、
2^(m-1)x（1+ (2^(m-1) -1)/2）=2^(2m-3)+2^(m-2) （通り）
n=2mの時(m=2,3,----) 問題７と同様に
m番目をmの位置、その前のm-1個の並べ方は2^(m-2)、残りのm個の並べ方は2^(m-1)通
りであるが、このうち対称型になるのは、１８０°回転と裏返しでそれぞれ２通り。
それ以外は、逆から数えると２回ずつ重複して数えることになるので、
2^(m-2)x（2+(2^(m-1)-2)/2）=2^2(m-2)+2^(m-2) （通り）
両方の場合を合わせて表現すれば 2^(n-4)+2^([n/2]-2) []はガウス記号
(n=3,4,5,----)
NO4「uchinyan」3/17 18時04分受信 更新4/2
第１６９回数学的な応募問題への解答［糸かけ］
前提：
点の番号のつけ方を、反時計回りとしておきます。
問題1：
まず、ナイーブな方法から。
例えば、始点 1、終点 4 の場合は、
1 -> 2 -> 3 -> 4, 1 -> 3 -> 2 -> 4
ですが、後者は交差するのでダメです。
以下では、交差しない場合を OK、交差する場合を NG と略記します。
同様にして、始点、終点を変えていくと、
1 -> 2 -> 3 -> 4 : OK, 1 -> 3 -> 2 ->
4 : NG
1 -> 2 -> 4 -> 3 : OK, 1 -> 4 -> 2 ->
3 : OK
1 -> 3 -> 4 -> 2 : NG, 1 -> 4 -> 3 ->
2 : OK
2 -> 1 -> 3 -> 4 : OK, 2 -> 3 -> 1 ->
4 : OK
2 -> 1 -> 4 -> 3 : OK, 2 -> 4 -> 1 ->
3 : NG
2 -> 3 -> 4 -> 1 : OK, 2 -> 4 -> 3 ->
1 : NG
3 -> 1 -> 2 -> 4 : NG, 3 -> 2 -> 1 ->
4 : OK
3 -> 1 -> 4 -> 2 : NG, 3 -> 4 -> 1 ->
2 : OK
3 -> 2 -> 4 -> 1 : OK, 3 -> 4 -> 2 ->
1 : OK
4 -> 1 -> 2 -> 3 : OK, 4 -> 2 -> 1 ->
3 : NG
4 -> 1 -> 3 -> 2 : OK, 4 -> 3 -> 1 ->
2 : OK
4 -> 2 -> 3 -> 1 : NG, 4 -> 3 -> 2 ->
1 : OK
で、この段階での OK は 16 通りですが、このうち、逆方向のものが必ずあるので、
これを除いて、半分の 16/2 = 8 通り、になります。
問題1の考察と問題2への準備：
ここで、後のために、見方を少し変えてみます。
n = 3 のときは、
1 -> 2 -> 3, 1 -> 3 -> 2, 2 -> 1 -> 3
の 3 通りでした。これを、敢えて逆向き、
3 -> 2 -> 1, 2 -> 3 -> 1, 3 -> 1 -> 2
の 3 通りも許すと、全体で 6 通りになります。
n = 4 のときは、これらに 4 を追加すると、考えることができます。
具体的な追加の方法には、次が考えられます。
・最初に追加
4 -> 1 -> 2 -> 3, 4 -> 1 -> 3 -> 2, 4
-> 2 -> 1 -> 3
4 -> 3 -> 2 -> 1, 4 -> 2 -> 3 -> 1, 4
-> 3 -> 1 -> 2
・1番目と2番目の間に追加
1 -> 4 -> 2 -> 3, 1 -> 4 -> 3 -> 2, 2
-> 4 -> 1 -> 3
3 -> 4 -> 2 -> 1, 2 -> 4 -> 3 -> 1, 3
-> 4 -> 1 -> 2
・1番目と2番目の間に追加
1 -> 2 -> 4 -> 3, 1 -> 3 -> 4 -> 2, 2
-> 1 -> 4 -> 3
3 -> 2 -> 4 -> 1, 2 -> 3 -> 4 -> 1, 3
-> 1 -> 4 -> 2
・最後に追加
1 -> 2 -> 3 -> 4, 1 -> 3 -> 2 -> 4, 2
-> 1 -> 3 -> 4
3 -> 2 -> 1 -> 4, 2 -> 3 -> 1 -> 4, 3
-> 1 -> 2 -> 4
これは、よく見ると、先ほどのナイーブな方法のすべての場合を尽くしています。
これは当然で、n = 3 のすべての場合に、すべての可能な 4 の挿入を行ったからです。
一方、n = 4 の構成方法として、次のような考え方も可能です。
・1, 2, 3 に 4 を追加する。今、行った方法。
・1, 2, 4 に 3 を追加する。
・1, 3, 4 に 2 を追加する。
・2, 3, 4 に 1 を追加する。
もちろん、この四つは同じものを与えますが、これは、同じものを違った見方で分類できることを
示唆しています。つまり、ちょっと変えて、
・1, 2, 3 の最後に 4 を追加する。
・1, 2, 4 の最後に 3 を追加する。これは、上記の 3 <-> 4 の入れ替えと同じ。
・1, 3, 4 の最後に 2 を追加する。これは、上記の 2 <-> 3 の入れ替えと同じ。
・2, 3, 4 の最後に 1 を追加する。これは、上記の 1 <-> 2 の入れ替えと同じ。
とすることもできます。これらは、四つすべて行って、重複なくすべてを与えます。
これらは、1, 2, 3, 4 の順列と同じなので、1, 2, 3 の順列に 4 を追加することと同じで、
それは、1, 2, 3 の各順列の最後に 4 を追加して、
例えば、1 => 2, 2 => 3, 3 => 4, 4 => 1 と置き換える、つまり、
1 -> 2 -> 3 -> 4 => 2 -> 3 -> 4 ->
1 => 3 -> 4 -> 1 -> 2 => 4 -> 1 -> 2 -> 3
2 -> 1 -> 3 -> 4 => 3 -> 2 -> 4 ->
1 => 4 -> 3 -> 1 -> 2 => 1 -> 4 -> 2 -> 3
などと隣の数字へ置換すると考えることもできます。
特にこの置換は、図形の回転をしているのと同じなので、OK、NG は変化しません。
そこで、以下ではこの置換を使ったものを採用することにします。
結局、以上のことから、n = 4 を考えるには、次のように考えていいことになります。
・n = 3 の場合の 1, 2, 3 の場合の並びの逆向きも許したものの最後に 4 を追加する。
・それらの OK、NG を具体的に調べる。
当然ですが、n = 3 の場合で NG のものは NG です。(n = 3 ではないのですが。)
・OK だったものに隣の数字への置換をする。
・逆向きを除き、半分にする。
この考え方は、n が 4 であることを何も使っていないので、一般の場合にも成立します。
一応、この考え方を使って、n = 4 の場合を求めておきましょう。
n = 3 の場合は、逆向きも許して次の 6 通りです。
1 -> 2 -> 3, 1 -> 3 -> 2, 2 -> 1 -> 3
3 -> 2 -> 1, 2 -> 3 -> 1, 3 -> 1 -> 2
4 を最後に追加して、OK、NG を判定します。
1 -> 2 -> 3 -> 4 : OK
1 -> 3 -> 2 -> 4 : NG
2 -> 1 -> 3 -> 4 : OK
3 -> 2 -> 1 -> 4 : OK
2 -> 3 -> 1 -> 4 : OK
3 -> 1 -> 2 -> 4 : NG
OK は、4 通りあります。隣の数字への置換によって、4 倍になるので、逆向きを除いて、
4 * 4 / 2 = 8 通り。
確かに、答えを再現します。
この考え方を使って、n = 5 を考えてみます。
問題2：
n = 4 の場合は、逆方向も許すと、
1 -> 2 -> 3 -> 4 : OK
1 -> 2 -> 4 -> 3 : OK, 1 -> 4 -> 2 ->
3 : OK
1 -> 4 -> 3 -> 2 : OK
2 -> 1 -> 3 -> 4 : OK, 2 -> 3 -> 1 ->
4 : OK
2 -> 1 -> 4 -> 3 : OK
2 -> 3 -> 4 -> 1 : OK
3 -> 2 -> 1 -> 4 : OK
3 -> 4 -> 1 -> 2 : OK
3 -> 2 -> 4 -> 1 : OK, 3 -> 4 -> 2 ->
1 : OK
4 -> 1 -> 2 -> 3 : OK
4 -> 1 -> 3 -> 2 : OK, 4 -> 3 -> 1 ->
2 : OK
4 -> 3 -> 2 -> 1 : OK
の 16 通りでした。そこで、最後に 5 を追加して、OK、NGを判定すると、
1 -> 2 -> 3 -> 4 -> 5 : OK
1 -> 2 -> 4 -> 3 -> 5 : NG
1 -> 4 -> 2 -> 3 -> 5 : NG
1 -> 4 -> 3 -> 2 -> 5 : NG
2 -> 1 -> 3 -> 4 -> 5 : OK
2 -> 3 -> 1 -> 4 -> 5 : OK
2 -> 1 -> 4 -> 3 -> 5 : NG
2 -> 3 -> 4 -> 1 -> 5 : OK
3 -> 2 -> 1 -> 4 -> 5 : OK
3 -> 4 -> 1 -> 2 -> 5 : NG
3 -> 2 -> 4 -> 1 -> 5 : OK
3 -> 4 -> 2 -> 1 -> 5 : OK
4 -> 1 -> 2 -> 3 -> 5 : NG
4 -> 1 -> 3 -> 2 -> 5 : NG
4 -> 3 -> 1 -> 2 -> 5 : NG
4 -> 3 -> 2 -> 1 -> 5 : OK
より、OK は、8 通り。隣の数字への置換は、5 通りなので、逆向きを除いて、結局、
n = 5 では、8 * 5 / 2 = 20 通り。
問題2の考察と問題3への準備：
n = 5 の場合の可能なものを具体的に並べて調べるのは、少し大変です。
何通りか、ということだけでいいので、それが分かるうまい方法を模索します。
問題2：から分かるように、この作業で大変なので、最後に 5 を追加した後の OK、NG の判定です。
しかし、結果をよく見てみると、OK なのは 5 と隣り合う点 1, 4 が最後に来ている場合だけです。
これは実は当然で、もし、最後が 2 だったら、2 -> 5 で 1 と 3, 4 は反対側になります。
5 は新たに最後になり既に 2 と結ばれているので、1 は 5 とは結ばれません。
また、1 が最後だった 2 と結ばれているとすると、1 は途中にあるこになるので、
1 は、3 又は 4 とも結ばれなければなりません。
1 が 2 と結ばれていないとすると、もちろん、1 は、3 又は 4 と結ばれなければなりません。
結局、2 -> 5 の反対側にある 1 と 3 又は 4 が結ばれなければならないので、
交差ができてしまいます。
つまり、最後が 2 の場合は NG です。同様にして、最後が 3 の場合も NG です。
結局、OK なのは、5 と隣り合う点が最後に来ている場合だけ、ということが分かりました。
このことは、一般の n でも同様です。
n = 5 の場合は、今までの議論でほとんど明らかですが、一応まとめておきましょう。
5 と隣り合う点 1, 4 が n = 4 で OK の最後に来ている場合を考えます。
4 が最後の場合は、問題1の考察と問題2への準備：より、逆向きを許して 4 通りでした。
1 が最後の場合は、4 が最後の場合の隣の数字への置換でそれぞれ 1 通りずつ得られるので、4 通りです。
したがって、n = 5 の OK は、それらの合計 8 通りで、当然、先ほどの場合と一致します。
この方法で、n = 6 を考えてみます。
問題3：
n = 6 で OK になるのは、n = 5 の OK のうち、6 と隣り合う点 1, 5 が最後に来ている場合だけです。
5 が最後に来るのは、問題2：より 8 通り。
1 が最後に来るのは、それぞれの並びに対して隣の数字への置換をすると 1 通りずつあるので、8 通りです。
したがって、n = 6 の OK は、合計して 16 通りになります。
そこで、n = 6 の隣の数字への置換で 6 倍になり、逆方向を除いて半分になるので、
16 * 6 / 2 = 48 通り。
問題4：
問題3：までで明らかだと思いますが、求める場合の数を f(n) 通りとして漸化式が作れます。
n のときの OK が、2 * f(n) * 1/n * 1/2 = f(n)/n 通り、
n-1 のときの OK が、f(n-1)/(n-1) 通り、ですが、
n のときの OK は、n-1 のときの OK、又はその隣の数字への置換で最後が 1 のものに、
n を最後に追加して得られます。そこで、
f(n)/n = 2 * f(n-1)/(n-1)
ただし、n >= 4, f(3) = 3 です。これから、
f(n)/n = 2 * f(n-1)/(n-1) = ... = 2^(n-3) * f(3)/3 =
2^(n-3)
f(n) = n * 2^(n-3) 通り
になります。
今までの考察：
今までの議論を見直してみました。冗長で少し論理的に甘いですが、誤りはないようです。
ただ、問題5：以下の対応のこともあるので、少し見方を変えて、命題としてまとめておきましょう。
命題：
平面上に円があり、円周上に n 個、ただし n >= 3、の異なる点がある。
それらのうちから、始点と終点とを決めて、始点から終点へとそれ以外の点を
一度ずつ通るように線を引く。ただし、始点と終点とは結ばない。
このとき、線が交差しないような結び方で、結ぶ向きだけが異なるものを同じとすると、
その場合の数 f(n) は、
f(n) = n * 2^(n-3)
である。
(証明)
円周上の点の一つを 1 と番号をつけ、反時計回りに 2, 3, ..., n とします。
f(n) の条件を満たす点の結び方で、ただし逆向きを区別しないもの、の集合を S とします。
逆向きを区別しないとしたのは、後の問題5：以降を意識しています。
今、1 => 2, 2 => 3, ..., n-1 => n, n =>
1 という変換σを考えます。
これは、図形的には、回転を表しています。
回転によって交差する交差しないは変化しないので、この変換によって S は不変です。
より具体的には、始点 1 の結び方を始点 2 の結び方に変換します。
また、逆変換で元に戻り、しかも、n 回の回転で元に戻ります。
したがって、σは、S を始点 i に注目した n 個の部分集合 S(i) に分割し、
S(i) の各要素は、j not= i となる S(j) の要素と一対一に対応します。
そこで、S(i) は S(1) からσを使って構成でき、S(i) の要素の個数と
S(1) の要素の個数とは一致し、S の要素の個数は S(1) の n 倍になります。
つまり、S(1) を考えれば十分なことが分かります。
そこで、以下では S(1)、始点を 1 に固定した結び方、について考えます。
このとき、
(A) 始点を 1 に固定した場合で交差がないものは、1 と、1 に隣り合う点 2, n を結んだ場合に限る。
ということがいえます。これは、次のようにして分かります。
n = 3 の場合は、2, n (= 3) が 1 の隣にあるので明らかです。
n >= 4 の場合は、2, n でない点 k が取れるので、1 と k を結ぶと仮定します。
すると、少なくとも 2, n は、線分 1k に関して反対側にあり、
線分 1k は円周上の 1, k 以外の点を二つの異なる領域に分けることが分かります。
したがって、k から終点まで順次すべての点を結んでいくと、
どこかで必ず線分 1k をまたがる線を引かなければなりません。これは交差があることを意味します。
これで、(A)が分かりました。
なお、今は始点に関して議論しましたが、一般には、結び方は逆方向もあるので、
同様の議論を行うと、終点に関して
(B) 終点を a に固定した場合で交差がないものは、a と、a に隣り合う点 a-1, a+1 を結んだ場合に限る。
もいえます。これは今は使いませんが、後で考える問題8：で重要になります。
(この(B)は、実は、問題2の考察と問題3への準備：で議論したことと同じです。)
さて、こうなると、線分 12 又は 1n が最初にあることになりますが、これは、もちろん、
他の線と交差しないので、交差する交差しないは、2 〜 n で考えればいいことになります。
つまり、n-1 個の点で考えることに帰着します。この場合の始点、2 又は n ですが、
これを先ほどの 1 と思えば、同様の議論が展開でき、以下、これを繰り返せます。
このことから、f(n) が求められます。
まず、始点の選択に n 通り。
始点を 1 に固定したとき、交差がなく 1 と結べる点は 1 の両隣の 2 又は n なので 2 通り。
交差に関係しない 1 を除いたとき、残りの n-1 個の点の始点は 2 又は n ですが、
これらと交差がなく結べる点はそれぞれの両隣で 2 通りずつ。
以下同様に最後の一点が残るまで 2 通りずつです。
その回数は、始点と終点とを除いた n-2 回なので、全部で、n * 2^(n-2) 通り。
ただし、f(n) は逆向きを区別しないので半分にして、
f(n) = n * 2^(n-2) * 1/2 = n * 2^(n-3) 通り
になります。
(証明終)
この証明のアイディアは今までの議論と同じですが、問題5：以降のことも考えて、
回転対称性で始点 1 を固定し、始点に関する(A)を使うように修正しています。
問題5への準備：
さて、これまでは、対称性を考えない一般の場合でした。
しかし、問題5：以降は、対称性を考慮しなければなりません。
これを少し考察しておきます。
円周上に等間隔に並んだ n 個の点、釘、は、正ｎ角形を構成します。
そこで、明らかに、ｎ回の回転対称性があります。
また、正ｎ角形は、頂点と正ｎ角形の中心とを結ぶｎ本の軸に関する軸対称性をもっています。
n が偶数の場合には、正ｎ角形の辺に垂直で正ｎ角形の中心を通る軸に関する対称性もあります。
さらに、今までも考えてきた、結ぶ向きの対称性があります。
まず、回転対称性です。
これは、今までの議論で言うところの、隣の数字への置換、σ、に対応します。
したがって、隣の数字へ置換したものを等価とみなすので、f(n) を n で割る必要があります。
回転対称性を除くことは、始点を点 1 に固定することを意味します。
したがって、以下では、始点を 1 に固定して考えていいことになります。
次に、軸対称性です。
ナイーブには、これによって、2^n の重複があるのですが、回転対称性を除いたので、
点 1 は動かさないようにする必要があります。そうしないと、重複してしまいます。
この場合、軸対称性は、点 1 を通る軸に関する対称性に限定されます。
これによって、半分になります。
このとき、始点 1 と結ばれる点は、命題の(A)より 2 か n ですが、2 に限定されます。
なお、n が偶数の場合には、正ｎ角形の辺に垂直で正ｎ角形の中心を通る軸に関する対称性もありました。
しかしこれは、例えば、n = 6 で、
1 <==> 6, 2 <==> 5, 3 <==> 4
ですが、ます、回転
1 => 2, 2 => 3, 3 => 4, 4 => 5, 5 => 6,
6 => 1
を行って、1 軸対称
1 <=> 1, 2 <=> 6, 3 <=> 5, 4
<=> 4
を行えば、合成の変換として、
1 <==> 6, 2 <==> 5, 3 <==> 4
が実現できるので考えなくていいです。一般の偶数の n でも同様です。
ここまでで、結ぶ向きの対称性は除いていない、つまり、逆向きを許しているので、
2 * f(n) * 1/n * 1/2 = f(n)/n = 2^(n-3)
になります。
さて、残るは結ぶ向きの対称性です。これが結構面倒です。
f(n) は逆向きのものは除いていますが、実は、今考えている対称性に含まれている可能性があります。
実は、最初の解答では、ここで間違えて、水の流れさんのご指摘を受けたことを白状しておきます (^^;
なお、以降では、記述を簡単にするために、1 -> 2 -> 3 -> 4
-> 5 などを矢印を除いて、
12345 と書くことにします。
また、逆向きの対応を <->、回転移動を =>、軸対称移動を <=>、と書き、
結果として生じる対応を == と書くことにします。
さて、例えば、n = 5 の場合で逆向きを考えて見ましょう。
この場合は、回転対称性、1 軸対称性を除くと、命題の(A)も考慮して、
12345, 12354, 12534, 12543
ここで、逆向きは、例えば、
12345 <-> 54321
ですが、これは元の並びで、2 <=> 5, 3 <=> 4 と 1 軸に対して対称にして、
それを、1 => 5, 2 => 1, 3 => 2, 4 => 3, 5
=> 4 と回転した場合と同じです。
12345 <=> 15432 => 54321
これは言い換えると、最初の並びを逆向きにして、始点を 1 にするように反時計回りに回転し、
始点 1 と結ばれている点が 5 のときは 2 になるように 1 軸対称性で変換すると、元に戻る、
ことを意味しています。以降では、この操作を「操作(O)」と呼ぶことにします。
実際、
12345 <-> 54321 => 15432 <=> 12345
となって、元に戻ります。このような場合は、重複がないことを意味します。しかし、
12354 <-> 45321 => 12543
なので、
12354 == 12543
で、この二つは、実は同じもので重複していることを意味します。
これは除かないといけません。
このように、逆方向は、回転対称及び軸対称に紛れ込んでいるので、
一度、逆方向を許してから、回転対称、軸対称との関係を考慮して慎重に除く必要があります。
しかしそれを一般的に考察する前に、様子を探るために具体例をやってみます。
問題5：
始点を点 1 に固定し実際に図を書いて調べてみると、2 種類、になります。
問題5の考察：
これを先ほどの考察の結果を使ってみると．．．
問題1：から、f(4) = 8 通り、でした。
これを一度逆方向を許して、回転対称性、1 軸対称性を除くと、
8 * 2 * 1/4 * 1/2 = 2
になります。これは、実際には、
1234, 1243
です。操作(O)を行うと、
1234 -> 4321 => 1432 <=> 1234
1243 -> 3421 => 1243
となり、どちらも不変です。
そこで、2 - 0 = 2 種類、になります。
問題6：
始点を点 1 に固定し実際に図を書いて調べてみると、3 種類、になります。
問題6の考察：
これを先ほどの考察の結果を使ってみると．．．
問題2：から、f(5) = 20 通り、でした。
これを一度逆方向を許して、回転対称性、1 軸対称性を除くと、
20 * 2 * 1/5 * 1/2 = 4
になります。これは、実際に図を書いて考えた場合と一致しません！
操作(O)を使って、具体的に調べてみます。
まず、4 通りは、
12345, 12354, 12534, 12543
です。操作(O)を行うと、
12345 <-> 54321 => 15432 <=> 12345
12354 <-> 45321 => 12543
12534 <-> 43521 => 15243 <=> 12534
12543 <-> 34521 => 12354
となり、
12354 == 12543
で、この二つが移り合います。これが原因です。なお、それ以外は元に戻ります。
結局、4 - 1 = 3 種類、が正しいわけです。
問題7：
始点を点 1 に固定し実際に図を書いて調べてみると、6 種類、になります。
問題7の考察：
問題3：から、f(6) = 48 通り、でした。
これを一度逆方向を許して、回転対称性、1 軸対称性を除くと、
48 * 2 * 1/6 * 1/2 = 8
になりますが、これは、実際に図を書いて考えた場合と一致しません！
同じく操作(O)を使って具体的に調べてみると、
123456 <-> 654321 => 165432 <=> 123456
123465 <-> 564321 => 126543
123645 <-> 546321 => 162543 <=> 126345
123654 <-> 456321 => 123654
126345 <-> 543621 => 165243 <=> 123645
126354 <-> 453521 => 126354
126534 <-> 435621 => 162354 <=> 126534
126543 <-> 345621 => 123465
となり、
123465 == 126543
123645 == 126345
がいえます。そこで、
結局、8 - 2 = 6 種類、になります。
これは、実際に図を書いて考えた場合と一致します。
問題8への準備：
もう少し調べてみます。
・n = 7
1234567 <-> 7654321 => 1765432 <=>
1234567
1234576 <-> 6754321 => 1276543
1234756 <-> 6574321 => 1726543 <=>
1273456
1234765 <-> 5674321 => 1237654
1237456 <-> 6547321 => 1762543 <=>
1237456
1237465 <-> 5647321 => 1273654
1237645 <-> 5467321 => 1723654 <=>
1276345
1237654 <-> 4567321 => 1234765
1273456 <-> 6543721 => 1765243 <=>
1234756
1273465 <-> 5643721 => 1276354
1273645 <-> 5463721 => 1726354 <=>
1273645
1273654 <-> 4563721 => 1237465
1276345 <-> 5436721 => 1762354 <=>
1237645
1276354 <-> 4536721 => 1273465
1276534 <-> 4356721 => 1723465 <=>
1276534
1276543 <-> 3456721 => 1234576
なので、
1234576 == 1276543
1234756 == 1273456
1234765 == 1237654
1237465 == 1273654
1237645 == 1276345
1273465 == 1276354
となり、6 個が重複します。そこで、これを引いて、
2^(7-3) - 6 = 2^4 - 6 = 16 - 6 = 10 種類
・n = 8
12345678 <-> 87654321 => 18765432 <=>
12345678
12345687 <-> 78654321 => 12876543
12345867 <-> 76854321 => 18276543 <=>
12834567
12345876 <-> 67854321 => 12387654
12348567 <-> 76584321 => 18726543 <=>
12384567
12348576 <-> 67584321 => 12837654
12348756 <-> 65784321 => 18237654 <=>
12873456
12348765 <-> 56784321 => 12348765
12384567 <-> 76548321 => 18762543 <=>
12348567
12384576 <-> 67548321 => 12873654
12384756 <-> 65748321 => 18273654 <=>
12837456
12384765 <-> 56748321 => 12384765
12387456 <-> 65478321 => 18723654 <=>
12387456
12387465 <-> 56478321 => 12834765
12387645 <-> 54678321 => 18234765 <=>
12876345
12387654 <-> 45678321 => 12345876
12834567 <-> 76543821 => 18765243 <=>
12345867
12834576 <-> 67543821 => 12876354
12834756 <-> 65743821 => 18276354 <=>
12834756
12834765 <-> 56743821 => 12387465
12837456 <-> 65473821 => 18726354 <=>
12384756
12837465 <-> 56473821 => 12837465
12837645 <-> 54673821 => 18237465 <=> 12873645
12837654 <-> 45673821 => 12348576
12873456 <-> 65437821 => 18762354 <=>
12348756
12873465 <-> 56437821 => 12873465
12873645 <-> 54637821 => 18273465 <=>
12837645
12873654 <-> 45637821 => 12384576
12876345 <-> 54367821 => 18723465 <=>
12387645
12876354 <-> 45367821 => 12834576
12876534 <-> 43567821 => 18234576 <=>
12876534
12876543 <-> 34567821 => 12345687
なので、
12345687 == 12876543
12345867 == 12834567
12345876 == 12387654
12348567 == 12384567
12348576 == 12837654
12348756 == 12873456
12384576 == 12873654
12384756 == 12837456
12387465 == 12834765
12387645 == 12876345
12834576 == 12876354
となり、重複は 12 個なので、
2^(8-3) - 12 = 2^5 - 12 = 32 - 12 = 20 種類
ここまでくると、不変な方を数えた方が早そうです。これは、8 個なので、
(2^(8-3) + 8)/2 = 2^4 + 4 = 16 + 4 = 20 種類
実際、不変な個数は、n >= 3 に関して、
1, 2, 2, 4, 4, 8, ...
さらによく見ると、(回転)＋(1 軸対称) と書くと、
0+1, 1+1, 0+2, 2+2, 0+4, 4+4, ...
ということは．．．
・n が奇数のとき：g(n) = (2^(n-3) + 2^((n-3)/2))/2 =
2^(n-4) + 2^((n-5)/2)
・n が偶数のとき：g(n) = (2^(n-3) + 2 * 2^((n-4)/2))/2 =
2^(n-4) + 2^((n-4)/2)
かな？
問題8：
求める種類を g(n) 種類としておきます。
円周上に等間隔にある n 個の点は、正ｎ角形を構成します。
そこで、ｎ回の回転対称性、各頂点と中心とを通る軸についての軸対称性があります。
なお、n が偶数の場合には、辺に垂直で中心を通る軸に関する対称性もありますが、
これは、上記の二つの合成で実現できるので考える必要はありません。
さらに、結び方の向きに関する対称性、逆向きをおなじとする、があります。
したがって、これらの対称性で不変なものを除く必要があります。
さて、回転対称性を除くことは、始点を点 1 に固定することを意味します。
そこで、軸対称性は、点 1 を通る軸、1 軸、について考えればよく、
またそうしないと、重複して考えてしまいます。
しかし、1 軸は、n が奇数の場合と偶数の場合とで状況が異なり、
奇数の場合はそれ自身しかありませんが、偶数の場合は、(n/2 + 1) 軸と一致します。
これは、180度の回転対称性の表れと考えることもできますし、
先に注意した軸対称性の重複の可能性とも関係し、後で、重要になってきます。
なお、命題の(A)から分かるように、1 軸対称性を考慮すると、点 1 と結ぶ点を 2 に限定できます。
したがって、すべての結び方に対して、回転対称性を除いて始点 1 を固定し、
次に 1 軸対称性を除くと、始点を 1 とし、1 と 2 を結ぶ結び方、だけが残ります。
そこで、以下では、これに限定して考えればいいことになります。
さて、交差しない結び方で対称性を考えない場合は、問題4：より f(n) でした。
ただし、これは、逆向きを除いています。
そこで、これから、まずは逆向きを許し、回転可能性の自由度を除き点 1 を固定して、
1 軸の対称性を除くと、次のようになります。
2 * f(n) * 1/n * 1/2 = 2 * n * 2^(n-3) * 1/n * 1/2 =
2^(n-3)
しかし、問題5：〜問題7：で見たように、これには、逆向きに絡んだ対称性が残っています。
次にこれを除きます。
点 1 を固定し 1 軸対称性を考慮した結び方の逆向きを考えます。
結び方は、一般に、i を 3 〜 n とし、a(i) の値も 3 〜 n として、
1 -> 2 -> a(3) -> ... -> a(i) -> ...
-> a(n-i+1) -> ... -> a(n-2) -> a(n-1) -> a(n)
と書けます。これに対して、
・並びを逆向きにする。
・始点を 1 にするように反時計回りに回転する。
・始点 1 と結ばれている点が n のときは 2 になるように 1 軸対称性で変換する。
という一連の操作を行います。この操作を、以降では「操作(O)」と呼ぶことにします。
操作(O)によって、最初の結び方の終点が新たに始点 1 になりますが、
命題の(B)及び 1 軸対称移動によって始点 1 と結ばれている点は 2 に限定されます。
そこで、操作(O)によって、新たな結び方が生じることはありません。
さらに、実際に操作(O)を行ってみると、
1 -> 2 -> a(3) -> ... -> a(i) -> ...
-> a(n-i+1) -> ... -> a(n-2) -> a(n-1) -> a(n)
=逆向き=>
a(n) -> a(n-1) -> a(n-2) -> ... -> a(n-i+1)
-> ... -> a(i) -> ... -> a(3) -> 2 -> 1
=回転=>
1 -> 1 - a(n) + a(n-1) -> 1 - a(n) + a(n-2) ->
... -> 1 - a(n) + a(n-i+1) -> ...
-> 1 - a(n) + a(i) -> ... -> 1 - a(n) + a(3)
-> 1 - a(n) + 2 -> 1 - a(n) + 1
=
1 -> 1 - a(n) + a(n-1) -> 1 - a(n) + a(n-2) ->
... -> 1 - a(n) + a(n-i+1) -> ...
-> 1 - a(n) + a(i) -> ... -> 1 - a(n) + a(3)
-> 3 - a(n) -> 2 - a(n)
=軸対称=>
n + 2 - 1 -> n + 2 - 1 + a(n) - a(n-1) -> n + 2 -
1 + a(n) - a(n-2) -> ...
-> n + 2 - 1 + a(n) - a(n-i+1) -> ...
-> n + 2 - 1 + a(n) - a(i) -> ...
-> n + 2 - 1 + a(n) - a(3) -> n + 2 - 3 + a(n)
-> n + 2 - 2 + a(n)
=
1 -> 1 + a(n) - a(n-1) -> 1 + a(n) - a(n-2) ->
... -> 1 + a(n) - a(n-i+1) -> ...
-> 1 + a(n) - a(i) -> ... -> 1 + a(n) - a(3)
-> - 1 + a(n) -> a(n)
ただし、1 軸対称移動は、回転後に 1 -> 2 -> ... となっている場合には不要です。
また、実際に現れる数字は 1 〜 n なので、適宜、+n, -n を行うとします。つまり、mod
n で考えます。
さて、操作(O)で得られた結果に、再度、操作(O)を行ってみます。すると、
1 軸対称移動を行わなかった場合：
1 -> 1 - a(n) + a(n-1) -> 1 - a(n) + a(n-2) ->
... -> 1 - a(n) + a(n-i+1) -> ...
-> 1 - a(n) + a(i) -> ... -> 1 - a(n) + a(3)
-> 3 - a(n) -> 2 - a(n)
=逆向き=>
2 - a(n) -> 3 - a(n) -> 1 - a(n) + a(3) -> ...
-> 1 - a(n) + a(i) -> ...
-> 1 - a(n) + a(n-i+1) -> ... -> 1 - a(n) +
a(n-2) -> 1 - a(n) + a(n-1) -> 1
=回転=>
1 -> 1 + a(n) - 2 + 3 - a(n) -> 1 + a(n) - 2 + 1
- a(n) + a(3) -> ...
-> 1 + a(n) - 2 + 1 - a(n) + a(i) -> ...
-> 1 + a(n) - 2 + 1 - a(n) + a(n-i+1) -> ...
-> 1 + a(n) - 2 + 1 - a(n) + a(n-2) -> 1 + a(n) -
2 + 1 - a(n) + a(n-1) -> 1 + a(n) - 2 + 1
=
1 -> 2 -> a(3) -> ... -> a(i) -> ...
-> a(n-i+1) -> ... -> a(n-2) ->a(n-1) -> a(n)
で、元に戻ります。
1 軸対称移動を行った場合：
1 -> 1 + a(n) - a(n-1) -> 1 + a(n) - a(n-2) ->
... -> 1 + a(n) - a(n-i+1) -> ...
-> 1 + a(n) - a(i) -> ... -> 1 + a(n) - a(3)
-> - 1 + a(n) -> a(n)
=逆向き=>
a(n) -> - 1 + a(n) -> 1 + a(n) - a(3) -> ...
-> 1 + a(n) - a(i) -> ...
-> 1 + a(n) - a(n-i+1) -> ... -> 1 + a(n) -
a(n-2) -> 1 + a(n) - a(n-1) -> 1
=回転=>
1 -> 1 - a(n) - 1 + a(n) -> 1 - a(n) + 1 + a(n) -
a(3) -> ...
-> 1 - a(n) + 1 + a(n) - a(i) -> ...
-> 1 - a(n) + 1 + a(n) - a(n-i+1) -> ...
-> 1 - a(n) + 1 + a(n) - a(n-2) -> 1 - a(n) + 1 +
a(n) - a(n-1) -> 1 - a(n) + 1
=
1 -> n -> n + 2 - a(3) -> ... -> n + 2 -
a(i) -> ... -> n + 2 - a(n-i+1) -> ...
-> n + 2 - a(n-2) -> n + 2 - a(n-1) -> n + 2 -
a(n)
=軸対称=>
1 -> n + 2 - n -> n + 2 - n - 2 + a(3) -> ...
-> n + 2 - n - 2 + a(i) -> ...
-> n + 2 - n - 2 + a(n-i+1) -> ...
-> n + 2 - n - 2 + a(n-2) -> n + 2 - n - 2 +
a(n-1) -> n + 2 - n - 2 + a(n)
=
1 -> 2 -> a(3) -> ... -> a(i) -> ...
-> a(n-i+1) -> ... -> a(n-2) -> a(n-1) -> a(n)
となって、やはり、元に戻ります。
つまり、操作(O)を二回行うと元に戻ります。
結局、始点を 1 とし、1 と 2 とを結んだ結び方に、
操作(O)を一回行うと同じ種類の結び方のいずれかになり、操作(O)を二回行うと元の結び方に戻るので、
一回の操作で自分自身に戻る、不変、か、二つの異なる結び方で移り合うかのどちらかになります。
前者、不変な場合は問題ありませんが、後者は、一見異なるものが移り合うので、
意味のあるのは半分です。これは、不変なものを 2 回数えるとして足して、2 で割っても同じです。
不変性の方が検討しやすいので、この戦略をとることにします。
そこで、具体的に不変なものを調べてみましょう。
回転まで行うと、
1 -> 1 - a(n) + a(n-1) -> 1 - a(n) + a(n-2) ->
... -> 1 - a(n) + a(n-i+1) -> ...
-> 1 - a(n) + a(i) -> ... -> 1 - a(n) + a(3)
-> 3 - a(n) -> 2 - a(n)
もしこの段階で 1 - a(n) + a(n-1) = 2 ならば、1 軸対称移動は不要なので、
この結び方自身がが不変でなければなりません。
つまり、適宜、+n, -n をする意味での等式、要するに mod n、で、
1 - a(n) + a(n-1) = 2
1 - a(n) + a(n-i+1) = a(i)
1 - a(n) + a(i) = a(n-i+1)
3 - a(n) = a(n-1)
2 - a(n) = a(n)
最後の式で a(n) = 1 はありえないので、a(n) = n/2 + 1 になります。
a(n) は 3 〜 n の自然数なので、n は偶数でなければなりません。
そのとき、上式より、mod n に注意して、
a(n-1) = n/2 + 2
これ以上は上式だけでは確定できません。a(n-i+1) は a(i) が決まれば決まりますが、
a(i) だけの自由度があります。これは、結び方が複数あることを意味しています。
しかし、結び方には、命題の(A)の条件があったので、実際には、
1 -> 2 -> 3 -> ..(1).. -> n/2 + 3 -> n/2
+ 2 -> n/2 + 1
or
1 -> 2 -> n -> ..(2).. -> n/2 -> n/2 + 2
-> n/2 + 1
さらに、..(1).. などは、
..(1).. = 4 -> ..(3).. -> n/2 + 4, or n ->
..(4).. -> n/2
..(2).. = 3 -> ..(5).. -> n/2 + 3, or n-1 ->
..(6).. -> n/2 - 1
..(3).. = 5 -> ... -> n/2 + 5, or n -> ...
-> n/2
..(4).. = 4 -> ... -> n/2 + 4, or n-1 -> ...
-> n/2 - 1
..(5).. = 4 -> ... -> n/2 + 4, or n-1 -> ...
-> n/2 - 1
..(6).. = 3 -> ... -> n/2 + 3, or n-2 -> ...
-> n/2 - 2
...
などと決定していけます。
結局、最初に四つの点が確定した後は、a(i) を (n-4)/2 回決定すればよく、
その決定は 2 倍ずつ増えるので、不変な結び方は 2^((n-4)/2) 通りあることが分かります。
ここで、問題には直接関係しませんが、図形的考察をしておくと．．．
n に具体的な数を与えて点の並びを図に描いてみると分かりますが、
これは、180度の回転対称性をもった結び方になっています。
先に、n が偶数の場合は、1 軸が (n/2 + 1) 軸に一致しており、これが重複の可能性を生むと、
注意しました。まさに、これが対応しているものと思われます。
さて、回転までで不変になる場合は、分かりました。
次は、1 軸対称性を使う場合です。この場合は、1 - a(n) + a(n-1) = n でなければなりません。
回転までしたものを 1 軸に対称に移動すると
1 -> 1 + a(n) - a(n-2) -> ... -> 1 + a(n) -
a(n-i+1) -> ...
-> 1 + a(n) - a(i) -> ... -> 1 + a(n) - a(3)
-> - 1 + a(n) -> a(n)
これが不変なので、
1 - a(n) + a(n-1) = n
1 + a(n) - a(n-i+1) = a(i)
1 + a(n) - a(i) = a(n-i+1)
先ほどと同じで、これだけでは確定しませんが、命題の(A)の条件から、
1 -> 2 -> 3 -> ..(1).. -> a(n) - 2 ->
a(n) - 1 -> a(n)
or
1 -> 2 -> n -> ..(2).. -> a(n) + 1 ->
a(n) - 1 -> a(n)
で、
..(1).. = 4 -> ..(3).. -> a(n) - 3, or n ->
..(4).. -> a(n) + 1
..(2).. = 3 -> ..(5).. -> a(n) - 2, or n-1 ->
..(6).. -> a(n) + 2
..(3).. = 5 -> ... -> a(n) - 4, or n -> ...
-> a(n) + 1
..(4).. = 4 -> ... -> a(n) - 3, or n-1 -> ...
-> a(n) + 2
..(5).. = 4 -> ... -> a(n) - 3, or n-1 -> ...
-> a(n) + 2
..(6).. = 3 -> ... -> a(n) - 2, or n-2 -> ...
-> a(n) + 1
...
などとなっていき、結局、中央のところで、a(n) が決定して、その場合の結び方が確定します。
それまでは、最初の二つを除いて 2 倍ずつ増えます。
ただし、上記の方法で a(n) を決定したときに、矛盾がないかどうか調べる必要があります。
まず、特殊な場合として、n = 3 は、具体的に調べて、明らかに問題ありません。
(1 -> 2 -> 3 しかありません。)
次に、n >= 4 の場合を考えます。
今、命題の(A)に従って a(i) を決めていったときに表れる数字は、
1, 2, ..., k 及び n, n-1, ..., n-m+1
になります。ただし、k >= 2 で、n の系列は出現しない可能性もあります。m = 0 でそれを表します。
また、a(i) + a(n-i+1) = 1 + a(n) に注意します。
・n が奇数の場合 (n >= 5 としていることに注意。)
i = (n+1)/2 のときに
a((n+1)/2) + a((n+1)/2) = 1 + a(n)
a(n) = 2 * a((n+1)/2) - 1
命題の(A)に従っていれば、a((n+1)/2) = k 又は n-m+1 となっているハズです。
ただし、2 <= k <= (n+1)/2、m は 3 点目から (n+1)/2 点目までで最大、右隣り、を結んだ回数なので、
最小、左隣り、を結んだ回数 k-1 を ((n+1)/2 - 1) 回から引いて、m =
(n+1)/2 - k です。
そこで、あらためて、1 <= i <= (n+1)/2 として、
a((n+1)/2) = k のとき、a(n) = 2k - 1, a(n-i+1) = 2k - a(i)
a((n+1)/2) = n-m+1 = (n+1)/2 + k のとき、a(n) = 2k,
a(n-i+1) = 2k+1 - a(i)
このとき a(n-i+1) は、a(i) によって決定し、a(i) はその決定の仕方から i が異なれば異なるので、
a(n-i+1) 同士も異なります。
そこで、a(n-i+1) の取り得る値が、a(i) の範囲と共通部分をもたないことが分かれば、
決定に矛盾がないことになります。
まず、1 <= i <= (n+1)/2 で現れる数字、要するに a(i) の取り得る値、を確認しておきます。
a((n+1)/2) = k の場合は、
1, 2, ..., k 及び n, n-1, ..., n-m+2 = (n+1)/2 + k + 1
a((n+1)/2) = n-m+1 = (n+1)/2 + k の場合は、
1, 2, ..., k-1 及び n, n-1, ..., n-m+1 = (n+1)/2 + k
で、結局、1 <= i < (n+1)/2 で a(i) は、
1, 2, ..., k-1 及び n, n-1, ..., n-m+1 = (n+1)/2 + k + 1
のいずれかをとります。
さて、1 <= i < (n+1)/2 での a(n-i+1) の取り得る値を調べます。
a((n+1)/2) = k の場合：
2 <= k <= (n+1)/2 を考慮して、
1 <= a(i) <= k-1 では、
k < k + 1 <= a(n-i+1) = 2k - a(i) <= 2k - 1 =
k + (k-1) <= (n+1)/2 + k - 1 < (n+1)/2 + k
(n+1)/2 + k + 1 <= a(i) <= n では、
2k - n <= a(n-i+1) = 2k - a(i) <= k - (n+1)/2 - 1
<= -1 < 0
mod n で考えているので +n をして、
k < k + 2 <= k + k = 2k < a(n-i+1) <= k -
(n+1)/2 - 1 + n = (n+1)/2 + k - 2 < (n+1)/2 + k
で、いずれも、a(i), a((n+1)/2) の取り得る範囲と重ならず、問題ありません。
a((n+1)/2) = (n+1)/2 + k の場合：
この場合には、a((n+1)/2) not= 1 なので、2 <= k <=
(n+1)/2 - 1 になることに注意します。
1 <= a(i) <= k-1 では、
k < k + 2 <= a(n-i+1) = 2k+1 - a(i) <= 2k = k
+ k <= (n+1)/2 - 1 + k < (n+1)/2 + k
(n+1)/2 + k + 1 <= a(i) <= n では、
2k+1 - n <= a(n-i+1) = 2k+1 - a(i) <= k - (n+1)/2
<= -1 < 0
mod n で考えているので +n をして、
k < k + 3 <= k + k+1 = 2k+1 <= a(n-i+1) <=
k - (n+1)/2 + n = (n+1)/2 + k - 1 < (n+1)/2 + k
で、いずれも、a(i), a((n+1)/2) の取り得る範囲と重ならず、問題ありません。
結局、n が奇数の場合は、a(n) の決定に矛盾はありません。
そこで、2 倍ずつ増えるのは最初の二つを除いて (n+1)/2 - 2 = (n-3)/2 回になり、
n が奇数の場合の不変な結び方は、2^((n-3)/2) 通りになります。
・n が偶数の場合
i = n/2 のときに、、
a(n/2) + a(n/2+1) = 1 + a(n)
ですが、奇数の場合と異なり、a(n/2), a(n/2+1) の両方を決めないと a(n) が決まりません。
命題の(A)に従って、a(n/2) = k 又は n-m+1 としたとします。すると、
a(n/2) = k のとき、a(n/2+1) = k+1 又は n-m+1
a(n/2) = n-m+1 のとき、a(n/2+1) = k 又は n-m
と決めることになります。ただし、2 <= k <= n/2 です。
m は 3 点目から n/2 点目までで最大を結んだ回数なので、m = n/2 - k です。そこで、
a(n/2) = k 及び a(n/2+1) = k+1 のとき、a(n) = 2k, a(n-i+1) =
2k + 1 - a(i)
a(n/2) = k 及び a(n/2+1) = n-m+1 のとき、a(n) = k+n-m = 2k +
n/2, a(n-i+1) = 2k + n/2 + 1 - a(i)
a(n/2) = n-m+1 及び a(n/2+1) = k のとき、a(n) = k+n-m = 2k +
n/2, a(n-i+1) = 2k + n/2 + 1 - a(i)
a(n/2) = n-m+1 及び a(n/2+1) = n-m のとき、a(n) = n-m + n-m =
2k, a(n-i+1) = 2k + 1 - a(i)
このとき、奇数の場合と同様に、a(n-i+1) の取り得る値が、a(i) の範囲と
共通部分をもたないことが必要十分です。
1 <= i <= n/2 で現れる数字は
a(n/2) = k の場合は、
1, 2, ..., k 及び n, n-1, ..., n-m+2 = n/2 + k + 2
a(n/2) = n-m+1 = n/2 + k + 1 の場合は、
1, 2, ..., k-1 及び n, n-1, ..., n-m+1 = n/2 + k + 1
で、1 <= i < n/2 の a(i) は、
1, 2, ..., k-1 及び n, n-1, ..., n-m+2 = n/2 + k + 2
のいずれかをとります。
さて、1 <= i < n/2 での a(n-i+1) の取り得る値を調べます。
a(n/2) = k の場合：
2 <= k <= n/2 も考慮すると．．．
a(n/2+1) = k+1 のとき、
1 <= a(i) <= k-1 では、
k + 1 < k + 2 <= a(n-i+1) = 2k + 1 - a(i) <=
2k = k + k <= n/2 + k < n/2 + k + 1
n/2 + k + 2 <= a(i) <= n では、
2k + 1 - n <= a(n-i+1) = 2k + 1 - a(i) <= k - n/2
- 1 <= -1 < 0
mod n で考えているので、+n をして、
k + 1 < k + 3 <= k + k + 1 = 2k + 1 < a(n-i+1)
<= k - n/2 - 1 + n = n/2 + k - 1 < n/2 + k + 1
で、いずれも、a(i), a(n/2), a(n/2+1) の取り得る範囲と重複せず、問題ありません。
a(n/2+1) = n-m+1 = n/2 + k + 1 のとき、
1 <= a(i) <= k-1 では、
k + n/2 + 2 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
2k + n/2
n/2 + k + 2 <= a(i) <= n では、
2k - n/2 + 1 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
k - 1
mod n で考えているので、+n をして、
2k + n/2 + 1 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
k - 1 + n
先ほどの結果と合わせると、
k + n/2 + 2 <= a(n-i+1) <= k - 1 + n
ですが、これは、mod n に注意すると、
k + n/2 + 2 <= a(n-i+1) <= n, 1 <= a(n-i+1)
<= k - 1
としてよく、これらは、a(i) の範囲と重なってしまい、排除する必要があります。
結局、a(n/2) = k 及び a(n/2+1) = k+1 の場合だけが可能です。
a(n/2) = n-m+1 = n/2 + k + 1 の場合：
a(n/2) not= 1 なので、2 <= k <= n/2 - 1 としていいことに注意します。
a(n/2+1) = k のとき、
1 <= a(i) <= k-1 では、
k + n/2 + 2 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
2k + n/2 - 1
n/2 + k + 2 <= a(i) <= n では、
2k - n/2 + 1 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
k - 1
mod n で考えているので、+n をして、
2k + n/2 + 1 <= a(n-i+1) = 2k + n/2 + 1 - a(i) <=
k - 1 + n
先ほどの結果と合わせると、2k + n/2 は除かれていますが、
k + n/2 + 2 <= a(n-i+1) <= k - 1 + n
ですが、これは、mod n に注意すると、
k + n/2 + 2 <= a(n-i+1) <= n, 1 <= a(n-i+1)
<= k - 1
としてよく、これらは、a(i) の範囲と重なってしまい、排除する必要があります。
a(n/2+1) = n-m = n/2 + k のとき、
1 <= a(i) <= k-1 では、
k + 1 < k + 2 <= a(n-i+1) = 2k + 1 - a(i) <=
2k = k + k <= n/2 - 1 + k < n/2 + k
n/2 + k + 2 <= a(i) <= n では、
2k + 1 - n <= a(n-i+1) = 2k + 1 - a(i) <= k - n/2
- 1 <= -2 < 0
mod n で考えているので、+n をして、
k + 2 < k + 3 <= k + k + 1 = 2k + 1 < a(n-i+1)
<= k - n/2 + n - 1 = n/2 + k - 1 < n/2 + k
で、いずれも、a(i), a(n/2), a(n/2+1) の取り得る範囲と一致せず、問題ありません。
結局、a(n/2) = n-m+1 及び a(n/2+1) = n-m の場合だけが可能です。
以上から、結局、a(n/2+1) は a(n/2) の決め方で一意に決まってしまうことが分かります。
そこで、2 倍ずつ増えるのは最初の二つを除いて n/2 - 2 = (n-4)/2 回です。
そこで、n が偶数の場合の不変な結び方は、2^((n-4)/2) 通りになります。
これでやっと、操作(O)で不変な場合が求まりました。
まとめておくと、
・n が奇数の場合
回転だけの場合が 0 個、回転と 1 軸対称の両方を行う場合が 2^((n-3)/2) 個、
合計で、2^((n-3)/2) 個。
・n が偶数の場合
回転だけの場合が 2^((n-4)/2) 個、回転と 1 軸対称の両方を行う場合が
2^((n-4)/2) 個
合計で、2^((n-4)/2) + 2^((n-4)/2) = 2 * 2^((n-4)/2) 個。
以上から、逆向きを考慮しない場合 2^(n-3) 個に、不変な場合を足して 2 で割れば、
g(n) が求まります。結局、
・n が奇数のとき
g(n) = (2^(n-3) + 2^((n-3)/2))/2 = 2^(n-4) +
2^((n-5)/2) 種類
・n が偶数のとき
g(n) = (2^(n-3) + 2 * 2^((n-4)/2))/2 = 2^(n-4) +
2^((n-4)/2) 種類
になります。
[感想]
問題8：の解答が、恐ろしく難しくなってしまいました。
ただ、やっていることは単純で、考えられる対称性を一つずつ除いているだけです。
しかし、その証明に微妙な箇所があり、不等式の評価などに神経を使っています。
なお、全体的に、発見的な記述をしているので冗長になっていますが、
考え方の筋道を追う意味ではこの方が分かりやすいと思うので、そのままにしました。
もっとも、もっと簡単な方法がありそうな気もします。
見直して誤りがあったら、又はもっと分かりやすい方法が見つかったら、
また、報告します (^^;
NO5「ice」 4/01 19時53分受信 更新4/2
皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。
