2. 笑わない数学者の問題 の続き。
笑わない数学者の問題
.....
P_n=n*(n-1)/2 の場合について考えます。上限値を1下げたわけですね。
すでに述べたように n= 1,2,3 については考えません。
n=1 の場合はP_n=P₁=1のはずですが、この条件に従うと P₁=0になってしまいます。n=2 の場合も同様にP_n=P_n=2 ですが、この条件に従うとP₂=1 になってしまうからです。成り立たない。
n=3の場合、ボール全体が [1,2,3]になりますが、これだと全部あわせても n*(n-1)+1 …この場合は7に届きません。だからこれも無しです。

というわけで ｎ≧4が、P_n=n*(n-1)/2 のための条件になります。

.

P_n=n*(n-1)/2 の場合、P_nを使うかどうか(使うなら黒丸)で塗り分けた白黒の丸は次のような形になります。一応、左側の数字が小さく、右側が大きい。
○○○○……○○○● | ○●●●……●●●●
| の部分の左側のまるが Qn*(n-1)/2 、右側が Qn*(n-1)/2 + 1 です。

実は、P_nがこれ以上左に行くと、不確定な要素がさらに一つ追加されます。たとえばもういっちょ左に行くと

○○○○……○○●○ | ●○●●……●●●●
○○○○……○○●● | ○○●●……●●●●

の2パターンがありえるのです。面倒なのでどちらでもありえるボールは◎で表すことにします(でも線対称ですので片方が黒と決まれば対になるもう一方は白です)。

○○○○……○○●◎ | ◎○●●……●●●●
○○○○……○●◎◎ | ◎◎○●……●●●●
○○○○……●◎◎◎ | ◎◎◎○……●●●●

で、◎の部分の組み合わせは、縦棒の左側の◎の個数 x 個に対して 2^x 通りあります。どんどん苦しくなるー。なので、そういう不確定要素が増える前の最後のポイントを押さえておきましょう、というわけです。

.

前回と同様、P_i の値を求めましょう。 Σ^n-1 _i=1 P_iは、白丸の一番右側のポイントから n*(n-1)/2 + 1 と求まります。これは前回 P_n=n*(n-1)/2+1 だった場合よりも１だけ大きい。

前回P_i=i が i=1..(n-1) について成り立っていました。また P_i＞P_i-1が必ず成り立ちます。このことから、実は P_i=i ( i=1..n-2 ), P_n-1=n と一意決定します (P_n-1 だけが前回よりも 1 大きい。それ以外の数は変化してはいけない)。

たとえば、仮に P_n-2 が前回より1大きいとしましょう。P_n-2=n-1 です。すると自動的に P_n-1=n が成り立ちます。つまり、P_n-2とP_n-1の両方が前回よりも1づつ大きい値をとるのですから、合計すると「前回よりも2大きい値」…つまり n*(n-1)/2 + 2 が Σ^n-1 _i=1 P_i の答になってしまいます。他の P_i （i ≦ n-2 ）についても同様の議論が成り立ちます。

..........

さて、P_i の値が全部求まったところで並べ方です。今回は n が十分大きいとして、どのような順序で並べるべきなのかを考えていきます。行き詰った段階で、使っている最大値から、n の上限値が判ります。

○○○○……○○○● | ○●●●……●●●●

というここから P_n を含む「2番目に大きい値」は P_n+2 と判ります。これは2つの事を意味します。
1) P₁ は P_n に隣接していない。
2) P₂ は P_n に隣接している。

つまりこの段階で、ボールの並び順は [2, P_n ] が確定したわけです。

.

次は P_n+3 が黒丸なわけですが…早くも嵐の予感です。可能性が2つもあります。

A) [ 1, 2, P_n ]
B) [ 2, P_n, 3 ]

他にパターンがありえない、というのは良いと思います。さて、どちらが生き延びるでしょう?

.

P_n+4 もありますね。

A-1) [ 1, 1, 2, P_n ] これが NG なのは自明でしょう。同じ番号が2度出てきます。
A-2) [ 1, 2, P_n, 4 ] ---- 実はこれはNGです。
B-1) [ 2, 2, P_n, 3 ] これも NG です。
B-2) [ 2, P_n, 3, 1 ] ---- 実はこれもNGです。

はい。終～了～。 n が十分大きい場合は、ここまで来た段階で NG が発覚します。 A-1 と B-1 は同じボールが2度出てくるから、と判りますよね。ポイントは A-2 と B-2 です。

A-2 は実は 「1, 2」の並びが数字の 3 を作るからです。P_i=i が i ≦ n-2 について成り立つはずでしたよね? つまり P₃=3 が成り立つ ( 3 ≦ n-2 ですから 5 ≦ n ) 場合、A-2 の並び方は同じ数字を作る方法が2通り以上存在することになります。しかし、そもそもこの問題、『ボールの拾い方の組み合わせ』に無駄はなかったはずですよね? つまり同じ数字を作る方法が2通りあったら成立しなかったはずです。この段階で 3 を作る方法が2通り見つかるというのは NG な証拠なのです。

B-2 は [3,1] が 4 を作るからです。P₄=4 が成り立つ ( 4 ≦ n-2 なので 6 ≦ n ) の場合はNGです。

もちろん、十分小さな n に対してはそれぞれの制約はなくなります。

n = 4 の場合は P₁ = 1, P₂=2, P₃= P_n-1= 4, P₄=P_n=n*(n-1)/2 = 4*3/2=6 が成り立ちます。この場合は 3 と言う数字を持ったボールは存在しませんから A-2 は OK。逆に B-2 は「3がないので」NGです。実際 [1,2,6,4] は答のパターンの1つです。

n = 5 の場合、P₁ = 1, P₂=2, P₃=3, P₄=P_n-1=5, P₅=5*(5-1)/2=10 となりますが、これを満たせるのは B-2 の場合だけです。[ 2, 10, 3, 1 ] が決まっており、残りのボールは [5] だけなので [2, 10, 3, 1, 5] と一意に決まります。1 から数字の小さいほうに並べると [1,3,10,2,5] ですね。

.

P_n=n*(n-1)/2+1 がOKだったのは n=1,2,3,4 の4通りでした。
P_n=n*(n-1)/2 が OK だったのは n=4,5 の2通りでした。
んー、この調子なら P_n=n*(n-1)/2-1 が OKなのは n=6 の1通りで、n≧7 は解はありません、ってならないかなー、ってなるわけないよね。n=8の解はもう b e nihitode さんの日記 とか WindVoice さんの日記とかにも載ってるぐらいだし。

ということは ◎ の中身を追いかける必要があるって事ですかぁ～ orz

....

あとで私が見るためのリンク:
http://srad.jp/~WindVoice/journal/479012
http://srad.jp/~GeoJ/journal/479229
http://srad.jp/~greentea/journal/479414
  奇数偶数は考えなかったわ…意外と大事かもしれない。

......

最後に、たぶん計算量を減らすとしたら、アルゴリズムレベルではこれが必須だと思う:
A. 笑わない数学者の問題 なお、A. は「答」という意味じゃなく、「Appendix 第Ａ章」っていう意味だ。