브루스 윌리스가 주연한 할리우드 액션영화 '다이하드 3'를 보면 폭파전문가인 악당이 주인공을 공원으로 유인해 퀴즈를 내는 장면이 나온다. 폭파시간 전에 두 개의 물통을 이용해서 정확히 무게를 재도록 하는 것이었는데, 손에 땀을 쥐고 함께 고민했던 기억이 난다. 악당이 수학에 대해서 얼마나 많은 관심을 가지고 있는지 모르지만, 이러한 문제는 단순한 퍼즐로서 뿐만 아니라, 고급수학을 위한 기초과정으로서도 가치가 있다. 이번호에 소개하는 'Interactive Mathematics Miscellany and Puzzles'사이트는 매우 다양한 종류의 간단한 수학 퍼즐 문제들을 웹 사이트 상에서 직접 풀어볼 수 있도록 구현해 놓은 곳이다. 문제들을 재미있게 풀어볼 수 있을 뿐만 아니라, 해당 문제와 관련된 수학적 이론도 살펴볼 수 있어 많은 도움을 준다. 이곳의 주소는 http://www.cut-the-knot.com/front.html이며, 이번호에 실린 '3 glass'라는 퍼즐은 http://www.cut-the-knot.com/water.html, 퍼즐에 대한 설명은 http://www.cut-the-knot.com/water2.html 이다.
탁자 위에 3온스, 5온스, 8온스를 담을 수 있는 세 개의 유리잔이 놓여 있다. 처음 두 잔은 비어 있고, 마지막 잔은 8온스의 물이 차 있다. 최소한의 횟수로 물을 다른 잔으로 옮겨 담아 정확하게 4온스가 되도록 해보자.
이것은 ‘3, 5, 8과 4의 4가지 숫자간의 특수한 관계는 무엇인가?’라는 질문과 비슷한 것이다. 이들 변수 중 하나를 바꿔도 여전히 의미를 갖는 퍼즐이 되도록 하는 것은 실제로 가능할까?
예를 들어 표의 3열이 각각 유리잔 속의 물의 양을 나타낸다고 하면, 내가 처음 문제를 풀었던 방법은 다음 표와 같이 될 것이다.
0 0 8
3 0 5
0 3 5
3 3 2
1 5 2
1 0 7
0 1 7
3 1 4
여러분은 이 표에서 6을 제외한 0에서 8까지의 모든 수가 사용된다는 사실을 알아챌 수 있을 것이다. 그렇다면 6을 얻는 것은 가능할까?
6을 목표로 시도해보자.
여러분은 3, 8, 11의 용량을 사용해서 9의 양을 얻을 수 있는가?
여러분은 지금 실험수학을 하고 있는 것이다. 4가지 숫자의 여러 조합을 다루다보면 그럴듯한 가정을 이끌어 낼 수 있다. 4개로 이루어진 숫자들을 몇벌 더 찾아낼 수도 있을 것이다. 찾아냈는지를 확인해보라. 찾아냈다면 역으로 증명하도록 한다.
내가 잠시동안 풀어보고 도달한 설명(증명과정 1개를 포함해서) 예제 두 개를 이 페이지 퍼즐 바로 뒤에 제공했다. 여기 간단한 예제가 하나 있다. a, b, c, d는 3개의 (유리잔) 용적과 목표양을 의미한다.
용적 a, b, c가 다음 조건을 만족한다고 하자.
1. a=1
2. 1+b >; c/2
1 <; d <; c를 만족하는 모든 d(목표량)는 해를 가지는 퍼즐이 될 수 있음을 증명해보자.
너무 쉬운 문제인가? 원래의 퍼즐에 대한 이 일반화의 진위를 확인해 보자.
1. a <; b <; c
2. c는 4의 배수
3. a=c/2 - 1, b = c/2 + 1, d=c/2
라고 가정하면, 퍼즐은 마지막 단계에서 해결된다.
c가 4의 배수가 되어야 하는 까닭은 무엇인가? 이는 a와 b가 모두 공약수를 갖지 않는 홀수가 되기 위해서는 d=c/2가 짝수라야만 하기 때문이다.
위의 문장은 이론적으로 존재하는 정리로 알려져 있다. 해답을 구할 수 있는 방법을 알려주지는 않고, 단지 해답이 있다는 사실만을 알려준다(이것이 바로 실험수학에서 일반수학으로의 단계다).
그러나 퍼즐을 가지고 내가 한 실험에서 도출된 증명은 좀 더 보탬이 될 것이다. 다시 말하자면 그것은 퍼즐을 풀 수 있는 규칙을 알려준다.
증명:
앞으로 몇 단계를 진행하는 동안의 편의를 위해서 세개의 변수 x, y, z를 사용해 퍼즐의 현 상태를 기술한다. 여기서 x는 첫번째 유리잔의 크기(담을 수 있는 용량은 a), y는 두번째 유리잔의 크기, z는 세번째 유리잔의 크기다.
1 단계
문제를 해결하는 것은 (0, 1, c-1)을 얻는 것이라고 일단 해두자. 실제로 세번째 잔에서 첫번째 잔으로 물을 부으면 (a, 1, c-a-1)이 되며, 이것은 먼저 세운 가정에 의해 c-a-1=c-(c/2 - 1)-1=c/2=d가 되므로 퍼즐을 푸는 해가 된다.
2 단계
퍼즐의 목표를 (0, 1, c-1)로 바꾸기 위해서 약간의 마술을 사용하겠다. 즉 한 쌍의 숫자를 만들어낼텐데, 왜 다른 것들이 아니라 이 두 개를 선택했는지에 대해서는 생략하기로 한다. 내가 말할 수 있는 단 하나의 이유는 3, 5, 8의 용량을 가진 퍼즐 문제 다음에는 5, 7, 12를 이용한다는 것이다.
나는 그럴듯한 어림수(추측의 수) -후에 내가 증명하려는 전제가 될 수 있는- 를 만들어 낼 수 있는 것에 주목한다. 내가 관심을 갖고 있는 사실은 이 단계에서 필요한 두 숫자를 어떻게 정확하게 얻을 수 있는가 하는 것이다.
그래서 X = c/4, Y = c/4 -1 이라 하면, 다음 식이 성립한다.
a*X - b*Y = 1
3 단계
이제 완성하는 단계다. 계속해서 세번째 잔을 첫번째 잔에, 첫번째 잔을 두번째 잔에 붓는다.
두번째 잔이 차면, 세번째 잔에 채운다. 이렇게 Y번(2단계에서 정의한 수)하면, 첫번째 잔에는 1온스의 물이 담기고, 두번째 잔에는 0온스, 세번째 잔에는 (c-1)온스의 물이 담겨진다. 이것은 평형의 과정이다. 이제 첫번째 잔을 두번째 잔에 모두 붓고 1단계대로 한다.
증명끝
관련된 문제
제대로 된 아침식사를 하기 위해서, 한 사람이 달걀을 정확히 15분간 삶으려고 한다. 그는 7분과 11분짜리 모래시계를 가지고 있다. 그가 아침을 준비하려면 어떻게 해야 할까? 몇번이나 모래시계를 뒤집어야 할까? 모래시계를 뒤집는 최소한의 수는 얼마인가?
There are three glasses on the table -3, 5, and 8 oz. The first two are empty, the last contains 8 oz of water. By pouring water from one glass to another make at least one of them contain exactly 4 oz of water.
It′s appropriate now to ask a question ″What′s so special about the four numbers - 3, 5, 8, and 4?″ Indeed, is it possible to modify any of these parameters and still have a meaningful puzzle?
For example, the way I solved the original puzzle can be represented by the following table where in each row three numbers indicate quantities of water in the glasses:
0 0 8
3 0 5
0 3 5
3 3 2
1 5 2
1 0 7
0 1 7
3 1 4
You may notice that all numbers between 0 and 8 appear in the table with the exception of 6. Is it possible to get 6 also?
Try it with the target of 6
Can you solve the puzzle with capacities 3, 8, 11, and the target volume of 9?
We are now in the realm of Experimental Mathematics. Playing with different combinations of four numbers you may come up with a plausible hypothesis. You may try to validate it with a few more quartets of numbers. See if it works. If it does, try to prove it regorously. On this page, immediately after the puzzle I give two examples of such statements (one with a proof) at which I arrived after playing with the puzzle for a while.
Here is one simple example where I use letters a, b, c, d to denote three capacities and the target volume, respectively:
Let capacities a, b, and c satisfy the following conditions:
1. a=1
2. 1+b >; c/2
Prove that for every target volume d such that 1 <; d <; c the puzzle has a solution.
Is it too simple? Check this generalization of the original puzzle:
Assume that
1. a <; b <; c
2. c is a multiple of 4
3. a = c/2 - 1, b = c/2 + 1, d = c/2
Then the puzzle can be solved in a final number of steps.
Why should c be a multiple of 4? Because then d=c/2 is still even so that both a and b are odd with no common factors.
The above statement is what′s known as a pure existence theorem. It does not tell you how to attain the solution, it merely asserts its existence. (It′s a step from Experimental to regular Mathematics, right?). However, the proof, drawn from my experiments with the puzzle, is constructive, i.e., it provides a prescription how to solve the puzzle.
Proof:
I′ll proceed in several steps. For convenience, I′ll use a triplet (x, y, z) to describe the current state of the puzzle such that x is the quantity of water in the first glass (the one with capacity a), y - the volume of water in the second glass, and z - in the third.
Step 1.
To solve the puzzle suffice it to get (0, 1, c-1). Indeed, pouring from the third glass into the first glass you come up with (a, 1, c-a-1) which solves the puzzle for, by the conditions of our proposition, c-a-1 = c-(c/2-1)-1 = c/2 = d.
Step 2.
Having replaced the goal with (0, 1, c-1), I am going to do some magic, i.e., I am going to produce a couple of numbers without explaining why I want these two and no others. The only reason I may give is that after I played with the puzzle with capacities 3, 5, 8 and then with 5, 7, 12, I noticed something that allowed me to form a very plausible, general conjecture which later became the Proposition I am proving.
The fact I have noticed is exactly how to select the two numbers I need at this stage.
Thus, let X = c/4 and Y = c/4-1. Then the following is, of course, true
a*X - b*Y= 1
Step 3.
Now the constructive part. Keep pouring from the third glass into the first and from the first into second. When the second glass becomes full, empty it into the third one.
After this happened Y (the number from Step 2) times, the first glass will contain 1 oz of water, the second 0 oz and the third (c-1) oz. This is a consequence of the equality above. Now, empty the first glass into the second and apply Step 1.
Q.E.D.
One related problem.
For a perfect breakfast, a fellow decides to boil an egg exactly 15 minutes. He has two hour glasses - one for 7 minutes, another for 11. How should he go about preparing his breakfast? How many times will he have to turn hour glasses? What would be the minimal required number of glass turns?
