프로베니우스 디오판투스 방정식과 동전 바꾸기 문제 (coin exchange problem)
http://bomber0.myid.net/ (토론)님의 2011년 12월 18일 (일) 08:11 판
이 항목의 수학노트 원문주소
개요
- \(a_1,\ldots, a_n, b\) 를 양의 정수라 하자. 다음과 같은 부정방정식을 프로베니우스 방정식이라 한다.
\(a_1x_1+\ldots +a_nx_n=b\) - \(x_1\geq 0,\ldots, x_n\geq 0\) 인 정수해를 찾는 문제
- 프로베니우스 동전 바꾸기 문제 (coin exchange problem)
예
- 자연수 r에 대하여, 다음 부정방정식의 \(x_i \geq 0\)인 정수해의 개수
\(x_0+x_1+x_2+\cdots+x_n=r\) - 중복조합의 공식 H(n,r) =C(n+r-1,r)
동전 바꾸기 문제
- http://math.sfsu.edu/beck/papers/frobprojects.pdf
- http://www.math.binghamton.edu/sabalka/teaching/09Spring375/Chapter10.pdf
동전 두 개일 때의 문제
- \(a,b>0\),
- 프로베니우스 수 (실베스터의 정리)
방정식 \(ax_1+bx_2=k\)의 \(x_1, x_2\geq 0\) 가 해를 갖지 않는
\(g(a,b)=ab-a-b\) - Popoviciu 의 정리
방정식 \(ax_1+bx_2=k\)의 \(x_1, x_2\geq 0\) 인 해의 개수는 다음과 같다
\(N(k)=\frac{k}{a b}-\left\{\frac{b^{-1}k}{a}\right\}-\left\{\frac{a^{-1}k}{b}\right\}+1\)
http://math.sfsu.edu/beck/papers/frobeasy.slides.pdf
\(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}\)
역사
- 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=
- 수학사연표
메모
- http://www.amazon.com/Diophantine-Frobenius-Problem-Mathematics-Applications/dp/0198568207
- Math Overflow http://mathoverflow.net/search?q=
관련된 항목들
수학용어번역
- 단어사전
- 발음사전 http://www.forvo.com/search/
- 대한수학회 수학 학술 용어집
- 한국통계학회 통계학 용어 온라인 대조표
- 남·북한수학용어비교
- 대한수학회 수학용어한글화 게시판
사전 형태의 자료
- http://ko.wikipedia.org/wiki/
- http://en.wikipedia.org/wiki/Coin_problem
- The Online Encyclopaedia of Mathematics
- NIST Digital Library of Mathematical Functions
- The World of Mathematical Equations
리뷰논문, 에세이, 강의노트
관련논문