동전 문제

동전 문제(수학자 페르디난드 프로베니우스 다음으로 프로베니우스 동전 문제 또는 프로베니우스 문제라고도 한다)는 특정 종파의 동전만을 사용하여 얻을 수 없는 가장 큰 화폐량을 요구하는 수학적인 문제다.^[1] 예를 들어 3단위와 5단위의 동전만으로 얻을 수 없는 가장 큰 금액은 7단위가 된다. 주어진 동전 세트에 대한 이 문제의 해결책은 그 세트의 프로베니우스 번호라고 불린다. 프로베니우스 수는 동전 세트가 1보다 큰 공통점이 없는 한 존재한다.

x와 y라는 두 개의 다른 동전 액면만이 있을 때 프로베니우스 숫자에 대한 명시적인 공식은 xy - x - x - y이다. 만약 화폐단위의 수가 3개 이상이라면, 명시적인 공식은 알려져 있지 않지만, 일정한 수의 화폐단위의 경우, 다항 시간(입력을 구성하는 화폐단위의 로그)에 프로베니우스 숫자를 계산하는 알고리즘이 있다.^[2] 알려진 알고리즘은 코인 단위 수에서 다항식 시간이며, 코인 단위 수가 원하는 만큼 많을 수 있는 일반적인 문제는 NP-hard이다.^[3][4]

성명서

수학 용어로 이 문제는 다음과 같이 명시될 수 있다.

gcd(a₁, a₂, a, ..., a_n) = 1과 같은_n 양의 정수₁, a₂, ...가 주어지면 이들 숫자의 정수 원뿔형 조합으로 표현할 수 없는 가장 큰 정수를 발견하게 된다.

ka₁₁ + ka₂₂ + ···+ka_nn,

여기서 k₁, k₂, ..., k는_n 음이 아닌 정수다.

이 가장 큰 정수는 집합 { a₁, a₂, ..., }의_n 프로베니우스 번호로 불리며, 보통 g(a₁, a₂, ..., a_n)로 표시된다.

프로베니우스 숫자가 존재하기 위해서는 가장 큰 공통점수(GCD)가 1이 되어야 한다는 요건이 필요하다. 만약 GCD가 1이 아니라면, 어떤 숫자 m에서 시작할 수 있는 유일한 합은 GCD의 배수량이다; GCD에 의해 분리되지 않는 m 이후의 모든 숫자는 집합에서 숫자의 어떤 선형 결합으로 나타낼 수 없다.^[5] 예를 들어, 만약 당신이 6센트와 14센트로 평가되는 두 종류의 동전을 가지고 있다면, GCD는 2와 같을 것이고, 그러한 동전을 몇 개 결합하여 홀수 숫자인 합을 만들 방법이 없을 것이다. 게다가, 2, 4, 8, 10, 16, 22 (m=24 이하)도 역시 형성될 수 없었다. 한편 GCD가 1과 같을 때마다 { a₁₂, a, ...}의_n 원뿔 조합으로 표현할 수 없는 정수 집합이 슈르의 정리에 따라 경계되고, 따라서 프로베니우스 수가 존재한다.

프로베니우스(소수 n)의 숫자

이 섹션은 갱신되어야 한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 최근 이벤트 또는 새로운 사용 가능한 정보를 반영하도록 이 문서를 업데이트하십시오.(2017년 10월)

폐쇄형 솔루션은 n = 1 또는 2인 경우에만 동전 문제에 대해 존재한다. n > 2에 대해 알려진 폐쇄형 솔루션은 없다.^[4]

n = 1

n = 1이면 a₁ = 1이므로 모든 자연수가 형성될 수 있다. 따라서 한 변수에 프로베니우스 숫자가 존재하지 않는다.

n = 2

만약 nx2,Frobenius 수가 공식 g(1하나, 2)에서 볼 수 있다 12− 1− 2{\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}. 이 공식이 있다는 사실에 의해 제임스 조셉 실베스터에 1882,[6]었으나 이 원래의 근원은 가끔 잘못 인용 as,[7]에서 작가 그의.한 orems 오락성 문제^[8](그리고 프로베니우스 숫자에 대한 공식은 명시적으로 명시하지 않았다). 실베스터는 또한 이 경우에 대해 총 $N{\displaystyle }$(${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{2\mathrm{}}_{}}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle {}_{}{}_{}}$- ${\displaystyle 1}$) = ( ${\displaystyle {2\mathrm{}}_{}}$- ${\displaystyle 1}$)${\displaystyle }$/$$2 {\$displaystyle$ N$(a_{1},a_{2}}=(a_${1$}-1$)(a_{$2}-1)/2}$의 비표현적$$(양) 정수가 있음을 증명했다.

