Problem darnau arian

Mae'r broblem darnau arian (y cyfeirir ati hefyd fel y broblem darnau arian Frobenius neu broblem Frobenius, ar ôl y mathemategydd Ferdinand Frobenius) yn broblem fathemategol. Mae'n gofyn am y swm ariannol mwyaf ni ellir ei greu trwy ddefnyddio darnau arian o werthoedd penodol yn unig. Er enghraifft, y swm mwyaf ni ellir ei greu trwy ddefnyddio ond darnau arian o 3 a 5 uned o werth, yw 7 uned o werth. Gelwir yr ateb i'r broblem hon ar gyfer set penodol o werthoedd darnau arian yn rhif Frobenius y set. Mae'r rhif Frobenius yn bodoli cyn belled nad oes gan y set o werthoedd darnau arian ffactor cyffredin yn fwy nag 1.

Gydag ond darnau 2 geiniog a 5 ceiniog, ni all un wneud 3 cheiniog, ond gellir gwneud unrhyw gyfanrif uwch.

Datganiad mathemategol y broblem

Yn nhermau mathemategol gellir datgan y broblem fel:

O ystyried cyfanrifau positif a₁, a₂, …, a_n fel bod gcd(a₁, a₂, …, a_n) = 1, canfyddwch y cyfanrif mwyaf ni ellir ei fynegi fel cyfuniad llinol cyfanrifol y rhifau hyn, h.y. fel swm k₁a₁ + k₂a₂ + ··· + k_na_n, lle mae k₁, k₂, …, k_n yn gyfanrifau positif neu'n sero.

Gelwir y cyfanrif mwyaf hwn yn rhif Frobenius y set {a₁, a₂, …, a_n}, ac fel arfer caiff ei ddynodir gan g(a₁, a₂, …, a_n).

Mae'r gofyniad bod y ffactor cyffredin mwyaf (GCD) yn hafal i 1 yn angenrheidiol er mwyn i'r rhif Frobenius fodoli. Pe na bai'r GCD yn 1, yna gan ddechrau ar ryw rif m yr unig symiau posibl yw lluosrifau o'r GCD; mae'n amhosib cynrychioli unrhyw rif yn fwy nag m nad yw'n rhanadwy gan y GCD gan unrhyw gyfuniad llinol o rifau o'r set. Er enghraifft, pe bai gennych ddau fath o ddarnau arian wedi'u prisio ar 6 sent a 14 sent, byddai'r GCD yn hafal i 2, ac ni fyddai unrhyw ffordd i gyfuno unrhyw nifer o ddarnau arian o'r fath i gynhyrchu swm a oedd yn odrif; ar ben hynny, ni ellid ffurfio'r eilrifau 2, 4, 8, 10, 16 a 22 (llai na m = 24 ). Ar y llaw arall, pryd bynnag y mae'r GCD yn hafal i 1, mae'r set o gyfanrifau na ellir eu mynegi fel cyfuniad llinol cyfanrifol o {a₁, a₂, …, a_n} wedi'i ffinio yn ôl theorem Schur, ac felly mae'r rhif Frobenius yn bodoli.

Rhifau Frobenius ar gyfer n bach

Bodolir datrysiad ffurf gaeedig ar gyfer y broblem darnau arian ond am n = 1 neu 2. Ni gwyddon am unrhyw ddatrysiad ffurf gaeedig ar gyfer n > 2.

n = 1

Os yw n = 1, yna rhaid i a₁ = 1. Felly gellir ffurfio pob rhif naturiol. Felly ni fodoler rhif Frobenius mewn un newidyn.

n = 2

Os yw n = 2, rhoddir y rhif Frobenius gan y fformiwla $g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}$. Darganfuwyd y fformiwla hon gan James Joseph Sylvester ym 1882, er weithiau caiff y ffynhonnell wreiddiol ei dyfynnu'n anghywir fel , lle cyflwynodd yr awdur ei theorem fel problem hamdden. Dangosodd Sylvester hefyd, ar gyfer yr achos hwn, fod cyfanswm o $N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2$ cyfanrifau positif na ellir eu cynrychioli gan y set.

Rhoddir ffurf amgen ar gyfer yr hafaliad $g(a_{1},a_{2})$ gan Skupień: Os yw $a_{1},a_{2}\in \mathbb {N}$ a $\gcd(a_{1},a_{2})=1$ yna, ar gyfer pob un $n\geq (a_{1}-1)(a_{2}-1)$, mae yna un pâr yn gyfanrifau nad yw'n negatif $\rho$ a $\sigma$ fel bod $\sigma <a_{1}$ ac $n=\rho a_{1}+\sigma a_{2}$.

n = 3

Bodoler fformwlâu ac algorithmau cyflym am dri rhif, er y gall y cyfrifiadau fod yn hir iawn.

Mae ffiniau is ac uchaf symlach ar gyfer rhifau Frobenius ar gyfer n = 3 hefyd wedi'u pennu. Rhoddir ffin is gan Davison:

