프로베니우스 디오판투스 방정식과 동전 바꾸기 문제 (coin exchange problem)

선형 디오판투스 방정식의 하나
\(a_1,\ldots, a_n, b\) 를 양의 정수라 하자. 다음과 같은 부정방정식을 프로베니우스 방정식이라 한다.
\(a_1x_1+\ldots +a_nx_n=b\)
\(x_1\geq 0,\ldots, x_n\geq 0\) 인 정수해를 찾는 문제
동전의 종류가 정해져 있을 때, 만들 수 있는 액수에 대한 문제로 이해할 수 있다

\(a,b>0\), \(k\geq 0\) 인 정수라 하자.
방정식 \(ax_1+bx_2=k\)의 \(x_1, x_2\geq 0\) 인 해의 개수를 \(N(k)\) 라 하자.
생성함수
\(\sum _{n=0}^{} N(n) x^n=\frac{1}{\left(1-x^a\right) \left(1-x^b\right)}\)
성질
\(N(t+ab)=N(t)+1\)
\(\sum _{n=0}^{a b-1} N(n) x^n=\frac{1-x^{a b}}{\left(1-x^a\right) \left(1-x^b\right)}-\frac{x^{ab}}{1-x}\)
Popoviciu 의 정리
\(N(k)=\frac{k}{a b}-\left\{\frac{b^{-1}k}{a}\right\}-\left\{\frac{a^{-1}k}{b}\right\}+1\)
http://www.math.binghamton.edu/sabalka/teaching/09Spring375/Chapter10.pdf
프로베니우스 수 (실베스터의 정리)
방정식 \(ax_1+bx_2=k\)가 \(x_1, x_2\geq 0\)인 정수해를 갖지 않는 최대의 \(k\geq 0\) 값(즉, \(N(k)=0\) 이 되는 최대값)은 다음과 같다
\(g(a,b)=ab-a-b\)

d = 2 solved (probably by Sylvester in 1880’s)
d = 3 solved algorithmically (Herzog 1970, Greenberg 1980, Davison 1994) and in not-quite-explicit form (Denham 2003, Ramirez-Alfonsin 2005)
d >= 4 computationally feasible (Kannan 1992, Barvinok-Woods 2003),
otherwise: completely open
http://www.google.com/search?hl=en&tbs=tl:1&q=
수학사연표

목차