Internetbureau Rotterdam 
Dit bericht is geplaatst op dinsdag 28 augustus 2007 om 09:36 in categorieën Nieuws. Je kunt de reacties volgen via een RSS 2.0 feed. Je kunt een reactie plaatsen, of een trackback van je eigen site plaatsen.
Wiskundemeisjes
Ionica & Jeanine
Nieuwe wiskunde
In Nieuws, door wiskundemeisjes
Jeffrey Shallit schrijft op zijn blog over een nieuw resultaat van zijn promovendus Zhi Xu: The Noncommutative Frobenius Problem is Solved. Het aardige aan dit werk is dat het ook voor buitenstaanders redelijk makkelijk te begrijpen is. Shallit weet ook hoe hij dingen moet uitleggen, hij begint zijn stuk met het Chicken McNuggets probleem. McNuggets werden oorspronkelijk verkocht in doosjes met 6, 9 of 20 stuks. Wat is het grootste aantal McNuggets dat je NIET kunt kopen door een aantal van deze doosjes te kopen? Dit probleem staat (tot mijn verbazing) ook op Mathworld.
Het antwoord is 43. Elk groter aantal kun je samenstellen uit doosjes van 6, 9 en 20 stuks. Dit is een speciaal geval van het Frobenius probleem: stel je hebt een aantal positieve, gehele getallen met de grootste gemene deler gelijk aan één. Wat is het grootste getal dat je niet kunt maken door deze getallen (met positieve gehele coëfficienten) bij elkaar op te tellen? Voor twee en drie getallen is dit probleem efficiënt op te lossen, maar voor grotere aantallen is het een moeilijk probleem.
Shallit generaliseerde dit probleem naar woorden oftewel rijtjes symbolen. Zijn student haalde in die generalisatie een mooi resultaat. Lees de rest zelf op zijn blog Recursivity. Op arXiv kun je ook het complete wiskundige artikel van Xu en Shallit vinden: The Frobenius Problem in a Free Monoid.
(Ionica)
