프로베니우스의 동전 문제 ★

프로베니우스의 동전 문제는, $a$원의 동전과 $b$원의 동전만으로 만들 수 없는 금액의 최댓값을 구하는 문제입니다.

(이때, $a$, $b$는 자연수입니다.)

 

공식만 알고 있었는데, 정확한 적용 범위가 헷갈려서 아예 증명을 해봅니다. 잘못된 부분이 있다면 알려주세요 :)

 

표기

• $\mathbb N_0:=\ $음이 아닌 정수 집합
• $\mathbb N_+:=\ $양의 정수 집합
  

 

$\text{Theorem. }$ 서로소인 두 정수 $a,b\in \mathbb N_+$에 대해 $an+bm(n, m\in \mathbb N_0)$로 표현할 수 없는 최대의 정수는 $ab-a-b$이다.

---

보조정리 1과 보조정리 2가 참임을 보이면 theorem도 참이다.

 

보조정리 1. $an+bm=ab-a-b$인 $(n,m)$은 존재하지 않는다.

표현이 가능하다고 가정하자.

$ab-a-b=a(b-1)+b(-1).$

$a(b-1-k)+b(-1+\frac {ak}b)(1\le k\le b-1)$꼴로 표현 될 것이다.

그런데, $b$와 $a$는 서로소이므로 $b|k$여야 한다. 하지만 $k<b\to b\nmid k$이므로 $m\not \in \mathbb Z$여서 모순이다.

$\square$

---

보조정리 2. $an+bm$로 $x\ge ab-a-b+1=(a-1)(b-1)$를 모두 표현할 수 있다.

$\{x-ak | 0\le k < b\}$는 $b$에 대한 완전 잉여계이므로 $b|(x-an')$인 $n'\in \mathbb N_0$가 존재한다. $x-an'=bm'(m'\in \mathbb Z)$이라고 하자.

이제 $m'$이 $0$ 이상임을 보이면 된다.

$bm'=x-an'\ge (a-1)(b-1)-a(b-1)=-b+1.$

$\Rightarrow b(m'+1)\ge 1.$

$\Rightarrow m'+1\ge 1/b> 0.$

$\Rightarrow m'> -1 \Rightarrow m'\ge 0.$

$\square$

---

만약 $\gcd(a,b)\neq 1$이거나, $a, b, c$의 3가지 동전이 있는 등 다른 경우에는 프로베니우스의 동전 문제 공식이 적용되지 않는다.

따라서 이럴 때에는 표를 만들어 채워나가는 방식이 좋다. 마치 에라토스테네스의 체를 이용하는 것처럼 말이다.

$0\to \{a,b,c\}$를 지우고, $a\to \{a+a,a+b,a+c\}$를 지우고, ...를 반복하면 된다. 이 때 표를 적당히 열의 수가 $a, b, c$ 중 하나가 되도록 잡고 그리면 지워지는 패턴이 눈에 더 잘 보인다. 또, $a,b,c$가 등차수열이면 $b$를 열의 길이로 잡았을 때 좌우 대칭으로 지워지기 때문에 더 편할 것이다.