Category Archives: Matematiikka

Match problem: infinite or not?

 

An intriguing matchstick problem has been running around on Facebook. (I haven’t managed to dig up the original originator). I suggest that the number of possible solutions is  in principle infinite. However, there is a reasonably good logical case to suggest that the maximum number of solutions is at least 9 and most 78. There are four classes of solutions, which have 3, 3-15, 3-15, and 0-45 solutions respectively.

Match

Spoiler alert: these solutions are shown below.

Continue reading Match problem: infinite or not?

Lewis Carroll’s fuzzy counters

This site is mostly in Finnish, but I would like to get wider feedback on one posting. I suspect that I am wrong, but have not been able to prove it so far. The Finnish version is here.

A local book publisher, Terra Cognita, publishes weekly classic puzzles.  Last week’s problem has stuck in my mind. It is the fifth puzzle in  Lewis Carroll’s Pillow Problems. It is framed in this way“A bag contains a counter, known to be either white or black. A white counter is put in, the bag is shaken, and a counter is drawn out, which proves to be white. What is now the chance of drawing a white counter?”

Continue reading Lewis Carroll’s fuzzy counters

Vastapähkinä: Lewis Carrollin sumea kuulatehtävä

Terra Cognita-kirjankustantamo kääntää ja julkaisee klassista tiedekirjallisuutta suomeksi. (Kaupallinen huomautus: En omista firman osakkeita, mutta omistan firman kääntämiä kirjoja, ja toivon että mahdollisimman moni muukin omistaisi).  Kustantamo julkaisee viikoittain klassisia matemaattisia pähkinöitä.

Viime viikon pähkinä jäi kuitenkin vaivaamaan. Kyseessä on Lewis Carrollin Pillow-Problems –ongelmakirjan viides ongelma. Terra Cognita muotoilee sen näin:

Pussissa on yksi marmorikuula, joka voi olla joko musta tai valkoinen. Pussiin lisätään valkoinen marmorikuula, pussia sekoitetaan ja pussista nostetaan sokkona yksi kuula, joka osoittautuu valkoiseksi. Mikä on todennäköisyys, että pussiin jäänyt kuula on valkoinen?

Continue reading Vastapähkinä: Lewis Carrollin sumea kuulatehtävä

Perimisen dynamiikkaa I

Rakensin hyvin yksinkertaisen simulaation perimisestä. Tarkoituksena tutustua järjestelmän dynamiikkaan. Systeemi on niin yksinkertainen ettei sitä voi pitää kovin luotettavana kuvauksena todellisuudesta, mutta ehkä jotain päätelmiä voidaan tehdä tai ainakin se näyttää miten ajattelen systeemin toimivan.

Oletuksena on perintöjen kertymisen haitallisuus kokonaisuuden kannalta ja parametrit on kuvaan 4 valittu siten että kertyminen näkyy. Motivaationa on tutkia millaisin parametrein varallisuus kertyy ja miten perintöverolla tähän voitaisiin vaikuttaa. Tämän ymmärtäminen on tärkeää, koska raha on valtaa ja harvoille kertyvä varallisuus johtaa epäreiluun yhteiskuntaan.

Simulaatiossa on pyritty huomioimaan varallisuuden periytyminen, kasautumisen riippuminen aiemmasta varallisuudesta sekä onnen vaikutus kertymään. Silloin kun vauraus johtaa köyhempiä parempaan kykyyn kerätä lisää vaurautta on systeemissä positiivinen takaisinkytkentä ja rikkaat rikastuvat kunnes kaikki varallisuus on kertynyt harvoihin tai jopa yksiin käsiin.

Periytyminen näkyy siten, että seuraava sukupolvi kerryttää varallisuutta aina aiemman päälle. Onni näkyy jokaisen sukupolveen kohdistuvana “onni”-kertoimena joka voi esimerkkinä käytetyssä jakaumassa vaihdella nollasta (koko omaisuus menetetään) johonkin 15 tienoille. Onni on yllä lainausmerkeissä, koska se voi tarkoittaa myös mitä tahansa piirrettä joka lisää kertyneen varallisuuden määrää, kuten esimerkiksi hyvää koulutusta tai kykyä verkostoitua.

Kuvassa 1 on selitetty lyhyesti simulaation kulku. Lähtötilanteessa kaikilla on sama varallisuus, lisää saa joko varallisuuden mukaan tai tuurilla. Varallisuutta voi myös menettää kahdella tavalla: joko huonolla tuurilla tai siten että muiden varallisuus on kasvanut suhteellisesti suuremmaksi. Simulaatio on kokonaan suhteellinen ja kokonaisvarallisuus aina kierroksen päätteeksi tasan yksi. Absoluuttiseen elintasoon ei siis oteta kantaa ollenkaan.

Johtuen varallisuuskertoimen (Kuva 2) voimakkaasti nousevasta luonteesta varallisuus pyrkii keskittymään kaikkein varakkaimmille. Toisin sanoen mitä enemmän varallisuutta, sitä enemmän sitä saa seuraavalla kierroksella. Mutta koska mallissa onni voi vaihtua sukupolvien välillä on rikkaidenkin mahdollista menettää varallisuutensa joko osittain tai kokonaan.

2014-12-29 simulaation kulku

