「教えて!ピックアップ」リリース!

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

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

A 回答 (3件)

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


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

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

1回め
(16,0,0) → (7,9,0) ;初出
(16,0,0) → (9,0,7) ;初出
2回め
(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) → (9,0,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回めで既出
4回め
...

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

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

また各容器に入っている水の量[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を3度繰り返せば
   (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回。というわけです。
    • good
    • 0

(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回
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング