数学の問題

16Lの容器に入っている水を、9Lの容器Aと7Lの容器Bの空容器を使って8Lずつに分けます。
最低何回の移動でできますか。

この問題の解き方をわかりやすく説明してください。
お願いします。

No.2 ベストアンサー 回答者： ありものがたり 回答日時： 2022/07/28 20:27

なんか弄っているうちに 8L ができることはあると思うんだけれど...

この問題で難しいのは「最低何回」って部分かなあ。
系統的な方法はちょっと思いつかないので、
各時点でできることは全部やってみて、樹形図を振り返って
「ほら、これより前には 8L は登場してないでしょう？」とやる
のが最善ではないかと思う。

16L容器に xL, 9L容器に yL, 7L容器に zL 入っている状態を
(x,y,z) で表すとして...

1回め
(16,0,0) → (7,9,0)　；初出
(16,0,0) → (9,0,7)　；初出
２回め
(7,9,0) → (0,9,7)　；初出
(7,9,0) → (16,0,0)　;0回めで既出
(7,9,0) → (7,2,7)　；初出
(9,0,7) → (0,9,7)　；2回めで既出
(9,0,7) → (16,0,0)　；0回めで既出
(9,0,7) → (9,7,0)　；初出
3回め
(0,9,7) → (9,0,7)　；1回めで既出
(0,9,7) → (7,9,0)　；1回めで既出
(7,2,7) → (0,9,7)　；2回めで既出
(7,2,7) → (９,０,7)　；1回めで既出
(7,2,7) → (14,2,0)　；初出
(7,2,7) → (7,9,0)　；1回めで既出
(9,7,0) → (7,9,0)　；1回めで既出
(9,7,0) → (2,7,7)　；初出
(9,7,0) → (16,0,0)　；0回めで既出
(9,7,0) → (9,0,7)　；1回めで既出
４回め
...

これを 8L が登場するまで続けるのか。拷問だな。
人手でやるより PC にやらせてほうがいいような気がする。

No.3 回答者： stomachman 回答日時： 2022/07/28 22:41

容器を　大 中 小 と呼ぶことにする。

また各容器に入っている水の量[L]を「状態」と呼んで、
　　 (大に入っている水の量, 中に入っている水の量, 小に入っている水の量)
と表すことにする。「大 中 小 のどれか」→「別のどれか」という移動によって、(ある状態)→(別の状態）に遷移していくわけです。

キホン的な考え方は：
　最短1回で行ける状態は(16,0,0)→(7,9,0), (16,0,0)→(9,0,7)
　最短2回で行ける状態は(7,9,0)→(7,2,7), (7,9,0)→(0,9,7), (9,0,7)→(9,7,0)
　最短3回で行ける状態は(7,2,7)→(14,2,0), (9,7,0)→(2,7,7)
　最短4回で行ける状態は(14,2,0)→(14,0,2), (2,7,7)→(2,9,5)
…
と地道に調べていけばいいんです。（既に出てきた状態に戻っちゃう場合、それは最短ではない、ってことだから、それはボツですね。）途中から「どの状態も、移動できる新しい状態は高々1個しかない」という風になるから、拷問ってほどでもない。

　やってみれば、最短k回(k≧3)で行ける状態の数はいつも2個だけである。そして、
　最短15回で行ける状態は(1,8,7)→(8,8,0), (15,1,0)→(8,1,7)
となって、(8,8,0)に行き当たったから、これで完了です。

というわけでコタエがわかったわけですが、結果を調べてみると構造があるのがわかります。
　まず、最短16回で行ける状態の個数は0。これは「ここまでに全部で32個の状態が現れていますが、どんな移動をどれだけ繰り返しても、これら32通りの状態のどれかにしか行けない」ということを意味しています。

　また、移動の手順にも単純な構造があります。すなわち：
　 (16-K, 0, K)から出発して、以下のa,b,c,dを順にやりますと：
a　　大 → 中 で　→(7-K, 9, K)
b　　中 → 小 で　→(7-K, 9-(7-K)),7) = (7-K, 2+K,7)
c　　小 → 大 で　→(14-K,2+K,0)
d　　中 → 小 で　→(14-K,0,2+K)
だから、この手順で小の水の量が2Lだけ増える。なので、a,b,c,dを３度繰り返せば
　　 (16, 0, 0) ⇨ (14, 0, 2) ⇨ (12, 0, 4) ⇨ (10, 0, 6)
となる。さらに a,b,cをやると
　(10, 0, 6) →(1,9,6)→(1,8,7)→(8,8,0)
となって、4×3 + 3 = 15回。というわけです。

No.1 回答者： metabolian 回答日時： 2022/07/28 15:19

(A,B, C) = (0, 0, 16) ※ ①初期状態

→ (9, 0, 7) ※ ②CからAに9ℓ
→ (2, 7, 7) ※ ③AからBに7ℓ
→ (2, 0,14) ※ ④BからCに7ℓ
→ (0, 2,14) ※ ⑤Aの中身をBへ移し替え
→ (0, 4,12) ※ ②〜⑤ を繰り返す
→ (0, 6,10) ※ ②〜⑤ をもう一度繰り返す
→ (9, 6, 1) ※ ② CからAに9ℓ
→ (8, 7, 1) ※ Aから Bへ1(=7-6)ℓ
→ (8, 0, 8) ※ Bの中身をCへ移し替え
（答）15回