Viime blogauksessa päätäni särki eräs matemaattinen ongelma ja sen koodimuotoinen ratkaisu. Ongelma kuului tähän tapaan: On kaksi lukua, joiden summa on enintään 100. Henkilö A tietää niiden tulon ja B summan. B sanoo A:lle: “Tiedän ettet voi tietää mitä luvut ovat.”, johon A vastaa: “Nyt tiedän.” ja B: “Nyt minäkin.” Mitkä luvut ovat? Kuten tarkkasilmäisimmät huomaavat, ongelmaa on viime kerrasta hieman tuunattu…

Useampi lukija innostui ratkomaan ongelmaa Skrollin Facebook-seinällä ja oikeasta vastauksesta syntyi keskustelua. Päädyinpä itsekin jatkamaan ohjelmointia, sillä pohdiskelu paljasti virheen omassakin ajattelussani – olin tehnyt ongelmaan liittyvän ensimmäisen lukukarsinnan käsin ja kovakoodannut sen koodiini. Ja olin tehnyt sen tietenkin väärin! Mitä opimme? Älä koskaan luota päässälaskuun… tai kovakoodaa turhia asioita…

Toinen asia, mikä tuli vastaan ongelman jakamisen jälkeen, oli se, että blogin lähdesivulla oli epätarkkuus tehtävänannossa. Siinä on ero, sanooko, että kaksi lukua ovat väliltä 2-50 (kuten alkujaan ratkoimme) tai että sanoo, että lukujen summa on enintään 100.

Nimittäin ensimmäisessä tapauksessa ongelmaan ei ole ratkaisua. Sama henkilö, joka tutustutti minut alkujaan tähän tehtävään, yritti ongelmaa ratkaistaessaan debugata koodiaan pitkään vain tajutakseen, että siinä ei ollut mitään debugattavaa – vastausjoukko oli kuin olikin tyhjä, kun lähtöjoukko lukupareja oli liian suppea.

Wikipediasta löytyi oikea tehtävänanto ja ratkaisu.

Lupasin julkaista oman ratkaisuni jonkin ajan kuluttua ongelman jakamisesta, mutta oma koodi alkoi hävettää liikaa. Törmäsin tähän paljon elegantimpaan ratkaisuun – se on Pythonia:

from collections import Counter

#Yleisyyden kärsimättä voidaan olettaa että ensimmäinen luvuista on suurempi tai yhtäsuuri kuin toinen
#(koska muuten lukujen paikat voidaan vaihtaa, jolloin yllä mainittu pätee)
#
#Näin listassa olevan parin (x,y) permutaatio (y,x) on listassa joss y = x
#
#Pythonin välit ovat puoliavoimia, joten ylärajaan lisätään yksi
pairs = [(x,y) for x in range(2, 100) for y in range(2, x + 1) if x+y < 100]

#Sulo1: Minä en tiedä mitkä luvut ovat
# -> Täytyy olla useampia pareja x,y joilla on sama summa
sums = Counter([x+y for x,y in pairs])
pairs_Sulo1 = [(x,y) for x,y in pairs if sums[x+y]>1]

#Tuukka1: Minä en tiedä mitkä luvut ovat
# -> Täytyy olla useampia pareja x,y joilla on sama tulo
prods = Counter([x*y for x,y in pairs_Sulo1])
pairs_Tuukka1 = [(x,y) for x,y in pairs_Sulo1 if prods[x*y] > 1]

#Sulo2: Tiesin ettet voi tietää mitkä luvut ovat
# -> lukujen summasta voi päätellä, että tulo ei ole yksikäsitteinen:
# Millään x, y joilla tulo on yksikäsitteinen ei ole tätä summaa
sums2 = [x+y for x,y in pairs_Sulo1 if prods[x*y] == 1]
pairs_Sulo2 = [(x,y) for x,y in pairs_Tuukka1 if not (x+y) in sums2]

#Tuukka2: Nytpä minä tiedän
# ->Jäljelle jäävien lukujen joukossa tulo xy on mahdollista muodostaa vain yhdellä tavalla
prods2 = Counter([x*y for x,y in pairs_Sulo2])
pairs_Tuukka2 = [(x,y) for x,y in pairs_Sulo2 if prods2[x*y] == 1]

#Sulo3: Nyt minäkin tiedän
# ->Jäljelle jäävien lukujen joukossa summa x+y on mahdollista muodostaa vain yhdellä tavalla
sums3 = Counter([x+y for x,y in pairs_Tuukka2])
pairs_Sulo3 = [(x,y) for x,y in pairs_Tuukka2 if sums3[x+y] == 1]

print( "Vastaus on %d ja %d"%pairs_Sulo3[0] )

Ratkaisussa karsitaan vaihe vaiheelta potentiaalisten lukuparien joukko siihen yhteen mahdolliseen, joka jää jäljelle.

Ratkaisun laatinut Antti Valli kritisoi itse ratkaisuaan siitä, että se ei pyri ymmärtämään matemaattisesti sitä, millaisia ominaisuuksia esim. lukujen tulolla tulee olla, jotta sen voisi tulkita vain yhdellä tavalla kahden luvun tulona. (Vastaus: jos se on kahden alkuluvun tulo.) Koodi yksinkertaisesti laskee kaikkien mahdollisten lukuparien summan/tulon ja katsoo, kuinka monta eri lukuparia voi muodostaa tietyn summan/tulon. A:n ja B:n – tai tässä tapauksessa Tuukan ja Sulon – esittämät väitteet liittyvät juurikin tähän määrään. Toisaalta tässä on mielestäni juuri ratkaisun eleganttius.

Oma ratkaisuni ei karsi lukupareja vaiheittain, vaan perustuu siihen, että olen päätellyt A:n ja B:n sanomisista sen, millainen ratkaisu-lukuparin tulee olla:

A tietää lukujen x ja y tulon x*y, B tietää lukujen summan x+y.

(1) B sanoo, että A ei voi tietää lukuja x ja y tulon perusteella. Siispä summaa x+y ei voi esittää kahden alkuluvun summana.

(2) A sanoo, että nyt hän tietää luvut x ja y. Siispä voi olla vain yksi tapa tulkita tulo x*y kahtena lukuna x' ja y' (x'*y'=x*y) siten, että lukua (x'+y') ei voi tulkita kahden alkuluvun summana.

(3) B sanoo, että nyt hänkin tietää luvut x ja y. Siis kaikista mahdollisista tavoista tulkita x+y kahden luvun summana x'+y' (x'+y'=x+y) vain yhdelle pätee: Tavoista tulkita x'*y' kahtena lukuna a ja b, siten että a*b=x'*y', vain yhdelle pätee: a+b ei ole mahdollista esittää kahden alkuluvun tulona.

Koodini generoi ensin kaikki mahdolliset sataa pienemmät summat, joita ei voi ilmaista kahden alkuluvun summana, ja lisää ne summalistaan. Tämän jälkeen se käy läpi kaikki tavat tulkita summa kahden luvun summana (esim. luvun 23 voi tulkita summana 2+21 mutta myös summana 6+15). Jokaisen tulkinnan kohdalla se käy läpi, miten saatujen lukujen tulon voi tulkita kahden luvun tulona. (Esim. 6*15=90 voi tulkita myös 2*45.)

Näin se laskee, kuinka moni tapa generoi sellaisen summan, joka löytyy summalistasta. Jos tavoista tulkita tulo lukuparina tasan yksi löytyy summalistasta, tapa kelpaa. Jos tavoista tulkita summa lukuparina tasan yksi kelpaa, summa on ratkaisu.

Seuraavaksi olisi tarkoitus ratkoa sellaista ongelmaa, jossa on sata vankia, sadistinen matemaatikko-vanginvartija, satunnaisuuselementti ja Pakostrategia. Mutta sitä varten ajattelin ensin ohjelmoida koodin, joka testaa valittua Pakostrategiaa ja selvittää, ehtivätkö vangit kuolla vanhuuteen ennen vapautumistaan…

Toivoo
Valhe Kouneli