프로베니우스 디오판투스 방정식과 동전 바꾸기 문제 (coin exchange problem)
둘러보기로 가기
검색하러 가기
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
개요
- 선형 디오판투스 방정식의 하나
- \(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\] 여기서 \(\{x\}\)는 \(x\)의 분수부분
- 정리 (실베스터)
방정식 \(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
- 수학사 연표
메모
- 자연수 r에 대하여, 다음 부정방정식의 \(x_i \geq 0\)인 정수해의 개수\[x_0+x_1+x_2+\cdots+x_n=r\]
- 중복조합의 공식 H(n,r) =C(n+r-1,r)
- http://blog.naver.com/preciousjean?Redirect=Log&logNo=120067436228
- Moscariello, Alessio, and Alessio Sammartano. “On a Conjecture of Wilf about the Frobenius Number.” arXiv:1408.5331 [math], August 22, 2014. http://arxiv.org/abs/1408.5331.
관련된 항목들
매스매티카 파일 및 계산 리소스
사전 형태의 자료
- 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
리뷰논문, 에세이, 강의노트
- Gasarch, William. “A Complete High School Proof of Schur’s Theorem on Making Change of \(n\) Cents.” arXiv:1507.04421 [math], July 15, 2015. http://arxiv.org/abs/1507.04421.
- https://en.wikipedia.org/wiki/Schur%27s_theorem#Combinatorics
- http://math.sfsu.edu/beck/papers/frobprojects.pdf
- http://math.sfsu.edu/beck/papers/frobeasy.slides.pdf
관련도서
메타데이터
위키데이터
- ID : Q2295746
Spacy 패턴 목록
- [{'LOWER': 'coin'}, {'LEMMA': 'problem'}]