Hyvä Will Huntingin toinen matematiikkatehtävä

Elokuva Good Will Hunting kertoi salaperäisestä matematiikkanerosta, jota näytteli Matt Damon. Juoni keskittyy päähenkilö Williin, joka ratkaisee erittäin vaikean matemaattisen tehtävän, joka askarrutti MIT:n matematiikan professoreita kahden vuoden ajan. Tehtävä ei ollut ainoastaan itse asiassa melko helppo, vaan elokuvan hahmo silti ratkaisi sen väärin.

Liitutaululle kirjoitettu tehtävä oli "Piirrä kaikki homeomorfisesti pelkistymättömät puut, joiden koko on n = 10."

Yritänpä selittää tämän selkeästi ja yksinkertaisesti. Siinä kysytään kaikkia mahdollisia kaavioita, jotka koostuvat kymmenestä viivoilla yhdistetystä pisteestä, joissa mistään viivasta ei voi lähteä täsmälleen kaksi viivaa (muuten se olisi pelkistyvä) eikä suljetuista silmukoista voi syntyä (muuten se ei olisi puu). ”Homeomorfisesti pelkistymätön” tarkoittaa, että viivojen kulmilla ei ole väliä, vaan sillä, kuinka monta viivaa lähtee kustakin pisteestä.

Elokuvassa Will tuottaa vain kahdeksan kymmenestä puusta. Anna kun näytän teille tavan selvittää vastaus systemaattisesti. Teen sen ajattelemalla puita sukupuina, alkaen suvun päästä.

Ratkaisu 1 – Yhdeksän lasta. Tämä on ainoa ratkaisu, jossa on vain kaksi sukupolvea.

Ratkaisu 2 – Kolme lasta ja lastenlapsia erotettuna 6/0/0

Huomaa, että lapsia ei voi olla täsmälleen kaksi, koska silloin voisit siirtyä yhdestä lapsesta vanhempaan ja sitten toiseen lapseen, mikä olisi pelkistettävää.

Ratkaisu 3 – Kolme lasta ja lastenlapsia erotettuina 4/2/0

Huomaa, että kenelläkään ei voi olla yhtä lasta, muuten puu olisi pelkistettävä.

Ratkaisu 4 – Kolme lasta ja lastenlapsia erotettuina 3.3.2000

Ratkaisu 5 – Kolme lasta ja lastenlapsia erotettuna 2/2/2

Ratkaisu 6 – Neljä lasta ja lastenlapsia erotettuina 5/0/0/0

Ratkaisu 7 – Neljä lasta ja lastenlapsia erotettuina 2.3.2000.

<

Muista, että lapset eivät voi saada yhtä lasta, ettei puu olisi lyhennettävä.

Ratkaisu 8 – Viisi lasta ja lastenlapsia jakautuvat 4/0/0/0

Voit ajatella viiden lapsen ja lastenlasten jakoa ratkaisulla 2/2/0/0, mutta tämä olisi homeomorfisesti pelkistettävä samaan puuhun kuin ratkaisu 3 (tämän ymmärtäminen vei minulta hetken).

Ratkaisu 9 – Kolme lastenlasta, ja lastenlapset ovat jaettuina 2/0/0. Toisella kahdesta lapsenlapsesta on neljä lapsenlapsenlasta.

Ratkaisu 10 -- Kolme lastenlasta, ja lastenlapset ovat jaettuina 2/2/0. Toisella kahdesta lapsenlapsesta on kaksi lapsenlapsenlasta.

Tajuan käyttäväni jonkinlaista käsienheiluttelulogiikkaa saadakseni kaikki kymmenen ratkaisua. Ainakin sain ne kaikki tehtyä, toisin kuin Will elokuvassa.

Ensi viikolla aion käsitellä toista elokuvaa, jossa matemaattinen kohtaus oli tehty hyvin – Mean Girls.

Aiheeseen liittyviä linkkejä:

Ongelma Good Will Huntingissa – YouTube-video Numberfileltä

Ratkaisu osoitteessa MathProblems.info