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