水の移し替えパズル
Posted feedbacks - Ruby
* 補題 1
a, b, cについて，b >= 3の時，
(a, b, c)から(a, b - 3, c + 3)
を得るような手順があり，それは最小3手でできる．
* 補題 2
補題1は，条件のa, b, cを任意に入れ替えても成り立つ．
* 補題 3
補題1は，a = 0であっても成り立ち，かつ題意に反しない．
* 定理 4 ( 解の存在 )
a, b, cについて，a - b, b - c, c - aの3つのうち，
少なくとも1つが3の倍数ならば，
このa, b, cに対して題意を満たすような解が存在する．
* 定理 5 ( 探索の上限 )
a, b, cに対し，cに全ての水を入れるとした時，
a - bが3の倍数ならば，題意を満たすような手数が存在し，
それはmax{a, b}.
* 定理 6 ( 手数の最小 )
a, b, cに対して，題意を満たす最小の手数は，
定理4より得られる手数のうちの最小．
証明は皆さんの宿題です:-)
とか書いてみたりして．
短い証明を考えていて，時間を無駄に使ってしまったのはココだけの秘密です:-)
ということで，実際に探索する必要は無く，入力に対する算術演算だけで最小手数を求めることができるようですね．
大きな入力であっても効率的に解けそうです．
それと，一般化できそう…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | def water_puzzle_solver(a, b, c)
[[a,b],[b,c],[c,a]].select{|x,y|(x-y)%3==0}.map{|x|x.max}.min
end
## 以下テスト
p water_puzzle_solver(1, 2, 3) # not feasible
p water_puzzle_solver(3, 6, 9)
p water_puzzle_solver(4, 2, 10)
p water_puzzle_solver(827392, 65536, 122880)
100.times {| i |
a, b, c = rand(2**32), rand(2**32), rand(2**32)
puts "( #{a}, #{b}, #{c} ) -> #{water_puzzle_solver(a,b,c)}"
}
|
にしお
#3547()
Rating0/2=0.00
A, B, Cの容器があり，それぞれ水が4L, 2L, 10L入っている． ここで次の操作を繰り返す．
(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ，残りの容器に移す．」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる． くみ上げる前の容器には必ず水が入っているとする．
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ．
可能ならA=827392L，B=65536L，C=122880Lのときも求めよ．
このお題は光成さんの投稿を元に作成しました。ご協力ありがとうございます。
[ reply ]