Problem darnau arian

Oddi ar Wicipedia
Jump to navigation Jump to search
Two Pence 01.jpgFive New Pence.jpg
Gydag ond darnau 2 geiniog a 5 ceiniog, ni all un wneud 3 cheiniog, ond gellir gwneud unrhyw gyfanrif uwch.

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.[1] 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.

Datganiad mathemategol y broblem[golygu | golygu cod y dudalen]

Yn nhermau mathemategol gellir datgan y broblem fel:

O ystyried cyfanrifau positif a1, a2, …, an fel bod gcd(a1, a2, …, an) = 1, canfyddwch y cyfanrif mwyaf ni ellir ei fynegi fel cyfuniad llinol cyfanrifol y rhifau hyn, h.y. fel swm k1a1 + k2a2 + ··· + knan, lle mae k1, k2, …, kn yn gyfanrifau positif neu'n sero.

Gelwir y cyfanrif mwyaf hwn yn rhif Frobenius y set {a1, a2, …, an}, ac fel arfer caiff ei ddynodir gan g(a1, a2, …, an).

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.[2] 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 {a1, a2, …, an} wedi'i ffinio yn ôl theorem Schur, ac felly mae'r rhif Frobenius yn bodoli.

Rhifau Frobenius ar gyfer n bach[golygu | golygu cod y dudalen]

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.[3]

n = 1[golygu | golygu cod y dudalen]

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

n = 2[golygu | golygu cod y dudalen]

Os yw n = 2, rhoddir y rhif Frobenius gan y fformiwla . Darganfuwyd y fformiwla hon gan James Joseph Sylvester ym 1882,[4] er weithiau caiff y ffynhonnell wreiddiol ei dyfynnu'n anghywir fel [5], lle cyflwynodd yr awdur ei theorem fel problem hamdden[6]. Dangosodd Sylvester hefyd, ar gyfer yr achos hwn, fod cyfanswm o cyfanrifau positif na ellir eu cynrychioli gan y set.

Rhoddir ffurf amgen ar gyfer yr hafaliad gan Skupień[7]: Os yw a yna, ar gyfer pob un , mae yna un pâr yn gyfanrifau nad yw'n negatif a fel bod ac .

n = 3[golygu | golygu cod y dudalen]

Bodoler fformwlâu[8] 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:

ac adroddir ei fod yn gymharol dun.[9]

Gwyddon hefyd ymddygiad cyfartalog asymptotig am dri newidyn:[10]

lle yw'r rhif Frobenius addasedig (cyfanrif mwyaf na ellir ei gynrychioli gan gyfuniadau llinol cyfanrif positif o ).

Enghreifftiau[golygu | golygu cod y dudalen]

Rhifau McNugget[golygu | golygu cod y dudalen]

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.[11] 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.[12]

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[golygu | golygu cod y dudalen]

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.

Cyfeiriadau[golygu | golygu cod y dudalen]

  1. J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press.
  2. https://math.stackexchange.com/questions/3430648/antifrobenius-number
  3. Weisstein, Eric W. "Coin Problem". MathWorld.
  4. Sylvester, James Joseph (1882). "On subinvariants, i.e. Semi-Invariants to Binary Quantics of an Unlimited Order". American Journal of Mathematics 5 (1): 134. doi:10.2307/2369536. JSTOR 2369536.
  5. Sylvester, James Joseph (1884). "Question 7382". Mathematical Questions from the Educational Times 41: 21. https://archive.org/stream/mathematicalque05unkngoog#page/n150.
  6. J. Ramírez Alfonsín (2005). The Diophantine Frobenius problem. Oxford Univ. Press. t. xiii.
  7. Skupień, Zdzisław (1993). "A generalization of Sylvester's and Frobenius' problems". Acta Arithmetica LXV.4 (4): 353–366. doi:10.4064/aa-65-4-353-366. http://matwbn.icm.edu.pl/ksiazki/aa/aa65/aa6545.pdf.
  8. Tripathi, A. (2017). "Formulae for the Frobenius number in three variables". Journal of Number Theory 170: 368–389. doi:10.1016/j.jnt.2016.05.027.
  9. M. Beck; S. Zacks (2004). "Refined upper bounds for the linear Diophantine problem of Frobenius". Adv. Appl. Math. 32 (3): 454–467. arXiv:math/0305420. doi:10.1016/S0196-8858(03)00055-1.
  10. Ustinov, A. (2009). "The solution of Arnold's problem on the weak asymptotics of Frobenius numbers with three arguments". Sbornik: Mathematics 200: 131–160. doi:10.1070/SM2009v200n04ABEH004011.
  11. Wah, Anita; Picciotto, Henri (1994). "Lesson 5.8 Building-block Numbers". Algebra: Themes, Tools, Concepts. t. 186.
  12. Weisstein, Eric W. "McNugget Number". MathWorld.