들이가 3갤런, 5갤런인 물통을 이용해 4갤런을 재는 문제인 다이하드 문제는 많은 변형 문제를 갖고 있다.
일반화해서, 들이가 p,q인 두 물통을 이용해 J만큼의 물을 재는 방법을 알아보자.
J = ap+bq의 정수해 a,b가 존재하기 위해서는 gcd(p,q) = gcd(p,q,J)여야 함은 자명하다. a<0인 경우를 생각하자.
J는 q만큼 b번 더하고, p만큼 a번 뺀 값이다. 즉, q에 채우는 행위를 b번, p로 덜어내는 행위를 a번 하면 된다. q에 채우고, q가 p보다 크므로 q에 있는 물을 최대한 p에 덜어내고, p에 있는 물을 모두 버리고, ... 를 반복하면 채우는 행위를 a번 하고, 비우는 행위를 b번 할 수 있게 된다.
예를 들어, 3갤런, 5갤런으로 4갤런을 재는 계산을 하자.
4 = 5*2 - 3*2이므로 5갤런을 채우고, 3갤런에 붓고 3갤런을 비운다. 남은 2갤런을 3갤런에 붓고, 5갤런을 가득 채워 3갤런 통에 1갤런을 부으면 4갤런이 남는다. 마지막으로 3갤런 통을 비우면 (비우나 안비우나 동일하지만) 5갤런을 두 번 채웠고, 3갤런을 두 번 비워 디오판토스 방정식을 따라 해결한 것과 같다.
다른 예를 들면 5갤런과 17갤런으로 8갤런을 잰다고 하자.
8 = 17*4 - 5*12이다.
17갤런을 가득 채우고, 5갤런으로 3번 덜어낸다. 남은 2갤런을 5갤런으로 옮기고, 17갤런을 가득 채우고 3갤런을 5갤런으로 옮긴 뒤 덜어낸다. 남은 14갤런을 5갤런으로 두 번 덜어내고, 4갤런을 마저 5갤런으로 옮긴다. 17갤런을 가득 채우고 1갤런을 5갤런으로 옮긴 뒤 덜어낸다. 남은 16갤런에서 5갤런으로 세 번 덜어낸 뒤, 마지막 1갤런을 5갤런으로 옮긴다. 17갤런을 가득 채우고 4갤런을 5갤런으로 덜어낸 뒤, 남은 13갤런에서 한 번 5갤런으로 덜어내면 8갤런이 남는다. 이때 동일하게 17갤런을 네 번 채우고 5갤런을 12번 덜어냈으므로 디오판토스 방정식을 따라 해결한 것이다.
한편 8 = 5*5 - 17이기도 하므로 5갤런으로 17갤런에 네 번 나누어 담고 17갤런을 모두 버리면 5갤런에 3이 남는다. 17갤런에 옮겨 담고 5갤런을 추가해서 8갤런을 얻을 수 있고, 이 또한 디오판토스 방정식을 따라 해결한 것이다.
즉, 다이하드 문제는 두 정수를 계수로 하는 디오판토스 방정식을 해결하는 것과 같다. 디오판토스 방정식의 해는 한쪽이 양수, 한쪽이 음수인 해가 있다면, 반대쪽이 각각 음수, 양수인 해도 존재한다. 무엇을 채우고 무엇을 비우고는 상관 없다. 그리고, 물은 한 쪽에만 채워도 된다.
다시말해 무식하게 해결하는 방법은, 한 쪽에서는 물을 채우기만, 한 쪽에서는 덜어내기만 하면 언젠가는 해결할 수 있다.
