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

수학노트
둘러보기로 이동 검색으로 이동

개요

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



동전 바꾸기 문제



동전 두 개일 때의 문제

  • <math>a,b>0</math>, <math>k\geq 0</math> 인 정수라 하자.
  • 방정식 <math>ax_1+bx_2=k</math>의 <math>x_1, x_2\geq 0</math> 인 해의 개수를 <math>N(k)</math> 라 하자.
  • 생성함수:<math>\sum _{n=0}^{} N(n) x^n=\frac{1}{\left(1-x^a\right) \left(1-x^b\right)}</math>
  • 성질:<math>N(t+ab)=N(t)+1</math>:<math>\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}</math>
  • Popoviciu 의 정리
<math>N(k)=\frac{k}{a b}-\left\{\frac{b^{-1}k}{a}\right\}-\left\{\frac{a^{-1}k}{b}\right\}+1</math>

여기서 <math>\{x\}</math>는 <math>x</math>의 분수부분

정리 (실베스터)

방정식 <math>ax_1+bx_2=k</math>가 <math>x_1, x_2\geq 0</math>인 정수해를 갖지 않는 최대의 <math>k\geq 0</math> 값(즉, <math>N(k)=0</math> 이 되는 최대값)은 다음과 같다

<math>g(a,b)=ab-a-b</math>



역사

  • 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
  • 수학사 연표

메모

관련된 항목들

매스매티카 파일 및 계산 리소스


사전 형태의 자료



리뷰논문, 에세이, 강의노트

관련도서

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'coin'}, {'LEMMA': 'problem'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=프로베니우스_디오판투스_방정식과_동전_바꾸기_문제_(coin_exchange_problem)&oldid=52100"