『リング状に並べた自然数』解答

◆広島県　清川　育男　さんからの解答。

十進BASICでプログラミングしました。

【問題１】

　１
４　２
　６
【問題２】
　 １
５　 ３
２　１０
 【問題３】

　　１
１３　　２
　６　　５
　　４

　　１
　５　　２
１２　　７
　　４


　　１
１０　　３
　８　　２
　　７


　　１
１４　　３
　５　　６
　　２

【問題４】

一般的には不可能だと思います。
Ｎ＝１０くらいまで確かめた報告を見たことがありますが、それでも、とびとびに可能だったように思います。
連続的には不可能。

証明はわかりません。
あるＨ．Ｐで話題になり検討されたことがあります。

１，３，７，１３，２１，３１，４３，５７，７３，９１
２，４，６，８，１０，１２，

一般式　Ｎ2−Ｎ＋１　まで可能性はありますが、
Ｎ＝１〜１０までに実現不可能な数Ｎがあります。　

◆東京都　未菜実　さんからの解答。

【問題１の答え】

１，２，６，４
１，３，２，７

【問題２の答え】

１，３，１０，２，５

【問題３の答え】

１，２，５，４，６，１３
１，２，７，４，１２，５
１，３，２，７，８，１０
１，３，６，２，５，１４
１，７，３，２，４，１４

【問題４の答え】

１個からｎ−１個までは、各々組み合わせがｎ個
それにすべてを選ぶのが１個で、
計ｎ(ｎ−１)＋１＝ｎ2−ｎ＋１の組み合わせが存在するので最大はこの数になる。

しかし、それがすべて出来るかどうかは問題で、事実７個の４３は無い様です。

◆広島県　清川　育男　さんからの解答。

・追加

●Ｎ＝４（１〜１３）

　１
７　３
　２
●Ｎ＝７　　不可能　（１〜４３）

●Ｎ＝８　（１〜５７）

１，２，１０，１９，４，７，９，５
１，３，５，１１，２，１２，１７，６
１，３，８，２，１６，７，１５，５
１，４，２，１０，１８，３，１１，８
１，４，２２，７，３，６，２，１２
１，６，１２，４，２１，３，２，８

上記６通りだと思います。
すべての検索が終わったわけではないのですが。
なんとなく規則性があるような気がします。

Ｎ＝９はベーシック言語では時間的に無理のようです。
Ｃ言語とか。
高速化のためにかなり改良したのですが。

●表

Ｎ検索されるべき最大の数表わせる数
１１１
２２１〜３
３４１〜 ７
４７１〜１３
５１１１〜２１
６１６１〜３１
７２２１〜４３
（不可能）
８２９１〜５７
・・・・・・
Ｎ(N2ｰN+2)/21〜(N2-N+1)

◆広島県　清川　育男　さんからの解答。

●中間報告

Ｎ＝９（１〜７３）

１，２，４，８，１６，５，１８，９，１０
（未菜実さんから教えてもらいました。）

１，４，７，６，３，２８，２，８，１４

１，６，４，２４，１３，３，２，１２，８

まで見つけました。
１，７，．．．がなければこれですべてだと思います。

Ｎ＝１０はやはりＣ言語かコンパイル型言語でないと時間的に。

◆広島県　清川　育男　さんからの解答。

１，７．．．．は存在しませんでした。
したがって、３通りだと思います。
規則性があるように思ったのですが、見つかりません。

◆埼玉県　\aleph_0　さんからの解答。

一般則はまだ分かりません。
現在分かっているところまで報告したいと思います。

●n=9, a9=4:
  1  2  4  8 16  5 18  9 10
  1 16 22  2  3  4  6  8 11
  1  8 12  2  3 13 24  4  6
  1 14  8  2 28  3  6  7  4

●n=10, a10=6:
  1  2  6 18 22  7  5 16  4 10
  1 36  2 12  7  8  3 13  4  5
  1  4  2 20  8  9 23 10  3 11
  1 18  3  2  8  4 29 11  9  6
  1  4  3 10  2  9 14 16  6 26
  1 18 28  5  2  8  6 11  9  3

●n=11, a11=0.

