amori's blog

よろず技術系と趣味関係の雑記です。アニメの比重が高くなってます・・

ビリヤードリング

森博嗣の「すべてがFになる」にシリーズの「笑わない数学者」で以下のようなパズルが紹介されている。

「ビリヤードの球(つまり1~15)から五個球を選んでリングに並べる。

 この時、連続する球の数字の和が1~21になるようにするにはどうならべればいいか?」

こちらで実際にこのパズルをプレイできる。

 

21というのは5個のリングから作りうる最大数で、Combination(5,2)*2+1 =21 であるので、作りうる数字の和に重複がないということである。

 

5個未満については、

1個の場合は[1]で自明、

2個の場合は[1,2]の並びは自明で、1,2,3=1+2とでき、

3個の場合は、合計は3*(3-1)+1 = 7なので、[1,2,4]で、1,2,3=1+2,4,5=1+4,6= 2+4, 7=1+2+4 と、これもほとんど自明。

では4個の場合はというと、少し試行錯誤すれば[1,3,2,7]と[1,2,6,4]という2通りがすぐみつかる。

 

5個からはいきなり組合せ数が増えて、ぱっとは答えが見つからないと思う。しかし、ちょっとパターンが見えてくると試行錯誤の範囲をぐっと狭めることができ、パズルとして実にいいバランスの問題となる。ちゃんと解はユニークだし(回転・鏡像パターンを除く)

 

では、6個以上ではどうか?

6個で合計 6*(6-1)+1 = 31 なので例えば[1,2,3,4,6,15]という6個ならばビリヤードの球だけでも構成できる。とりあえず手で解いてみた。

[1, 7, 3, 2, 4, 14]
[1, 3, 6, 2, 5, 14]
[1, 3, 2, 7, 8, 10]
[1, 2, 5, 4, 6, 13]
[1, 2, 7, 4, 12, 5]

の5通りで結果的に全てビリヤードの球の範囲でリングをつくることができる。

(31通り全てを網羅していることを確かめてみてください)

しかし、手間の割には解が複数と綺麗ではないのでパズルとしてはやはり5個のパターンが秀逸なのだと言えよう。

 

7個以上では、たぶん組合せがどんどん増えるからパズルとしては面白くないだろうなあ・・とは思うものの、「ビリヤードの球で構成できる解はあるか?」という興味は残る。

例えば7個ならば[1,2,3,4,5,13,15]という数字の組合せがあるので解はなくはないような気がする。

 

さすがに手で解くのはしんどいのでrubyで解いてみた。

その結果は、

7個 

なんと解なし!

8個

[1, 4, 22, 7, 3, 6, 2, 12]
[1, 6, 12, 4, 21, 3, 2, 8]
[1, 4, 2, 10, 18, 3, 11, 8]
[1, 3, 5, 11, 2, 12, 17, 6]
[1, 3, 8, 2, 16, 7, 15, 5]
[1, 2, 10, 19, 4, 7, 9, 5]

 解は6通りあるが、15以下だけの解がないのでビリヤードリングにはならない。

9個

[1, 4, 7, 6, 3, 28, 2, 8, 14]
[1, 11, 8, 6, 4, 3, 2, 22, 16]
[1, 6, 4, 24, 13, 3, 2, 12, 8]
[1, 2, 4, 8, 16, 5, 18, 9, 10]

 解は4通り。 これもビリヤードリングにはならなかった。

 どうやら奇数個では解の個数が少ない傾向があるようだ。

 

10個以上ではざっと1000時間くらいかかりそうなので断念・・・

 

#rubyスクリプトは以下。 シンプルなGeneration & Testに回転・鏡像をできるだけ発生しないようにしたぐらいだが、これ以上Generationの総数削減の方法がちょっと思いつかない・・

 

require 'Benchmark'

def cmb( n , remain , min )
    if (2*min+n-1)*n/2 > remain then return end
    if n == 1 then
        if min <= remain then return [[remain]]
        else return

        end
    end
    return cmb(n-1, remain - min, min+1).map{|x| x.unshift(min)} + cmb(n, remain, min+1)
end


def bbcmb( n )
   case n
   when 1..3
        return cmb(n, n*(n-1)+1, 1)
   else
       return cmb(n-3, n*(n-1)+1 - 6, 4).map{|x| [1,2,3]+x } + cmb(n-3, n*(n-1)+1 - 7, 5).map{|x| [1,2,4]+x }
   end
end

 

# main routine

[1,2,3,4,5,6,7,8,9].each{|n|
    total = n*(n-1)+1
Benchmark.bm do |z|
z.report("#{n}\n"){
    dplist={}
    bbcmb(n).each{|x| # Generation of combination
        hd = x.shift
        x.permutation(n-1).each { |xx| # Generation of list
        xx.unshift(hd)
        if dplist[xx.inspect] then next # check mirror pattern
        else
            dplist[xx.reverse.rotate(-1).inspect]= true # record mirror pattern
        end
        i=0
        y=xx.map{|f| f+i ; i=f+i } # list for number combination
        chlst = {}
        y.combination(2){ |a,b| # check number combination
           dd = (a-b).abs
           if ( chlst[ dd ] ) then
               break
           else
               chlst[dd]=true
           end
           if ( chlst[ total - dd ] ) then break
           else
               chlst[total - dd] = true
           end
         } # combination
         print("----#{xx}\n") if chlst.size >= total -1 # combination found
       } # each
    }#bbcmb
}#report
end #benchmark

}#main