ものさしの目盛り

 投稿者:山中和義  投稿日:2014年 4月12日(土)09時41分49秒
  問題
自然数を直線状に並べます。
その状態で、連続して並んだいくつかの自然数の合計をとります。
合計をとる自然数はいくつ選んでもかまいません。
1つだけでも、全部でもかまいません。
ただし、続いて並んでいなければならず、飛び飛びに合計することはできません。

(1) 5個の自然数をうまく選んで並べると、1から13までの合計をつくることができます。
(2) 6個の自然数をうまく選んで並べると、1から17までの合計をつくることができます。
(3) 7個の自然数をうまく選んで並べると、1から23までの合計をつくることができます。


1個の場合
 1 として、1
2個の場合
 1,2 として、3
3個の場合
 1,3,2 として、6
4個の場合
 1,1,4,3 として、9
 1,3,3,2 として、9

http://math.a.la9.jp/jyougi.htm


考察
p進法を利用した数字の並び
 ① ※丸数字がk個並ぶ 1からkまで 通常の目盛り
 1② 2k+1
 11③ 3k+2
 111④ 4k+3
 1111⑤ 5k+4
  :
さらに、
 ②1 2k+1
 1③2 3k+3
 11④3 4k+5
 111⑤4 5k+7
 1111⑥5 6k+9
  :
と展開できる。これは、いわゆる近似解である。
(終り)


数字の並びの組み合わせは、次の問題と同値なので、それを元に作成する。
 問題:n個の球をm個の箱に分ける方法 (5)



LET N=13
LET M=5

DIM B(M) !各箱の中の球の個数
MAT B=CON

PUBLIC NUMERIC C !場合の数
LET C=0

CALL try(2,N-M, N,M,B) !※1の位置を固定する
PRINT C;"通り"

END


EXTERNAL SUB try(P,T, N,M,B())
IF P=M THEN !R番目なら
   LET B(P)=B(P)+T !set it

   FOR i=1 TO INT(M/2) !対称性(直線状)
      IF B(i)<>B(M-i+1) THEN EXIT FOR
   NEXT i
   IF B(i)<B(M-i+1) OR i>INT(M/2) THEN

      DIM F(N) !1~nの数字
      MAT F=ZER
      FOR i=1 TO M !i番目から
         FOR K=0 TO M-i !続くk個の数字
            LET S=0
            FOR X=0 TO K !その和
               LET S=S+B(i+X)
            NEXT X
            LET F(S)=1
         NEXT K
      NEXT i
      FOR i=1 TO N !すべて表されるかどうか確認する
         IF F(i)=0 THEN EXIT FOR
      NEXT i
      IF i>N THEN

         LET C=C+1 !結果を表示する
         MAT PRINT B;

      END IF

   END IF

   LET B(P)=B(P)-T !restore it

ELSE
   FOR i=0 TO T !p番目
      LET B(P)=B(P)+i !set it
      CALL try(P+1,T-i, N,M,B)
      LET B(P)=B(P)-i !restore it
   NEXT i

END IF
END SUB


実行結果 (1)

1  1  4  4  3

1  3  1  6  2

1  5  3  2  2

3 通り

 

戻る