$g{\displaystyle }$( 1 ,${\displaystyle {}_{}{2\mathrm{}}_{}}$ ) ${\displaystyle g(a_{1},a_{2}}$에 대한 또 다른 형태의 방정식은 다음과 같은 제안에서 Skupień에^[9] 의해 제공된다$$. If ${\displaystyle a_{1},a_{2}\in \mathbb {N} }$ and ${\displaystyle \gcd(a_{1},a_{2})=1}$ then, for each ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$, there is exactly one pair of nonnegative integers ${\displaystyle \rho }$ and ${\displaystyle \sigma }$${\displaystyle }$${\$$displaystyle \probma$$\probma$probma <$a_${1}, n${\displaystyle }$= ${\displaystyle {1\mathrm{}}_{}}$ +${\displaystyle {}_{}}$+ ${\displaystyle {a\mathrm{}}_{}}$ 2 ${\$

그 공식은 다음과 같이 증명된다. Suppose we wish to construct the number ${\displaystyle m\geq (a_{1}-1)(a_{2}-1)}$. Note that, since ${\displaystyle \gcd(a_{1},a_{2})=1}$, all of the integers ${\displaystyle m-ja_{2}}$ for ${\displaystyle j=0,1,\ldot$$s ,a_{1}-1}$ are mutually distinct modulo ${\displaystyle a_{1}}$. Hence there is a unique value of ${\displaystyle j}$, say ${\displaystyle j=\sigma }$, and a nonnegative integer ${\displaystyle \rho }$, such that ${\displaystyle m=\rho a_{1}+\sigma a_{2}}$: Indeed, ${\displaystyle \rho \ge }$${\displaystyle \rho \geq 0}$ because ${\displaystyle \rho a_{1}=m-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1}$.

n = 3

공식과^[10] 빠른 알고리즘은^[11] 손으로 하면 계산이 매우 지루할 수 있지만 세 개의 숫자로 알려져 있다.

n = 3에 대한 프로베니우스 숫자에 대한 간단한 하한과 상한도 결정되었다. 데비슨으로 인한 점근 하한

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3}+a_{1}+a_{2}+a_{3}}}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}}}}}$

상대적으로 뾰족합니다실제 한계(매개 변수 관계에 의해 정의된, f(z(나는)과[12](ff{\displaystyle}여기서 1의 긍정적인 정수 결합에 의한 가장 큰 정수 대표적인 아닌 수정 프로베니우스. FerdinandGeorg. 수, 2,3{\displaystyle a_{1},a_{2},a_{3}}이다.)비교)=9i.${\displaystyle f(z(i))=9i^{2}+54i+79}$ where ${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)}$) shows that the approximation is only 1 less than the true value as ${\displaystyle i\rightarrow \infty }$. It is conjectured that a similar parametric upper bound (for values of ${\displaystyle a_{1},a_{2},a_{3}}$ that are pairwise-coprime and no element is representable by the others) is ${\displaystyle f(z(i))=6i^{2}+19i+13}$ where ${\displaystyle z(i)=a_1{a}_2{a}_3=(3i+}$${\displaystyle 2}$)${\displaystyle }$( ${\displaystyle 3}$ ${\displaystyle i}$+ 3${\displaystyle }$)${\displaystyle }$( ${\displaystyle 6}$ ${\displaystyle \mathrm{i}}$+ ${\displaystyle 7}$) ${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+2)(3i+3)(6i+7$

세 변수에 대한$$ $f{\displaystyle }$ ${\displaystyle f}$의 점근 평균 동작도 알려져 있다.^[13]

${\displaystyle f(a_{1},a_{2},a_{3})\심(\frac {8}{8}{\pi }}{\sqrt{a_{1}a_{2}a_{3}}}}}}},$

특수 세트용 프로베니우스 숫자

산술 시퀀스

간단한 공식은 산술 순서에서 정수 집합의 프로베니우스 수에 대해 존재한다.^[14] gcd(a, d) = 1인 정수 a, d, w:

${\displaystyle g(a,a+d,a+2d,\floor,a+wd)=\좌측(\좌측)\floor {a-2}{w}\우측(오른쪽)a+d(a-1)}$

위의 $n{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle n=2}$케이스는$$ 이 공식의 특별한 케이스로 표현될 수 있다.

