Diberikan 3 buah gelas. Gelas pertama memiliki kapasitas 5 liter dan berisi air 3 liter. Gelas kedua memiliki kapasitas 7 liter dan berisi air 4 liter. Gelas ketiga memiliki kapasitas 9 liter dan berisi air 5 liter.
Definisikan satu langkah penuangan sebagai berikut, “Memilih gelas A dan menuang isinya ke gelas B hingga salah satu kondisi ini terpenuhi: 1) Air di gelas A habis. 2) Air di gelas B penuh.”
Berapa banyak langkah penuangan minimal yang diperlukan untuk mendapatkan dua buah gelas yang masing-masing berisi air 6 liter?
Solusi
5 langkah.
Penjelasan:
| # | Aksi | Gelas A (5L) | Gelas B (7L) | Gelas C (9L) |
| 0 | – | 3L | 4L | 5L |
| 1 | Tuang Gelas A ke C | 0L | 4L | 8L |
| 2 | Tuang Gelas B ke A | 4L | 0L | 8L |
| 3 | Tuang gelas C ke B | 4L | 7L | 1L |
| 4 | Tuang Gelas B ke A | 5L | 6L | 1L |
| 5 | Tuang Gelas A ke C | 0L | 6L | 6L |
[collapse]
Disumbang oleh J.P. (ITB 2008)