1. 개요
서로 다른 용량의 용기들을 이용해 원하는 양을 얻어내는 문제.
2. 문제 1
요시다 미쓰요시
[1]가 쓴 책의 <진겁기>에 수록되어 있는 문제와 유사하다. 원본에서는 11이 아닌 10의 용량의 통이 있었다. 세부적으로는 가장큰 비커/양동이에만 물이 있거나 물을 마음대로 얻을 수 있는 식이다. 바리에이션으로 모래시계를 사용하는 버전도 있다.
11L, 7L, 3L 사이즈의 통이 있다. 이들을 통해 정확히 5L의 물을 얻어야 할 때 어떻게 해야 할까?
|
- [ 해답 ]
이 문제의 해결법은
첫번째 방법
* 3L 비커에 물을 받은 후 7L 비커에 붓는 행위를 3번 하면 7L 비커가 가득 차고 3L 비커에 2L의 액체가 남는다.
* 7L 비커를 11L 비커에 옮기고 3L 비커에 있는 2L를 7L 비커에 옮긴다.
* 다시 3L를 채운 후 7L비커에 옮긴다.
두번째 방법
* 11L 비커에 물을 가득 받고
* 11L 비커에서 3L 비커로 물을 부어 8L만 남기고
* 3L 비커의 물을 7L 비커로 옮기거나 버리고
* 11L 비커에서 3L 비커로 물을 부으면 11L 비커에 5L만 남게 된다.
세번째 방법
* 11L 비커에 물을 가득 받고
* 11L 비커에서 7L 비커로 물을 부어 4L만 남기고
* 그 4L 물을 3L 비커로 옮겨 1L만 남기고
* 3L 비커를 비우고 7L비커에서 3L 비커로 물을 부어 4L를 남기고
* 그 물을 1L가 있는 11L 비커에 부으면 5L가 된다.
|
3. 문제 2
다이하드 3에도 비슷한 문제가 나온바 있으며, 내용은 다음과 같다.
저울 폭탄의 폭발을 막기 위해서는 정확히 4갤런의 물을 올려놓아야 하는데, 주어진 물통은 3갤런과 5갤런들이 통 뿐이다. 4갤런을 만들기 위해서는 어떻게 해야할까?
|
- [ 해답 ]
이 문제도 해결법이 여러가지가 있으며, 영화에서는 이렇게 해결했다.
* 5갤런 통을 가득 채운다.
* 5갤런 통에 있는 물을 3갤런 통으로 옮겨 2갤런만 남긴다.
* 3갤런 통을 비우고 5갤런 통에 남아있는 물을 3갤런 통으로 옮긴다.
* 5갤런 통을 다시 채우고 3갤런 통에 비어있는 1갤런을 채우면 5갤런 통에는 4갤런이 남는다.
|
4. 해설
비슷한 문제를 더 풀어보고 싶다면
링크에 들어가자.
- [해설 보기 / 접기]
좀 더 일반적인 해법으로 '작은 통에 있는 물을 큰 통에 옮기는 것을 반복'하다보면 원하는 물의 양을 무조건 얻을 수 있다. 문제 1의 경우 아예 3L통을 채우고 7L통을 채우는 행동을 5번 하면서 문제를 풀었고, 문제 2도 마찬가지로 3갤런들이 통을 채우고 5갤런짜리 통을 채우다 보면 마찬가지로 정답을 얻을 수 있다.
조금 더 수학적으로 접근해보면, 두 개의 통으로 만들어낼 수 있는 양은 통의 용량의 최대공약수와 관계가 있다. 바로 '''최대공약수의 배수''' 만큼은 만들어낼 수 있는 것. 예를 들어 10과 25의 경우 최대공약수가 5이므로 5의 배수(5, 10, 15, 20, 25)의 양만 만들 수 있고, 3과 5의 최대공약수는 1이므로 3갤런과 5갤런들이 통으로는 1부터 5까지 어떤 용량이건 만들 수 있게 된다. 즉, 두 수가 서로소인 경우 가장 큰 용량에 해당하는 모든 자연수의 양을 만들 수 있다는 것.
통을 채우는 것을 더한다고 하고, 통을 비우는 것을 빼는 것으로 생각하면 문제 1의 경우 3L통을 4번 채우고 7L통을 1번 비웠으므로 수식으로 나타내면 3×4-7×1=12-7=5로 5L가 정확히 나온다는 것을 알 수 있다. 마찬가지로 문제 2도 5갤런들이 통을 2번 채우고 3갤런 통은 2번 비웠으므로 5×2-3×2=4임이 나온다.
한편, 3×3-5×1=4로도 4를 만들 수 있는데, 이는 3갤런들이 통을 3번 채우고 5갤런 통에 붓다가 5갤런 통이 차면 비우는 과정을 반복하면 똑같이 4갤런 물을 만들 수 있음을 보인다. 따라서 작은 통에 물을 채워 큰 통을 붓는 것을 반복하면서 원하는 물의 양을 만들 수 있음과 동시에 반대로 큰 통에 채워서 작은 통으로 붓는 것을 반복해도 똑같은 결과를 얻을 수 있음을 알 수 있다. 즉, 사실상 노가다 하다보면 아예 불가능한 경우가 아닌 이상 언젠간 풀린다는 소리.
그래서 어떤 경우는 최소 횟수로 물을 옮기거나 사용할 물의 양을 정하는 페널티를 부여하기도 한다.
그래서 어떤 경우는 최소 횟수로 물을 옮기거나 사용할 물의 양을 정하는 페널티를 부여하기도 한다. }}}
5. 미디어 믹스
- 이 문제도 게임으로 많이 나온다. 미니게임으로 적당히 넣어두기 좋은 소재.
- 만화 트라우마에서도 잠깐 등장하며, 여기서는 범인이 3L(원본에선 3갤런)짜리 비커에 사은품으로 1L짜리 비커를 달아주는 마트에서 사오는 바람에 허무하게 클리어했다.
- 태합입지전 5에는 의술 미니게임으로 비슷한 게 등장한다. 이쪽은 3종류의 국자를 이용해서 정확히 약을 배합하는 문제.[2]
예: 8, 5, 4의 국자를 가지고 재료 1, 2, 3을 각각 8, 9, 1이 되도록 배합. 의술 레벨이 올라갈수록 재료와 만들어야 할 약, 조합해야 할 재료가 늘어난다.
- 이 문제에서 착안한 모래시계 문제도 있다.
6. 참고 자료
- 박경미 저. <박경미의 수학콘서트>. 동아시아. 2006년. 53~59p