(Calgary Reviews/Flickr. CC-BY 2.0.)
Kuvittele täysin hypoteettinen tilanne, jossa matematiikan opiskelija pistäytyy kansainvälisen pikaruokaketjun toimipisteeseen. Kyseinen opiskelija on lukenut tätä blogia ja inspiroitunut eläkeläisestä, joka maksaa käteisellä. Nälkäinen kun on, matemaatikkomme haluaa ostaa mahdollisimman monta kananugettia (jollekin "kanan" määritelmälle) — mahdollisimman vaikeasti.
Kekseliäänä nuorena hän on huomannut, että nugetteja myydään neljän, kuuden, yhdeksän ja kahdenkymmenen kappaleen laatikoissa. Siksi hän pyytää yksitoista nugettia.
Hän ei saa, mitä tilaa.
Mainituista paketeista ei voi koota yhdentoista nugetin annosta. Yksitoista on myöskin suurin mahdollinen kappalemäärä, joka ei onnistu. Ja jos nugettitarina tuntuu erittäin kaukaa haetulta, erehdyt: Tämä tunnetaan oikeasti McNugget-ongelmana. Kyllä, sitä nimeä käytetään jopa tieteellisissä artikkeleissa.
Tylsemmät ihmiset puhuvat tästä myös kolikkopulmana, koska sitä on pohdittu jo ennen kananugettien keksimistä. Yleisesti ottaen kysymys on: jos minulla on kolikoita/nugettirasioita/mitä vain, joiden suuruuksien suurin yhteinen tekijä on $1$, niin mikä on suurin kokonaisluku, jota en voi muodostaa? Se luku tunnetaan myös Frobenius-lukuna kyseisille suuruuksille. Nyt siis esimerkiksi nugettien tapauksessa luku on $g(4,6,9,20)=11$.
Kananugettipulmakin on kehittynyt aikojen saatossa: ennen vanhaan ei myyty neljän pakettia, jolloin suurin mahdoton luku oli peräti $43$. Hampurilaisketjut ovat selvästi tehneet tutkimusta optimaalisista paketeista, koska kaikki kolme suurta ketjua Suomessa myyvät neljää, kuutta tai yhdeksää nugettia. Tällöin on vain kuusi mahdotonta tilausta. (Harjoitus: mitkä ovat loput viisi?)
Yhdentoista nugetin jälkeen seuraa neljä peräkkäistä mahdollista lukua ja sen ansiosta kaikki loput onnistuvat. Jokainen myöhempi luku on nimittäin kirjoitettavissa muodossa $12+4m$, $13+4m$, $14+4m$ tai $15+4m$.
Kiinnostavaa on, että Frobenius-luvulle ei ole yhtä laskukaavaa. Kahden ja kolmen pakettikoon tapauksessa kaava on olemassa (harjoitus kiinnostuneille: ratkaise kahden paketin kaava),[1] mutta useamman vaihtoehdon kohdalla täytyy vain kokeilla. Tietokoneelle nopea algoritmi kyllä on olemassa. Sitä en tiedä, kuinka nopeita ratkaisijoita pikaruokaloiden myyjät ovat.
[1] Opettaja H:n pyynnöstä. Harjoitus tohtoriopiskelijoille: ratkaise kolmen paketin kaava.
Ei kommentteja:
Lähetä kommentti
Kommentit ovat moderoituja — yritän hyväksyä kommenttisi mahdollisimman pian. Voit kirjoittaa kommenttiin LaTeX-koodia tai yksinkertaista HTML-merkintää: lue lisää Kommentointi-sivulta.