Kuva 1. Simulaation kulku. 1) Ensin kaikille jaetaan sama varallisuus. 2) seuraavan sukupolven varallisuus määräytyy vanhan varallisuuden mukaan (kuva 2), mitä suurempi osuus potista sitä enemmän saa lisää. 3) Mukaan lisätään onnen vaikutus onni voi sekä lisätä että vähentää varallisuutta (Kuva 3). 4) Lähimpien kavereiden varallisuutta lisätään. 5) Lopputuloksena uusi varallisuus jonka jälkeen kierros alkaa uudestaan. 6) kun kierros on kierretty tarpeeksi monta kertaa simulaatio loppuu.

Continue reading Perimisen dynamiikkaa I

Kuntakierros

Luultavasti olen jostain kohtaa ajanut läpi tai lentänyt yli jokaisen Varsinais-Suomen kunnan, mutta paremman kuvan saisi kun kävisi kurkkaamassa miltä kylillä näyttää.

Varsinais-Suomessa on tällä hetkellä vielä 28 kuntaa, joten matkaa tulee vähintään melko paljon. Kuntien väliset etäisyydet vaihtelevat, mutta jos arvaa keskimääräiseksi välimatkaksi 30 km niin matkaa olisi noin 900 km. Matka olisi ajettavissa yhdessä päivässä jos oikein yrittää.

Todellinen matka kuitenkin riippuu siitä missä järjestyksessä kunnat kiertää. Mahdollisimman lyhyen reitin löytäminen on kuitenkin haastavaa koska mahdollisia reittejä on paljon.
Kyseessä on niin sanottu kauppamatkustajan ongelma, jonka matemaattista ratkaisua on pohdittu enemmänkin. Määränpäiden lukumäärän kasvaessa ongelma muodostuu nopeasti työlääksi ratkaista jopa tietokoneella.

Asiaa pohtiessani pieni nörtti sisälläni heräsi ja päätin kokeilla yksinkertaista algoritmiä. Kirjoitin taulukkoon google mapsin antamia lyhimpiä etäisyyksiä kuntien välillä ja laitoin koneen valitsemaan arvalla seuraavan kohteen. Annoin koneen laskea jonkin aikaa, Kuva 1 näyttää minkä pituisia matkoja löytyi.

Lyhin matka oli 809 km ja pisin 1619 km. Vieläkin pidempiä matkoja olisi varmasti tullut, mutta en jaksanut kirjoittaa taulukkoon kaikkia mahdollisia reittejä. Ajan säästämiseksi laitoin vain etäisyyden muutamaan lähimpään kuntaan.

HistogrammiKuva 1. Noin 600 000 yritystä joista 81786 johti takaisin kotiin. Ryhmästä “Uniikit” on poistettu useampaan kertaan esiintyneet matkan pituudet

Taulukko 1.
Min.  1st Qu.  Median  Mean  3rd Qu.  Max.   Ryhmä
809   1143      1207        1206    1270       1619  Kaikki
809   1119      1215        1211    1304       1619  Uniikit

Koska varsinkin kaikista piirretty histogrammi näyttä kovasti normaalijakautuneelta niin plottasin vielä QQplotin normalli jakaumaa vasten (R-QQnorm). Lineaarinen transformaatio tarvitaan ennen kuin kaikkien jakauma on normaali. Pelkästään uniikit matkan pituudet hyväksyvä jakauma poikkeaa normaalista enemmän. En osaa muuta sanoa kuin että jotain tälläistä voisi odottaa kun kohtuu satunnaisia pituuksia arpoo monta peräkkäin ja laskee summan.

Matkat-QQnorm

Alla laskennassa käytetty R-koodi:

[code language=”css”]

## laske kauppamatkustajan ongelmaa kiertueelle

TSP.distance <- function(yri=10, method = "mininum", verbosity=3){
# method = miten valitaan seuraava paikka
# verbosity = miten paljon kerrotaan toiminnasta

load("kkk.Rdata")
kotiin=kkk[kkk$variable=="Piikkiö", c("X", "variable", "value")]
K=kkk
D.k=numeric()
m.k=list()
m=0
for (j in 1:yri){
kkk=K
D=0
vajaa=F
Uk="Piikkiö"
Kaikki.K=numeric()
Kaikki.K[1]=Uk
for (i in 1:28){
k=kkk[kkk$variable==Uk, "X"]
if (length(k)==0){
vajaa=T
break
}
k=sample(k, 1)
Uk2=as.character(kkk[kkk$variable==Uk &
kkk$X==k,"X"])[1]
D=D+kkk[kkk$variable==Uk & kkk$X==k,"value"][1]
kkk=kkk[!(kkk$X==Uk | kkk$variable==Uk),]
Uk=Uk2
Kaikki.K[i+1]=Uk
}
if (!vajaa){
print(j)
m=m+1
D=D+kotiin[kotiin$X==Uk, "value"]
Kaikki.K[i+2]="Piikkiö"
print(D)
D.k[[m]]=D
m.k[[m]]=Kaikki.K
}
}
Reissut=list(Pituudet=D.k, Kunnat=m.k )
}

TSP.Lyhin <- function(R){
P=10000
for (i in 1:length(R$Pituudet)){
if (R$Pituudet[[i]]<P){
P=R$Pituudet[[i]]
K=R$Kunnat[[i]]
}
}
list(P, K)
}

[/code]