●n=12, a12=18:
  1  2 14  4 37  7  8 27  5  6 13  9
  1  2  9  8 14  4 43  7  6 10  5 24
  1  2 12 31 25  4  9 10  7 11 16  5
  1  2 14 12 32 19  6  5  4 18 13  7
  1  7  2 22  4 16  3 11 29 21 12  5
  1 11  2  8  7 25  6  3 27 20 19  4
  1  6  2 33 17 14 12 10 15  3 16  4
  1 14  3  2  4  7 21  8 25 10 12 26
  1 31 10  2  4  3  8 13  5 20 14 22
  1  9 48  2  4 18  5 11  3 12 13  7
  1  8  5  2 18 11 10 22  6 24 23  3
  1  6 28  2 13 16 23 19  5  9  8  3
  1  3 12 34 21  2  8  9  5  6  7 25
  1  4  7  3 16  2  6 17 20  9 13 35
  1 35 26  3 11  2  4 21  7  5 10  8
  1 15  5  3 25  2  7  4  6 12 14 39
  1 41  8  4 17  2  3  6  7 20 10 14
  1  7  6 16 15  2  9 10 40  3 20  4

●n=13, a13=0.

●n=14, a14=20:
  1  2 21 17 11  5  9  4 26  6 47 15 12  7
  1  2 13  7  5 14 34  6  4 33 18 17 21  8
  1  2 28 14  5  6  9 12 48 18  4 13 16  7
  1 10  2 16 32 20  3 21 33  5  4 22  8  6
  1  5  2 24 15 29 14 21 13  4 33  3  9 10
  1 15 34  2  3 17  7  6  8  4 19  9 48 10
  1  4 20  2 12  3  6  7 33 11  8 10 35 31
  1 12 48  6  2 38  3 22  7 10 11  5  4 14
  1 33 14 36  2 16  6  5  8  4  3 25 21  9
  1 12 11  6  2 18 16 35 21  4  3 40  5  9
  1  9  8 28  2 24  5  6 44 14 20  7 12  3
  1 25 23  4 10  2  3 17 11  7  6 45 21  8
  1  9 14 26  4  2 11  5  3 12 27 34  7 28
  1 19 16  5  8  2  7 55 11 14 12  6 24  3
  1 12 22  7 17  2 18 10 23 32 25  6  5  3
  1  4  6 31  3 13  2  7 14 12 17 46  8 19
  1 17  8  5 24 14  2  4  3 12 27 34 22 10
  1  8 16 10 12 19  2 11  4  3 42 27 23  5
  1 18  7 17 15 14  2  4 56  5 23 10  3  8
  1  4  8 52  3 25 18  2  9 24  6 10  7 14
p=7,11,13のときap=0となるのがとても気になるのですが....

以下は、上記の解を検索するためのBASICプログラムの一例です。

DECLARE EXTERNAL SUB SEARCH
INPUT PROMPT "N=": N
LET T=TIME
LET N2=N*(N-1)+1
DIM X(2-N TO 2*N),M(N2)
LET X(1)=1
LET X(1+N)=1
LET M(1)=1
FOR K=2 TO INT(N/2)+1
   CALL SEARCH(N,N2,X,M,2,2,K)
NEXT K
PRINT "THE PROGRAM HAS USED";TIME-T;"SECOND(S)."
END

EXTERNAL SUB SEARCH(N,N2,X0(),M0(),I,Y0,K0)
DIM X(2-N TO 2*N),M(N2)
MAT X=X0
MAT M=M0
LET Y=Y0
LET K=K0
LET X(K)=Y
LET X(K+N)=Y
LET X(K-N)=Y
LET LE=K
DO WHILE X(LE-1)>0
   LET LE=LE-1
LOOP
LET RE=K
DO WHILE X(RE+1)>0
   LET RE=RE+1
LOOP
FOR L=LE TO K
   FOR R=K TO RE
      LET Z=SUM(L,R)
      IF M(Z)=1 THEN EXIT SUB
      LET M(Z)=1
   NEXT R
NEXT L
IF I<N-1 THEN
   DO WHILE M(Y)=1
      LET Y=Y+1
   LOOP
   IF SUM(1,N)+Y>=N2 THEN EXIT SUB
   FOR K=2 TO N
      IF X(K)=0 THEN CALL SEARCH(N,N2,X,M,I+1,Y,K)
   NEXT K
ELSE
   LET K=2
   DO WHILE X(K)>0
      LET K=K+1
   LOOP
   LET X(K)=N2-SUM(1,N)
   FOR L=K-N+2 TO K
      FOR R=K TO L+N-2
         LET Z=SUM(L,R)
         IF M(Z)=1 THEN EXIT SUB
         LET M(Z)=1
      NEXT R
   NEXT L
   FOR K=1 TO N
      PRINT X(K);
   NEXT K
   PRINT
END IF
FUNCTION SUM(L,R)
   LET S=0
   FOR J=L TO R
      LET S=S+X(J)
   NEXT J
   LET SUM=S
END FUNCTION
END SUB
BASICコンパイラをお持ちでしたら、試してみてください。
（Nが偶数のとき、本質的に同じ逆順の解が出てくる場合がありますが、無視してください。）

　『リング状に並べた自然数』へ

　数学の部屋へもどる