In the event that ${\displaystyle a>w^{2}-3w+1}$, we can omit any subset of the elements ${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$ from our arithmetic sequence and the formula for the Frobenius number remains the same.^[15]

기하학적 시퀀스

기하학적 배열로 이루어진 세트의 프로베니우스 번호에 대한 폐쇄형 폼 솔루션도 존재한다.^[16] gcd(m, n) = 1인 정수 m, n, k:

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\n^{n-m-n)}=n^{k-1}(n-n-n)+{\m^{n-1}(m^{k-1}){m-n}}}}.}$

변수들 사이의 대칭성도 표시하는 간단한 공식은 다음과 같다. Given positive integers ${\displaystyle a,b,k}$, with ${\displaystyle \gcd(a,b)=1,}$ let ${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$. 그러면

${\displaystyle g(A_{k}(a,b))={\bma }_{k+1}(a,b)-{\bma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$

여기서 ${\displaystyle {}_{}b}$) ${\displaystyle {\sigma }_{k}(a,$${\displaystyle b}$$)}$은 ${\displaystyle {Ak}_{}b}$)${\displaystyle }$. ${\displaystyle A_{k}(a,b$)의 모든 정수의 합을 나타낸다$$$.$$}$

예

맥너겟 수

동전 문제의 한 가지 특별한 경우를 맥너겟 번호라고도 한다. 맥너겟 버전의 동전 문제는 헨리 피치오토에 의해 소개되었는데, 그는 그것을 아니타 와와 공동저술한 그의 대수 교과서에 포함시켰다.^[18] 피치오토는 1980년대에 맥도날드에서 아들과 식사를 하면서 냅킨으로 문제를 해결하면서 어플리케이션을 생각했다. 맥도날드 치킨 맥너겟의 총 개수는 어느 박스에나 들어 있는 맥도날드 치킨 맥너겟 수입니다. 영국에서는 원래의 박스(해피밀 크기 너겟 박스 도입 이전)가 6, 9, 20 너겟이었다.

슈르의 정리에 따르면 6, 9, 20은 (설정) 비교적 프라임이기 때문에 충분히 큰 정수는 이 세 개의 (비 음, 정수) 선형 조합으로 표현할 수 있다. 따라서 가장 큰 비McNugget 수가 존재하며, 이 수보다 큰 정수는 모두 McNugget 수이다. 즉, 모든 양의 정수는 McNugget 번호로, 예외의 수가 유한하다.

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, 43(OEIS에서 순서 A065003)이다.

합계	0	1	2	3	4	5
+0	0:0,0,0	1: —	2: —	3: —	4: —	5: —
+6	6:1,0,0	7: —	8: —	9:0,1,0	10: —	11: —
+12	12:2,0,0	13: —	14: —	15:1,1,0	16: —	17: —
+18	18:3,0,0	19: —	20:0,0,1	21:2,1,0	22: —	23: —
+24	24:4,0,0	25: —	26:1,0,1	27:3,1,0	28: —	29:0,1,1
+30	30:5,0,0	31: —	32:2,0,1	33:4,1,0	34: —	35:1,1,1
+36	36:6,0,0	37: —	38:3,0,1	39:5,1,0	40:0,0,2	41:2,1,1
+42	42:7,0,0	43: —	44:4,0,1	45:6,1,0	46:1,0,2	47:3,1,1
+48	48:8,0,0	49:0,1,2	50:5,0,1	51:7,1,0	52:2,0,2	53:4,1,1
+54	54:9,0,0	55:1,1,2	56:6,0,1	57:8,1,0	58:3,0,2	59:5,1,1
총 0 - 59개의 너겟에 대한 가능한 상자 조합 세트. 각 세 쌍둥이는 각각 6개, 9개, 20개의 상자 수를 나타낸다.

따라서 가장 큰 비 McNugget 숫자는 43이다.^[19] 43보다 큰 정수가 McNugget 번호라는 사실은 다음의 정수 파티션을 고려함으로써 알 수 있다.

${\displaystyle 44=6+9+9+20}$

${\displaystyle 45=9+9+9+9}$

${\displaystyle 46=6+20+20}$

${\displaystyle 47=9+9+9+9+20}$

${\displaystyle 48=6+6+9+9+9}$

$(\displaystyle 49=9+20+20}$

위의 적절한 칸막이에 6s의 숫자를 더하면 더 큰 정수를 얻을 수 있다.

또는 ${\displaystyle \text{lcm}(9,}$ ${\displaystyle 20}$)${\displaystyle }$= ${\displaystyle 180}$ ${\displaystyle {\textrm${\lcm$}(9,20)=180}$ 및$$ 6 ${\displaystyle 180\mathrm{}}$ ${\displaystyle$ 6 $180}$에 대해 제시된 $공식$을 이전에 n =${\displaystyle 3}$ ${\displaystyle n=3}$에 적용하여 솔루션을 얻을 수도 있다$.$^{[dubious – discuss]}

${\displaystyle g(6,9,20)={\textrm {lcm}+{\textrm {lcm}-6-9-20=18+60-35=43}$

더욱이 간단한 점검은 다음과 같이 43개의 McNuggets를 실제로 구매할 수 없다는 것을 보여준다.

1. 6박스와 9박스는 3의 배수만을 만들 수 있기 때문에 단독으로 43을 형성할 수 없다(3개 자체를 제외).
2. 필요한 나머지(23)도 3의 배수가 아니기 때문에 20의 한 상자를 포함해도 도움이 되지 않는다.
3. 사이즈 6 이상의 상자로 보완된 20개 이상의 상자는 총 43개의 McNuggets로 이어질 수 없다.

4피스 해피밀 사이즈 너겟 박스가 출시된 이후 가장 큰 비 맥너겟 번호는 11이다. 9피스 사이즈를 10피스 사이즈로 교체하는 국가에서는 홀수를 만들 수 없기 때문에 가장 큰 비 맥너겟 번호가 없다.

기타 예

럭비 유니온에서는 페널티 골(3점), 드롭 골(3점), 트라이(5점), 컨버전트 트라이(7점) 등 4종류가 있다. 이러한 점들을 결합함으로써 1, 2, 4를 제외한 모든 점들의 합계가 가능하다. 럭비 세븐에서는 네 가지 유형의 점수가 모두 허용되지만 페널티 골 시도는 드물고 드롭 골은 거의 알려지지 않았다. 팀 점수는 거의 항상 시도(5점)와 전환 시도(7점)의 배수로 구성된다는 뜻이다. 다음 점수(1, 2, 4 추가)는 5와 7의 배수로 만들 수 없으므로, 3과 6과 8과 9와 11과 13과 16과 18과 23은 거의 볼 수 없다. 예를 들어, 이러한 점수는 2014-15년 세븐스 월드 시리즈 어느 경기에서도 기록되지 않았다.

마찬가지로, 미식축구의 경우, 팀이 정확히 1점을 득점할 수 있는 유일한 방법은 터치다운 후 전환을 시도할 때 상대 팀에 안전이 부여되는 것이다. 정규 플레이에서 안전이 보장된 점수는 2점, 필드골은 3점이 부여되기 때문에 1-0, 1–1, 2–1, 3–1, 4–1, 5–1, 7–1 이외의 모든 점수가 가능하다.

적용들

^[20]

쉘포트 시간 복잡성

Shellsort 알고리즘은 시간 복잡성이 현재 열린 문제인 분류 알고리즘이다. 최악의 경우 복잡성은 주어진 양의 정수 순서의 프로베니우스 숫자에 따라 주어질 수 있는 상한을 가진다.

최소 활중량

페트리 네트는 분산 컴퓨팅의 문제를 모델링하는 데 유용하다. 특정 종류의 페트리 그물, 즉 보수적인 가중 회로의 경우, 주어진 가중치를 가진 "상태" 또는 "표식"이 "실시간"일 수 있는 것이 무엇인지 알고 싶다. 최소 활중량을 결정하는 문제는 프로베니우스 문제와 맞먹는다.

다항식의 확장된 검정력 항

일변량 다항식이 어떤 전력으로 상승할 때, 다항식의 지수를 정수 집합으로 취급할 수 있다. The expanded polynomial will contain powers of ${\displaystyle x}$ greater than the Frobenius number for some exponent (when GCD=1), e.g. for ${\displaystyle (1+x^{6}+x^{7})^{n}}$ the set is {6, 7} which has a Frobenius number of 29, so a term with ${\displaystyle x^{29}}$ will never app$n{\displaystyle }$ ${\displaystyle n}$의 값과 $n{\displaystyle }$ ${\displaystyle n}$의 일부 값에 대한 ear는 29보다 큰$$ $x{\displaystyle }$ ${\displaystyle x}$의 검정력을 갖는 항을 제공할 것이다$$. When the GCD of the exponents is not 1 then powers larger than some value will only appear if they are a multiple of the GCD, e.g. for ${\displaystyle (1+x^{9}+x^{15})^{n}}$, powers of 24, 27, ... will appear for some value(s) of ${\displaystyle n}$ but never values larger than 24 that are not multip3의 레스(1-8, 10-14, 16, 17, 19-23)

참고 항목

• 우표 문제
• 변화 문제
• 실버 코니지
• 숫자 세미그룹

참조

외부 링크

• 치킨 맥너겟 43개 주문 방법 – 번호표