2016年6月2日木曜日

階乗の集合の等しい積への分割 (はできない)

\(\{1, 2, \ldots, n\}\) を二つの部分集合に分割したとき、その積が一致することはない。 では \(\{1!, 2!, \ldots, n!\}\) にも同様に積が一致するような分割はないと証明できるか、というのがツイッターで流れてきたので考えてみた。

まず \([n] = \{1, 2, \ldots, n\}\) の場合を振り返っておこう。 二つの部分集合に分割して積が一致するならば、全体の積 \(n!\) は平方数である。 \(n=2,3\) の場合はこれが無理なことは明らかなので、\(n > 3\) とする。 ところで \(n/2\) と \(n\) の間に素数が一つ以上存在する(いわゆるベルトランの仮説)のでその一つを \(p\) とおく。 \(p\) の倍数は \([n]\) の中で \(p\) 自身のみだから、積 \(n!\) は \(p\) でちょうど1回しか割り切れないので平方数ではない。 したがって積が一致するような分割は存在しない。

次に \([n]! = \{1!, 2!, \ldots, n!\}\) の場合を考える。 (\([n]!\) という記号はここだけの記号である。) 二つの部分集合に分割して積が一致するならば、全体の積 \(\prod_{k=1}^{n}k!\) は平方数であるというところまでは同じである。 多分平方数にならないとは思うが、それを一気に考えるのは難しい。

簡単なところから考えると、\([2]! = \{1!, 2!\} = \{1, 2\} = [2]\) であるから明らかに分割できない。 \([3]! = \{1!, 2!, 3!\}\) の場合、\(3\) で割り切れる回数はそれぞれ 0, 0, 1 回だから、全体の積は 1 回しか \(3\) で割り切れず平方数でない。

少し一般化する。 \(p\) を素数とすると \([p]!\) 全体の積は \(p\) で 1 回しか割り切れないので平方数でない。 よって、\([p]!\) は積が一致するような分割を持たない。

同じように割り切る回数を数えることで次のことも判る。 奇素数 \(p\) に対し、\([2p]!\) は積が一致するような分割を持たない。 実際、数えてみれば全体の積は \(p\) で \(p+2\) 回割り切れるが \(p+2\) は奇数である。

と、ここまではすぐに考えたが、実際は別の方向に考えた方が良かったのである。

全体の積 \(\Pi_n = \prod_{k=1}^{n}k!\) をもう少し別の角度から眺めよう。 イメージとしては、\(k!\) という列を並べた三角形を、\(k\) の冪という行に分ける。

\[\Pi_n = \prod_{k=1}^{n}k! = \prod_{k=1}^{n} k^{n-k+1} \]

\(n\) が奇数の時、\(\Pi_n\) から偶数 \(k\) について \(k^{n-k+1}\) と奇数 \(k'\) について \(k'^{n-k}\) が平方因子として取り除けて、 \(\Pi_n\) の代わりに残った奇数の積 \(n!!\) が平方数かどうかを考えれば良い。 これは再びベルトランの仮説の出番で、\(n > 4\) とすると \(n/2\) と \(n\) の間に奇素数が一つ以上存在し、 これを \(p\) とおくと \(n!!\) は \(p\) でちょうど1回しか割り切れないので平方数でない。 したがって積が一致するような \([n]!\) の分割は存在しない。

\(n\) が偶数の時も同様の議論で、\(n!!\) が平方数かどうかの議論をすれば良く、 三度ベルトランの仮説から(偶数の二重階乗なので各数を半分にして) \(n/4\) と \(n/2\) の間に奇素数が存在することが言えて平方数でないと示せる。 結局積が一致するような \([n]!\) の分割は存在しないことがわかる。

まとめると、\(2\) 以上の任意の整数 \(n\) に対し \([n]!\) は積が一致するような二つの部分集合への分割を持たない。

0 件のコメント:

コメントを投稿