프로베니우스 동전 문제

 오늘 소개할 문제는 동전의 액면가에서 파생된 이야기를 담고 있다. 요지는 다음과 같다.

서로소인 두 자연수 a, b에 대해 액면가가 a와 b인 두 동전이 있다. 이 두 동전만으로 지불할 수 없는 금액들은 얼마일까? 특히, 그런 값들의 상한이 존재할까? 한다면 지불 불능 최고 금액은 얼마일까?

 

 위 문제를 확장해 일반적인 n개의 동전에 대해 지불 불가능한 최대값을 찾는 문제를 프로베니우스 동전 문제(Frobenius coin problem)라 한다. 현재까지 n이 3이하일때만 해법이 알려져있는데, 우리의 관심은 n=2일때, 즉 두 동전만을 대상으로 한다. 

 

 필자가 이 문제를 처음 접한 것은 '재미있는 영재들의 수학퍼즐2'(박부성 지음)이지만, 단순 손계산으로 푸는 꼼수가 통하지 않도록 충남대학교 수학경시대회 버전을 소개하도록 하겠다. 2008년대회(제 12회)의 5번문제이다.

2008년을 기념하기 위해여 금액이 각각 2008원과 2009원인 두 종류의 동전을 만들었다. 이 두 종류의 동전들만으로 지불할 수 없는 가장 큰 금액을 구하고 그 이유를 밝혀라.

 

 이 문제가 어렵다면 동전의 금액을 많이 낮추어 계산해보며 파악해보자.

 

 

풀이

 두 동전에 대해서는 1882년 제임스 조세프 실베스터(James Joseph Sylvester)가 그 해법을 제시하였다. 서로소인 두 동전의 액면가가 a와 b일 때, 지불할 수 없는 최고 금액은 ab-a-b이다. 반대로 ab-a-b+1이후부터는 두 동전의 조합만으로 얼마든지 값을 치룰 수 있다. 이 금액은 (a-1)(b-1)로서 아름답게 인수분해가 된다.

 증명은

1. ab-a-b는 지불 불능이다. 2. ab-a-b+1이후부터는 지불 가능하다.

 이렇게 두 부분으로 나뉜다.

 

1. ab-a-b는 지불 불능이다.

 아니라고 가정하자. 그러면 적당한 0이상 정수 m', n'에 대해 등식 ab-a-b=m'a+n'b을 만들 수 있다. 왼쪽 항이 ab보다 값이 작으므로 오른쪽 항에서 m'은 b보다 작고 n'은 a보다 작아야한다.

 오른쪽을 0으로 만들면 ab-(m'+1)a-(n'-1)b=0외 되는데, 식을 간단하게 하기 위해 m=m'+1, n=n'+1이라 치환하면

ab-ma-nb=0

이 된다. 이 때 m과 n의 범위는 0<m<b, 0<n<a이다.

 식 양변에 nb를 더하면 ab-ma=nb가 되는데 좌항은 a로 나눠지는 반면 우항의 n은 a보다 작고 b는 a와 서로소이므로 nb는 a로 나눠질 수 없다. 따라서 이는 모순이다.

 

2. ab-a-b+1이후부터는 지불 가능하다.

 ab-a-b+1=(a-1)(b-1)이상인 값 x가 있다고 가정하자. 여기서 x, x-b, x-2b, ... , x-(a-1)b 이렇게 a개의 수를 생각하자. 이들중 a의 배수인 수가 있을까? 만약 없다면 비둘기집의 원리에 의해 a로 나눈 나머지가 같은 두 수 x-jb, x-kb가 생기고(j>k), 두 수의 차 (j-k)b는 a의 배수가 된다. 그러나 j-k는 a보다 작고, b는 a와 서로소이므로 (j-k)b는 a로 나눠질 수 없다. 따라서 x-kb꼴인 a의 배수가 존재한다. 그러면 x-kb=ja -> x=ja+kb 이로서 j가 0이상인 것만 설명하면 된다.

 ja가 최소일 때는 그 값이 x-(a-1)b이다. 그런데 x-(a-1)b ≥ (a-1)(b-1)-(a-1)b = (a-1)(b-1-b) = -a+1 따라서 j는 0이상의 정수이다.

 

우리가 증명한 바, 주어진 문제의 답은 2007×2008-1=4030055이다.

 

 

추가1.

 2번파트 증명에서 a와 b가 서로소일 때 임의의 x에 대해 x, x-b, x-2b, ... , x-(a-1)b는 모두 a로 나눈 나머지가 다르다. 이러한 수의 집합을 법 a에 대한 완전 잉여집합 또는 완전잉여계(Complete Residue System modulo a)라고 부르며 기초정수론의 매우 중요한 역할을 한다.

 

추가2.

 2008과 2009는 딱 1차이이므로 2번파트 증명을 달리 해볼 수 있다. 2008×2007부터 2008×2007+2007까지 숫자가 모두 지불가능하다는 것만 보이면 그 다음부터는 이미 구한 것에서 2008원 동전을 하나씩 더 추가하면 되므로, 2008×2007+k 꼴에 대해서만 간단히 생각해보자. (0≤k≤2007)

 2008×2007+k = 2008×2007+k(2009-2008)= 2008×2007+2009k-2008k = 2008(2007-k)+2009k

k가 2007보다 작으므로 2008×2007+k는 항상 2008원과 2009원 동전으로 지불할 수 있다는 걸 알 수 있다.

 

 

참조

en.wikipedia.org/wiki/Coin_problem

재미있는 영재들의 수학퍼즐2(박부성 지음)