$g(a_{1},a_{2},a_{3})\geq {\sqrt {3a_{1}a_{2}a_{3}}}-a_{1}-a_{2}-a_{3}$

ac adroddir ei fod yn gymharol dun.

Gwyddon hefyd ymddygiad cyfartalog asymptotig $g$ am dri newidyn:

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

lle $f(a_{1},a_{2},a_{3})=g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}$ yw'r rhif Frobenius addasedig (cyfanrif mwyaf na ellir ei gynrychioli gan gyfuniadau llinol cyfanrif positif o $a_{1},a_{2},a_{3}$).

Enghreifftiau

Rhifau McNugget

Bocs o 20 McNugget Cyw Iâr o McDonald's.

Weithiau cyfeirir at un achos arbennig o'r broblem darnau arian hefyd fel rhifau McNugget. Cyflwynwyd fersiwn McNuggets o’r broblem darnau arian gan Henri Picciotto ac Anita Wah, a oedd wedi ei chynnwys yn eu gwerslyfr algebra. Rhif McNugget yw cyfanswm nifer McNuggets Cyw Iâr o McDonald's mewn unrhyw nifer o focsys. Yn y Deyrnas Unedig, roedd y bocsys gwreiddiol yn cynnwys 6, 9, ac 20 McNugget.

Yn ôl theorem Schur, gan fod 6, 9, ac 20 yn gymharol gysefin (relatively prime, hynny yw ei ffactor cyffredin mwyaf yw 1), gellir mynegi unrhyw gyfanrif digon mawr fel cyfuniad llinol ohonynt. Felly, mae yna rif mwyaf nad yw'n rhif McNugget. Hynny yw, mae pob cyfanrif positif arall yn rhif McNugget heblaw'r eithriadau canlynol:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, a 43. (cyfres A065003 yn yr On-Line Encyclopedia of Integer Sequences (OEIS))

Felly'r rhif mwyaf nad yw'n rhif McNugget yw 43.

Mae gwiriad syml yn dangos ni ellir prynu 43 McNuggets:

1. ni all bocsys o 6 a 9 McNugget yn unig ffurfio 43 gan mai dim ond lluosrifau o 3 y gall y rhain eu creu (ac eithrio 3 ei hun);
2. nid yw cynnwys bocs sengl o 20 yn helpu, gan nad yw'r gweddill gofynnol (23) hefyd yn lluosrif o 3; a
3. yn amlwg ni all mwy nag un bocs o 20, ynghyd â bocsys o 6 neu fwy, arwain at gyfanswm o 43 McNuggets.

Ers cyflwyno'r bocs maint Happy Meal, sy'n cynnwys 4 McNugget, y rhif mwyaf nad yw'n McNugget yw 11. Mewn rhai gwledydd bocs o 10 McNugget sydd ar gael, nid bocs o 9 McNugget. Yn y gwledydd hyn nid oes rhif mwyaf nad yw'n McNugget, oherwydd ni ellir gwneud unrhyw odrif.

Enghreifftiau eraill

Yn rygbi'r undeb, mae pedwar math o sgôr: gôl gosb (3 phwynt), gôl adlam (3 phwynt), cais (5 pwynt) a chais wedi'i drosi (7 pwynt). Trwy gyfuno'r rhain mae unrhyw gyfanswm pwyntiau yn bosibl ac eithrio 1, 2, neu 4. Mewn rygbi saith pob ochr, er bod pob un o'r pedwar math o sgôr yn cael ei ganiatáu, mae ymdrechion i goliau cosb yn brin ac mae goliau adlam bron byth yn digwydd. Mae hyn yn golygu bod sgoriau tîm bron bob amser yn cynnwys lluosrifau cais (5 pwynt) a chais wedi'i drosi (7 pwynt). Ni ellir gwneud y sgoriau canlynol (yn ychwanegol at 1, 2, a 4) allan o luosrifau o 5 a 7 ac felly nid ydynt bron byth i'w gweld mewn rygbi saith pob ochr: 3, 6, 8, 9, 11, 13, 16, 18 a 23. Er enghraifft, ni chofnodwyd yr un o'r sgorau hyn mewn unrhyw gêm yng Nghyfres Saith Bob Ochr y Byd 2014-15.

Yn yr un modd, yn y Gynghrair Bêl-droed Genedlaethol, yr unig ffordd i dîm sgorio un pwynt yn union yw os dyfarnir safety yn erbyn y tîm sy'n gwrthwynebu wrth geisio trosi ar ôl touchdown. Oherwydd dyfarnir 2 bwynt am safety mewn chwarae rheolaidd, a dyfarnir 3 phwynt ar gyfer gôl maes, mae'n bosib cael unrhyw sgôr heblaw am 1-0, 1-1, 2-1, 3-1, 4-1, 5-1 a 7-1.