물통 문제와 정수론의 만남
최근에 재미있는 물통 문제를 접했다. 5리터와 3리터의 플라스크를 이용해서 정확히 4리터의 물을 어떻게 측정할 수 있을까? 이 단순해 보이는 문제를 풀다 보니, 정수론적인 개념까지 생각하게 되었다.
5리터와 3리터로 4리터 만들기
먼저, 물을 직접 옮겨가며 4리터를 만드는 과정을 살펴보자.
- 5리터 플라스크를 가득 채운다.
- 5리터 플라스크에서 3리터 플라스크로 물을 옮겨 3리터 플라스크를 채운다. 이제 5리터 플라스크에는 2리터의 물이 남는다.
- 3리터 플라스크를 비운다.
- 5리터 플라스크에 남은 2리터를 3리터 플라스크로 옮긴다.
- 5리터 플라스크를 다시 가득 채운다.
- 5리터 플라스크에서 3리터 플라스크를 채울 때까지 물을 부어준다. 이미 2리터가 있으니 1리터만 부으면 된다. 결과적으로 5리터 플라스크에는 정확히 4리터의 물이 남는다.
이렇게 해서 4리터를 정확히 측정할 수 있다.
정수론적 접근: 디오판틴 방정식
이 과정을 수학적으로 설명하면 더 흥미롭다. 여기서 디오판틴 방정식이 등장한다. 디오판틴 방정식은 정수 해를 찾는 방정식으로, 일반적으로 다음과 같이 표현된다.
[ ax + by = c ]
- ( a ), ( b ): 플라스크의 부피 (5리터와 3리터)
- ( x ), ( y ): 플라스크를 채우거나 비운 횟수 (정수)
- ( c ): 목표 물의 양 (4리터)
최대공약수(GCD)와 해의 존재
5와 3의 최대공약수는 1이다.
[$ \gcd(5, 3) = 1 $]
이때, 임의의 정수 ( c )에 대해 위 방정식의 정수 해가 존재한다. 따라서 4리터를 만드는 것이 가능하다.
선형 디오판틴 방정식의 해
방정식 ( 5x + 3y = 4 )의 정수 해를 찾으면:
[ $5 \times (-1) + 3 \times 3 = 4$ ]
- ( x = -1 ): 5리터 플라스크를 한 번 비운다.
- ( y = 3 ): 3리터 플라스크를 세 번 채운다.
이러한 해를 통해 실제로 물을 채우고 비우는 과정을 수학적으로 뒷받침할 수 있다.
또 다른 문제: 7리터와 3리터로 5리터 만들기
비슷한 원리로, 7리터와 3리터 플라스크를 이용해서 5리터를 만들어보자.
- 3리터 플라스크를 가득 채워 7리터 플라스크에 부어 넣는다.
- 이 과정을 두 번 반복하면 7리터 플라스크에는 6리터의 물이 담긴다.
- 3리터 플라스크를 다시 가득 채워 7리터 플라스크가 가득 찰 때까지 부어준다. 이때 3리터 플라스크에는 2리터의 물이 남는다.
- 7리터 플라스크를 비우고, 3리터 플라스크에 남은 2리터를 옮긴다.
- 3리터 플라스크를 다시 가득 채워 7리터 플라스크에 부어 넣는다. 이제 7리터 플라스크에는 정확히 5리터의 물이 담긴다.
정수론적 설명
- ( $\gcd(7, 3) = 1 $)
- 디오판틴 방정식: ( 7x + 3y = 5 )
- 가능한 정수 해: ( x = -4 ), ( y = 13 )
디오판틴 방정식이란?
디오판틴 방정식은 정수 해를 찾는 다항식 방정식이다. 고대 그리스 수학자 디오판토스의 이름을 따왔다. 일반적으로 다음과 같은 형태를 가진다.
[ ax + by = c ]
여기서 ( a ), ( b ), ( c )는 정수이고, ( x ), ( y )를 만족하는 정수 해를 찾는 것이 목표다.
후기
단순한 물통 문제지만 곰곰히 생각하니 정수론의 개념을 이를 설명할 수 있다고 생각이 들었다. 원리를 이해하니 관련 문제도 만들기도 쉬웠다. 요새 수학에 관심이 좀 많다.