今週の問題『第196回 バラバラの配置』への補足  『16個以上の石をバラバラに配置する解は存在しない』ことの補足説明です。 1.準備(用語の定義など)   @a、bを0以上の整数とし、自然数mが(a**2 + b**2)で表すことができるとき、mをノルム数    と呼ぶことにする。また、その構成要素を[a,b]と表記する。    [a,b]の次数をmax(a,b)と定義する。    mの表記の中で次数が最小となる表記を既約表記とする。      ex. 25=[0,5]=[3,4]の場合、[3,4]が既約表記となる           5=[1,2]の場合は、(1つしか存在しないので)、[1,2]が既約表記となる    注:2つの石の間のX軸、Y軸の差分をそれぞれa,bとすると、[a,b]は、距離の2乗に対応する。   AL(N):NxNのパネルに配置できる2つの石の間の距離が異なるものの数とする。    L(N)は、次数(N−1)以下の既約表記の数に等しい。 N R(N) L(N)/ L(N)の要素 (既約表記でないものは*で表示)    ----------------------------------------------------------------------------     2 1[ 1] : 2 / [ 0, 1] [ 1, 1]               <----δL(2)      3 3[ 2] : 5 / [ 0, 2] [ 1, 2] [ 2, 2] <----δL(3)     4 6[ 3] : 9 / [ 0, 3] [ 1, 3] [ 2, 3] [ 3, 3] <----δL(4)     5 10[ 4] : 14 / [ 0, 4] [ 1, 4] [ 2, 4] [ 3, 4] [ 4, 4]     6 15[ 4] : 19 / * [ 1, 5] [ 2, 5] [ 3, 5] [ 4, 5] [ 5, 5] N<=21については、添付ファイルを参照されたい。   BR(N):N個の石をバラバラに配置したとき、必要となる異なる距離の種類の数。    R(N)=N*(N−1)/2となる。   CδL(N) = L(N) − L(N-1) と定義する。    L(N)の定義から、L(N-1)からL(N)になることで増えるのは、[0,N-1],[1,N-1],[2,N-1],... [N-1,N-1]の N個の中で既約表記となっているものだけである。従って、δL(N) =< Nとなる。   DδR(N) = R(N) − R(N-1) と定義する。    Bより、δR(N)=N−1となる。        以上より、N個の石をバラバラに配置できるためには、L(N)>=R(N)であることが必要である。      もし、『N>=16の場合、L(N)<R(N)』が成立すれば、バラバラの配置の解は存在しない。   N=16では、この条件が成立しているので、(添付のR(N),L(N)の計算結果を参照)   N>16で、δL(N)=<δR(N)が成立すれば、もとの命題も成り立つことになる。 2.命題 『N>16の時、δL(N)=<δR(N)が常に成り立つ』   C、Dより、δL(N)=<N、δR(N)=N−1であるから、δL(N)の中に既約表記でないものが1つ   でも含まれていれば、命題が成立することになる。 1)n = 5*k の場合(k>3)  [0,n] = [0,5*k] = (5*k)**2 = (3*k)**2 + (4*k)**2 = [3*k,4*k] k>3では、[0,5*k]の次数は、[3*k,4*k]より大きいので、[0,5*k]は既約表記ではない。 2)n = 5*k+1 の場合(k>=3)  [2,n] = [2,5*k+1] = (5*k+1)**2 + 2**2 = 25*k**2 * 10*k + 5 = (3*k-1)**2 + (4*k+2)**2 = [3*k-1,4*k+2] k>=3では、[2,5*k+1]の次数は、[3*k-1,4*k+2]より大きいので、[2,5*k+1]は既約表記ではない。 3)n = 5*k+2 の場合(k>=3)  [1,n] = [1,5*k+2] = (5*k+2)**2 + 1**2 = 25*k**2 * 20*k + 5 = (3*k+2)**2 + (4*k+1)**2 = [3*k+2,4*k+1] k>=3では、[1,5*k+2]の次数は、[3*k+2,4*k+1]より大きいので、[1,5*k+2]は既約表記ではない。 4)n = 5*k+3 の場合(k>=3)  [4,n] = [4,5*k+3] = (5*k+3)**2 + 4**2 = 25*k**2 * 30*k + 25 = (3*k+5)**2 + (4*k)**2 = [3*k+5,4*k] k>=3では、[4,5*k+3]の次数は、[3*k+5,4*k]より大きいので、[4,5*k+3]は既約表記ではない。 5)n = 5*k+4 の場合(k>=3)  [2,n] = [2,5*k+4] = (5*k+4)**2 + 4**2 = 25*k**2 * 40*k + 20 = (3*k+4)**2 + (4*k+2)**2 = [3*k+4,4*k+2] k>=3では、[2,5*k+4]の次数は、[3*k+4,4*k+2]より大きいので、[2,5*k+4]は既約表記ではない。 1)〜5)のいずれの場合も、命題は成り立っている。従って、N>=16の場合、L(N)<R(N)が  成り立つので、『16個以上の石をバラバラに配置する解は存在しない』ことになる。