PS를 위한 수학 - 프로베니우스 동전 문제

프로베니우스 동전 문제는 가끔가다 수학 문제로 나온다.

정의Permalink

자연수 $a,\,b$ 가 서로소일 때, $an+bm(n,\,m \ge 0,\,n,\,m \in \Z$ 로 만들 수 없는 최대의 자연수는 $ab-a-b$ 이다.

증명 $ab-a-b$ 는 만들 수 없다.Permalink

$ab-a-b$를 만들 수 없는 것을 증명한다.

$ab-a-b$가 $an+bm$으로 만들어 질 수 있다고 하자.

$\qquad ab-a-b=an+bm$

$\qquad ab-a-an=b+bm$

$\qquad a(b-1-n)=b(1+m)$

$\qquad gcd(a,b)=1 ~~ \Rightarrow ~~ b~\vert~ 1+n$

마찬가지로 $a~\vert~1+m$

따라서 $a \le 1+m~\&~b \le 1+n$

$\qquad a-1 \le m ~\&~ b-1 \le n$

$\qquad ab-a-b=an+bm \ge a(b-1)+b(a-1)=2ab+a-b$

따라서 $ab-a-b \ge 2ab+a-b$ 가 되어 모순이다.

그러므로 $ab-a-b$를 만들 수 없다. $\square$

증명 $ab-a-b$ 보다 큰 수는 항상 만들 수 있다.Permalink

$claim. (a-1)(b-1) \le M$의 $M$은 항상 만들어진다.

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

$gcd(a,b)=1$ 이기 때문에 디오판투스 방정식 $ax+by=1$ 인 $x,y$가 존재하고 $ax_1+by_1=M$ 인 $x_1,y_1$ 이 존재한다.

일반해는 $x=x_1+t\dfrac b{gcd(a,b)},\,y=y_1-t\dfrac a{gcd(a,b)}$ 이다.

$\dfrac b{gcd(a,b)}\to b,~\dfrac a{gcd(a,b)}\to a$ 라고 하자. $a$와 $b$는 각각 왼쪽 수들에 동일한 수를 곱한 배수이기 때문에 해로 두어도 문제없다.

$a(x_1+tb)+b(y_1-ta)=M \ge (a-1)(b-1)$

$a(x_1+tb) \ge (a-1)(b-1) - b(y_1-ta)$

$t$를 $y_1-ta \ge 0$ 이되는 최대의 정수라고 한다면, $y_1-ta \le a-1$

$a(x_1+tb) \ge (a-1)(b-1) - b(y_1-ta) \ge (a-1)(b-1)-b(a-1)=1-a$

즉, $a(x_1+tb) \ge 1-a$

$\qquad x_1+tb \ge \dfrac {1-a}a > -1$

$\qquad x_1+tb>-1$

따라서 $x_1+tb$ 는 음이 아닌 정수이고 이와 유사하게 $y_1-ta$ 도 음이 아닌 정수임을 보일 수 있으므로 $a(x_1+tb)+b(y_1-ta)=M$ 에서 $M$은 항상 만들 수 있다. $\square$