Zagadka z filmu

„Szklana Pułapka 3”

Dane

- nieograniczona ilość wody,

• dwa czerpaki o pojemnościach

A i B galonów,

• nieograniczony roboczy pojemnik,

• wodę można wlewać i wylewać
  czerpakami do i z roboczego
  pojemnika,

Problem

Czy można (przy zachowaniu powyższych reguł) wybrać C galonów wody?

Ogólny algorytm Euklidesa - przykład

150 = 1*150 + 0*105

105 = 0*150 + 1*105

45 = 1*150 + (-1)*105

15 = (-2)*150 + 3*105