油分け算
2 つの容器で、決まった量をはかり取れるか。作れるなら、最短で何手か。
解説
考え方
A L と B L の容器を使い、T L をはかる。使える操作は、満たす、空にする、一方から他方へ注ぐ、の 3 つ。注ぐときは、注ぐ側が空になるか、受ける側が満杯になるところで止める。
なぜそうなるか
どの操作のあとも、容器の中の量は A と B の整数倍の和で表される。だから A と B の最大公約数 g の倍数しか作れない。逆に g の倍数は A と B の整数倍の和で表せる（ベズーの等式）。T が g の倍数で、大きいほうの容器に入る（T ≤ max(A, B)）なら、はかり取れる。
補足
このツールは、2 つの容器の量の組を状態として、手数の少ない順に調べ、最短の手順を求めている。
容器が 3 つの例では、8 L・5 L・3 L の容器で、満杯の 8 L を 4 L ずつに分ける問題が有名。7 回注げば分けられる。