Simo K. Kivelä, 28.10.2004

Kexleruksen viiniongelma

Simon Kexlerus oli Suomen ensimmäinen matematiikan professori, joka työskenteli Turun akatemiassa sen perustamisesta lähtien vuosina 1640 – 1669. Seuraava probleema on häneltä peräisin:

Sinulla on viinejä, jotka maksavat 3, 5, 8 ja 10 markkaa pullolta. Ota yhteensä kymmenen täyttä pulloa ja tee niistä sekoitus, joka maksaa 6 markkaa pullolta. Montako pulloa kutakin viinilajia on otettava?

Ratkaisu

Pullojen määrät olkoot a, b, c ja d. Tällöin tulee seuraavien ehtojen olla voimassa:

pullot =  a + b + c + d == 10

rahat =  3 a + 5 b + 8 c  + 10 d  ==  60

On etsittävä ne ei-negatiiviset kokonaisluvut, jotka toteuttavat yhtälöt. Selvää on, että mahdolliset luvut ovat välillä [0, 10].

Yksinkertaisin ohjelmointitekniikalla toteutettava ratkaisu on tarkistaa yhtälöjen toteutuminen kaikkien vaihtoehtojen kohdalla. Vaihtoehtoja on

11^4

kappaletta.

Siis:

Do[If[pullot  &&  rahat, Print[{a, b, c, d}]], {a, 0, 10}, {b, 0, 
        10}, {c, 0, 10}, {d, 0, 10}]

Mahdollisia ratkaisuja on siis 7 kappaletta.

Nykyisillä ohjelmistoilla tällainen ratkaiseminen ei kestä kauan. Kexleruksen aikana tilanne oli toinen. Tiedossani ei ole, miten Kexlerus itse ratkaisi ongelman.

Harjoitustehtäviä

1) Tutki, miten testattavien vaihtoehtojen määrää voidaan vähentää.

2) Tutki, miten ratkaisujen lukumäärä ja laskenta-aika em. ratkaisutavassa muuttuvat, kun otettavien pullojen määrää kasvatetaan.