油分け問題(8)考察1を示します。
(8)考察1
5㍑、3㍑、2㍑入る3種類のコップ(A,B,C)がある。
5㍑のコップAに油が一杯入っているとき、他のコップB,コップCを使って、
1㍑を量り分ける方法は何通りあるか考察する。
ただし、あるコップから他のコップに油を移す場合、どちらかのコップが
空になるか、一杯になるときにやめるとする。
●考え方
試行錯誤しながら解を探索するバックトラックという考え方を紹介する。
5㍑のコップAにa㍑、3㍑のコップBにb㍑、2㍑のコップCにc㍑入っている状態を(a,b,c)で表す。最初の状態は(5,0,0)である。
この状態から図のように2つの状態(2,3,0)と(3,0,2)が得られ、2つの状態は、
つぎのように表すことができる。
5㍑のコップAから3㍑のコップBに油3㍑を移すと状態(2,3,0)が得られ、5㍑のコップAから2㍑のコップCに油2㍑を移すと状態(3,0,2)が得られる。
このように、ある状態から得られる状態をつぎつぎに求めていくと、つぎのような図(木とよぶ)が構成できる。(5,0,0)からある状態までの経路中に同じ状態がある場合には、その状態を枠で囲み枝分かれを停止する。繰り返しになるからである。
また、a,b,cのいずれかが1になった状態も解が得られたので枝分かれを停止する。
この図は、すべての状態を示している。(5,0,0)から出発して、反時計回りにたどれば、すべての解が得られる。
この結果、(5,0,0)からa,b,cのいずれかが1になった状態(a,b,c)までの経路が求める量り分けに対応することになる。5通りの方法があり、量り分けの最小回数は2回である。
解(1): (5,0,0) → (2,3,0) → (0,3,2) → (3,0,2) → (3,2,0) → (1,2,2)
解(2): (5,0,0) → (2,3,0) → (2,1,2)
解(3): (5,0,0) → (3,0,2) → (0,3,2) → (2,3,0) → (2,1,2)
解(4): (5,0,0) → (3,0,2) → (3,2,0) → (2,3,0) → (2,1,2)
解(5): (5,0,0) → (3,0,2) → (3,2,0) → (1,2,2)