◆広島県 清川 育男さんからの解答。
今回は３進法というか３に関係した問題ですね。
定規の長さを効率よく使って最大何ｃｍまで測れるかと条件をつけると、規則性がはっきりするのではないでしょうか。
（個別には色々なやり方がありますが。）
| 目盛 | 目盛の入れ方 | 測れる長さ | 定規の長さ | 無駄 |
| ２個 | 1,3,2 | ６ｃｍ | ６ｃｍ | ０cm |
| ３ | 3,1,5,2 | ９ | １１ | ２ |
| ４ | 1,3,1,5,2 | １２ | １２ | ０ |
| ５ | 3,1,5,1,5,2 | １５ | １７ | ２ |
| ６ | 1,3,1,5,1,5,2 | １８ | １８ | ０ |
| ７ | 3,1,5,1,5,1,5,2 | ２１ | ２３ | ２ |
| ８ | 1,3,1,5,1,5,1,5,2 | ２４ | ２４ | ０ |
| ９ | 3,1,5,1,5,1,5,1,5,2 | ２７ | ２９ | ２ |
| １０ | 1,3,1,5,1,5,1,5,1,5,2 | ３０ | ３０ | ０ |
上記のような規則性が予想されます。
最大で「目盛りの数×３。」まで測れると思われます。
綺麗な規則性があるので上記の関係は正しいと思います。
【コメント】
実は私はパソコンで解いたのですが、関係を発見できていません。
そう単純ではないようです。
目盛りの数が４〜１０の場合は、もう少し長い長さまで測定可能です。
ただし私の持っている解も、最長だという保障はないので、記録を更新した方はどんどん解答を送ってください。
◆広島県 清川 育男さんからの解答。
間違っていました。
４，６，８，１０の場合は５を６に置き換えても連続しますね。
とりあえず、下記のように訂正します。
| 目盛 | 目盛の入れ方 | 測れる長さ | 定規の長さ | 無駄 |
| ４ | 1,3,1,6,2 | １３ | １３ | ０ |
| ６ | 1,3,1,6,1,6,2 | ２０ | ２０ | ０ |
| ８ | 1,3,1,6,1,6,1,6,2 | ２７ | ２７ | ０ |
| １０ | 1,3,1,6,1,6,1,6,1,6,2 | ３４ | ３４ | ０ |
【コメント】
おそらく４個の場合はこれが最善です。
（他にも１３ｃｍになる解は存在しますが）
６，８，１０個の場合は、更に優れた解が存在します。
◆広島県 清川 育男さんからの解答。
目盛りの数をＮとする。最大の計測数をＫとする。
| Ｋ≦ | Ｎ2＋３Ｎ＋２ ―――――――― ２ |
【コメント】
はい、間違いなくこの関係は成立します。
◆広島県 清川 育男さんからの解答。
【問題３】
目盛りが５箇所のとき 無駄
１）１，１，１，５，５，４ ０
２）１，１，４，４，４，３ ０
３）１，１，６，４，２，３ ０
４）１，１，６，４，３，２ ０
５）１，３，６，２，３，２ ０
６）１，７，３，２，２，２ ０
７）３，２，１，６，４，４ ３
以上７通りの方法で１７ｃｍまで測れる。
・目盛りが６箇所のとき。
１，３，６，６，２，３，２
２３ｃｍまで測定可能です。
・目盛りが７箇所のとき。
１，１，１，５，５，５，５，４
２７ｃｍまで測定可能です。
・目盛りが８箇所のとき。
１，１，１，５，５，５，５，５，４
３２ｃｍまで測定可能です。
・目盛りが９箇所のとき。
１，１，１，５，５，５，５，５，５，４
３７ｃｍまで測定可能です。
・目盛りが１０箇所のとき。
１，１，１，５，５，５，５，５，５，５，４
４２ｃｍまで測定可能です。
奇数、偶数は分けて考えた方が言いようです。
５を６に変えた方がよくなります。
プログラムを組んで再度挑戦します。
【コメント】
目盛りが５カ所、６カ所のときは、正しいと思います。
７カ所以上のときは、さらに優れた解があります。
ただ私も最善であるという証明は持っていないのですが・・・。
◆広島県 清川 育男さんからの解答。
今度こそは規則性を見つけたと思います。
３，６，９，１３，１７，２３，２９，３６，４３，５０
(1)１，２
(2)１，３，２
(3)３，１，５，２
(4)１，３，１，６，２
(5)１，３，６，２，３，２
(6)１，３，６，６，２，３，２
(7)１，３，６，６，６，２，３，２
(8)保留
(9)保留
(10)保留
上記が予想されます。古いコンピュータが働いています。
【コメント】
今度はたぶん正解だと思います。
証明は大変でしょうが、解の系列だけは何とかして見つけたいですね。
◆広島県 清川 育男さんからの解答。
目盛りが８カ所の場合
３６
１，２，３，７，７，７，４，４，１ 無駄 ０
目盛りが９カ所のとき
４３
１，２，３，７，７，７，７，４，４，１ 無駄 ０
目盛りが１０カ所のとき
５０
１，２，３，７，７，７，７，７，４，４，１ 無駄 ０
以上です。
On-Line Encyclopedia of Integer Sequences（数列サイト）によると
３，６，９，１３，１７，２３，２９，３６，４３，５０，
５９，６０，７９，９０，１０１，１１２，１２３，１３８
一般式は解っていないようです。
「minimal nodes in graceful graph with n edges」 とタイトルがついていました。
目盛りが１１カ所のとき ５９
目盛りが１２カ所のとき ６０ となっていますが、間違いではないのでしょうね。
１ｃｍしか増加していないのが不思議な気もしますが、確認する元気はありません。
◆東京都 未菜実 さんからの解答。
以下 パズル数学入門 藤村幸三郎/田村三郎著
講談社・ブルーバックスｐ65〜,p282〜を参考にしました。
なお、表示の（*n）は括弧の前の数字がｎ個続くことを示します。
(1)2分割以上
1,2(*n) の形で 1 から 2*n+1 まで計れる。
(2)3分割以上
1,3(*n),2 の形で 1 から 3*n+3 まで計れる。
(3)4分割以上
1,1,4(*n),3 の形で 1 から 4*n+5 まで計れる。
(4)5分割以上
1,1,1,5(*n),4 の形で 1 から 5*n+7 まで計れる。
(5)6分割以上
1,3,6(*n),2,3,2 の形で 1 から 6*n+11 まで計れる。
(6)7分割以上
1,2,3,7(*n),4,4,1 の形で 1 から 7*n+15 まで計れる。
(7)9分割以上
1,1,4,2,9(*n),3,7,3,1
または
1,4,3,4,9(*n),5,1,2,2
で 1 から 9*n+22 まで計れる。
(11)12分割以上
1,1,3,5,5,11(*n),6,6,6,1,1 で 1 から 11*n+35 まで計れる。
上の中で最大計れるものが答えに該当します。
（すべてを網羅するわけではありませんが）
2分割：1,2
3分割：1,3,2
4分割：1,1,4,3
1,3,3,2
5分割：1,1,4,4,3
1,3,1,6,2
1,5,3,2,2
6分割：1,1,1,5,5,4
1,1,4,4,4,3
1,1,6,4,2,3
1,1,6,4,3,2
1,3,6,2,3,2
1,7,3,2,2,2
7分割：1,1,9,4,3,3,2
1,3,6,6,2,3,2
8分割：1,1,12,4,3,3,3,2
1,2,3,7,7,4,4,1
1,3,6,6,6,2,3,2
9分割：1,2,3,7,7,7,4,4,1
10分割：1,2,3,7,7,7,7,4,4,1
11分割：1,1,1,20,5,4,4,4,4,3,3
1,2,3,7,7,7,7,7,4,4,1
（以下は全部かどうか、最長かどうかも不明）
12分割：1,1,1,24,5,4,4,4,4,4,3,3
1,1,4,2,9,9,9,9,3,7,3,1
1,4,3,4,9,9,9,9,5,1,2,2
13分割：1,1,3,5,5,11,11,11,6,6,6,1,1
14分割：1,1,3,5,5,11,11,11,11,6,6,6,1,1
15分割：1,1,3,5,5,11,11,11,11,11,6,6,6,1,1
16分割：1,1,3,5,5,11,11,11,11,11,11,6,6,6,1,1
17分割：1,1,3,5,5,11,11,11,11,11,11,11,6,6,6,1,1
18分割：1,1,3,5,5,11,11,11,11,11,11,11,11,6,6,6,1,1
で、12分割は58、13分割は68になります。
なお、参考のためエクセルの表を添付しました。
参考にしてください。
◆富山県 N.C さんからの解答。
１２分割の場合の最長が５８か５９かという問題ですが，
私も５８を支持します。
1,1,1,24,5,4,4,4,4,4,3,3→58 1,1,4,2,9,9,9,9,3,7,3,1→58 1,1,6,7,1,10,10,10,3,4,2,3→58 1,2,3,11,7,3,11,7,4,4,4,1→58 1,2,3,11,3,7,8,10,4,4,4,1→58 1,4,3,4,9,9,9,9,5,1,2,2→58２年ほど前に作ったプログラムをもう一度走らせてみた結果です。
◆富山県 N.C さんからの解答。
十進BASICで１００行ほどのプログラムを作ってみました。
アルゴリズムは、両端から目盛りを刻んでいく単純なものです。
プログラムを１行でも短くするため、刻み込む目盛りの個数に両端を勘定に入れましたのでご注意を。
（８分割するときは１を足して，"9"と入力する）
●青木注
プログラムは Copy & Paste してお使いください。
REM 『定規のパズル』：「目盛り節約」物差し
REM N : 刻み込む目盛りの個数。（両端も数に入れる）
REM M : 現在、調べている物差しの長さ
REM K() : 刻み込んだ目盛りの位置を保管する配列
REM L() : 現時点で，長さxを計る方法がL(x)通りある。
input prompt "刻み込む目盛りの個数（両端を含む）は":N
dim K(N),L(N*(N-1)/2)
let K(1)=0
let K(3)=1
let L(1)=1
for M=N*(N-1)/2 to N step -1
print "check";M
let K(2)=M
let L(M)=1
let L(M-1)=1
let f=step1(N,K,L,M,3,N*(N-1)/2,1,0)
if f>0 then exit for
let L(M)=0
let L(M-1)=0
next M
print "最大長は";M
end
external function step1(N,K(),L(),M,i0,R,kr0,kf0)
REM 次に刻み込む目盛りの位置を調べる。
REM i0 : 現在までに刻み込んでしまった目盛りの個数
REM R : external function step2()を参照
REM kr0,kf0 : 前回に刻み込んだ目盛りの位置。
REM kf0=0のとき、左端から距離kr0の位置に
REM kf0=1のとき、右端から距離kr0の位置に刻み込まれる。
if i0<N then
let f=0
let kr=kr0
do while L(M-kr)>0
let kr=kr+1
loop
let kr=min(kr,ceil((M-(N-i0-1))/2))
do while kr>kr0
let f=f+step2(N,K,L,M,i0+1,R,kr,1)
let f=f+step2(N,K,L,M,i0+1,R,kr,0)
LET kr=kr-1
loop
if kf0=0 then
let f=f+step2(N,K,L,M,i0+1,R,kr0,1)
end if
else
let f=1
call printout(N,K)
end if
let step1=f
end function
external function step2(N,K(),L(),M,i,R,kr,kf)
REM 次の（i番目の）目盛りを刻み込む。
REM R : N個の目盛りがあれば，最大、N*(N-1)/2通りの計り方がある。
REM しかし、同じ長さを計る方法が複数あればそれは無駄になる。
REM R は、N*(N-1)/2から無駄になったペアの個数を引いたもの。
REM kr,kf : 今回、刻み込む目盛りの位置。
REM kf=0のとき、左端から距離krの位置に
REM kf=1のとき、右端から距離krの位置に刻み込まれる。
if kf=0 then
let ka=kr
else
let ka=M-kr
end if
let K(i)=ka
for j=1 to i-1
let len=abs(ka-K(j))
if L(len)>0 then let R=R-1
let L(len)=L(len)+1
next j
if R>=M then let f=step1(N,K,L,M,i,R,kr,kf)
for j=1 to i-1
let len=abs(ka-K(j))
let L(len)=L(len)-1
next j
let step2=f
end function
external sub printout(N,K())
REM 刻み込まれた目盛りの間隔を表示するルーチン。
dim a(N)
let a(1)=K(1)
let a(N)=K(2)
for i=3 to N
let j=i-1
do while K(i)<a(j-1)
let a(j)=a(j-1)
let j=j-1
loop
let a(j)=k(i)
next i
for i=1 to N-1
print a(i+1)-a(i);",";
next i
print "合計";a(N)
end sub