optimointi

0

Oi aitoja, oi latoja!

|

Matemaattisesti suuntautuneella maanviljelijä H:lla on ongelma. Hänellä on iso pelto ja sen keskellä neliöpohjainen lato. Hän haluaa rakentaa ladon luo suorakulmion muotoisen aitauksen, joka rajaa mahdollisimman suuren alan. H:lla on kaksi vaihtoehtoa:

  1. H. voi rakentaa sellaisen aitauksen, jossa ladon yksi seinä on osa suorakulmion sivua. Sivua voi kuten kuvassa jatkaa ladon seinästä molempiin suuntiin.
  2. H. voi rakentaa aitauksen, jossa yksi sivu kulkee ladon kahden nurkan kautta ladon pohjan lävistäjän suuntaisesti. Myös tässä diagonaalin suuntainen sivu voi olla vaikka kuinka paljon pidempi kuin itse diagonaali. Osa ladosta jää nyt aitauksen sisälle ja näin pienentää kokonaisalaa.

H:lla on aitatarpeita A metriä ja ladon seinän pituus on a metriä. Minkälainen suhde H:n kannattaa valita aitauksen pituudelle ja leveydelle? Kumpaa rakennusvaihtoehtoa H:n kannattaa käyttää? Riippuuko se aitatarpeiden määrästä A? Yksinkertaisuuden vuoksi1 rajataan tilanne niin, että A>3\sqrt{2}a.

Kuva: Neal Wellons/Flickr (CC BY-NC-ND 2.0)

Kuva: Neal Wellons/Flickr (CC BY-NC-ND 2.0)

0

Hyvät, pahat ja rumat

|

Sergio Leonen lännenelokuvan Hyvät, pahat ja rumat (1966) loppukohtauksessa Clint Eastwood, Lee Van Cleef ja Eli Wallach käyvät kuuluisan kolmintaistelun hautausmaalla, jonka asetelma on myös matemaattisesti kiintoisa: tällaisessa tilanteessahan nopein vetäjä ei automaattisesti olekaan vahvimmilla. Tarvitaan jonkinlaista optimointistrategiaa, jota voidaan mallintaa todennäköisyyslaskennan keinoin.

Kuva: Jacques Meynier de Malviala / Flickr (CC BY-NC-ND 2.0)

Kuva: Jacques Meynier de Malviala / Flickr (CC BY-NC-ND 2.0)

Leonen elokuvassa käsikirjoitus tietysti sanelee lopputuloksen, mutta kokeillaanpa kolmintaistelua tiukemmilla säännöillä. Arvotaan ensin ampumisjärjestys ja noudatetaan sitä loppuun asti. Ammutaan vuorojärjestyksessä yksi kuti kerrallaan minne tahansa, kunnes pystyssä on enää yksi mies. Oletetaan, että Clint osuu kohteeseensa aina, Lee 80 prosentin varmuudella ja Eli 50 prosentin varmuudella. Oletetaan vielä, että kaikki noudattavat parasta strategiaa, ja että kehenkään ei osu vahinkokimmokkeita. Kuka kolmikosta on todennäköisin taistelun voittaja? Mitkä ovat kunkin miehen täsmälliset selviytymismahdollisuudet?

Ongelman löysin jälleen Martin Gardnerin kautta; hän kertoo, että se on esiintynyt useissa lähteissä ainakin 1930-luvun lopulta alkaen.

Ratkaisu: Todennäköisin ammuskelun henkiinjäänyt on Eli. Hänelle paras strategia on ammuskella ilmaan siihen asti, kunnes jäljellä on vain toinen vastapelureista, sillä he tähtäävät varmasti toisiaan niin kauan kuin heissä henki pihisee, ja hyökätä sitten henkiinjääneen kimppuun. Mutta käydään nyt kunkin pyssysankarin mahdollisuudet läpi.

Clintin henkiinjäämisprosentti on helppo selvittää. Jos hän aloittaa Leetä vastaan, hän ampuu tämän. Jos taas Lee aloittaa, on Clintillä 20 prosentin mahdollisuus selvitä. Koska nämä tapaukset ovat erilliset ja yhtä todennäköiset, on Clintin selviämismahdollisuus Leetä vastaan \frac{1}{2}+\frac{1}{2}\cdot\frac{1}{5}=\frac{3}{5}. Koska tämän jälkeen Clint selviää 50 prosentin todennäköisyydellä Elin laukauksesta, joten kaikkiaan Clintin eloonjäämistodennäköisyys on \frac{3}{5}\cdot\frac{1}{2}=\frac{3}{10}=30\%.

Lee selviytyy voittajana Clintiä vastaan todennäköisyydellä \frac{2}{5}. Tämän jälkeen hän ajautuu kaksintaisteluun Elin kanssa. Jos hän selviytyy Elin ensimmäisestä laukauksesta, voittaa hän 80 prosentin todennäköisyydellä. Tämän jälkeen hän voi voittaa toisella laukauksellaan, ellei Eli osu, ja edelleen kolmannella, neljännellä, viidennellä laukauksella, kunnes ratkaisu tulee. Ensimmäisen laukauksen voiton todennäköisyys on \frac{1}{2}\cdot\frac{4}{5}=\frac{4}{10}, toisen laukauksen \frac{1}{2}\cdot\frac{1}{5}\cdot\frac{1}{2}\cdot\frac{4}{5}=\frac{4}{100} ja niin edelleen. Kaikkiaan Leen voittomahdollisuudet mittelössä Elin kanssa muodostavat geometrisen summan

    \[\frac{4}{10}+\frac{4}{100}+\frac{4}{1000}+\frac{4}{10000}+\cdots\]

Tämä taas voidaan ilmoittaa päättymättömänä desimaalikehitelmänä 0,44444\ldots=\frac{4}{9}. Lee siis voittaa Elin todennäköisyydellä \frac{4}{9}, joka yhdistettynä voittotodennäköisyyteen Clintiä vastaan antaa Leen kokonaistodennäköisyydeksi selvitä \frac{2}{5}\cdot\frac{4}{9}=\frac{8}{45}\approx 17,8\%.

Elin voittotodennäköisyys on nyt 1-\frac{3}{10}-\frac{8}{45}=\frac{47}{90}\approx 52,2\% ja siis selvästi paras kolmesta.

Jos Eli ei paukuttelisikaan ilmaan, vaan tähtäisi vaarallisimpaan vastustajaansa vuorollaan alusta asti, hänen selviämismahdollisuutensa olisi noin 44,7\%. Tällöin Leen mahdollisuudet nousisivat 31,1 prosenttiin ja Clintin mahdollisuudet olisivat vain noin 24,2\%.

2

Lentävän hollantilaisen aarre

|
image

Johann Gehrts (1887): Lentävä hollantilainen/Wikimedia Commons (Public Domain)

Tämänkertainen viikon vaikea vie meidät merta edemmäs, tarkkaan ottaen Itämerta edemmäs, sillä pulma löytyi hollantilaiselta The Ultimate Puzzle Site -sivustolta.

Lentävä hollantilainen haaksirikkoutui, ja viiden merirosvon kopla on saanut haltuunsa 1000 kultarahan aarteen. Nämä eivät olekaan mitään aivan tavanomaisia piraatteja, vaan heillä kaikilla on kolme yhtenevää piirrettä:

  1. He ovat ahneita. He haluavat niin paljon rahaa kuin vain ikinä saavat.
  2. He ovat verenhimoisia. He vaikka tappavat toverinsa, jos hyötyvät siitä.
  3. He ovat täydellisen loogisia optimoijia. He tekevät aina itselleen tuottoisimmat päätökset.

Nyt merirosvojen pitäisi siis jakaa 1000 rahan aarre. He menettelevät seuraavasti. Merirosvot on järjestetty tiukkaan arvojärjestykseen ensimmäisestä viidenteen ja jokaisella merirosvolla on vuorollaan yksi mahdollisuus ehdottaa omasta mielestään sopivaa rahanjakoa. Jos enemmistö merirosvoista hyväksyy jaon, rahat jaetaan esityksen mukaan. Jos taas ehdotus ei saa enemmistöä taakseen, heitetään ehdottaja armotta yli laidan haita kuhisevaan mereen.

Mitä ensimmäinen merirosvo ehdottaa?

0

Viiniä kuninkaan juhliin

|

Kuninkaalla oli suuret syntymäpäiväjuhlat tulossa. Hän oli varannut juhlia varten 1000 tynnyrillistä viiniä kellariinsa. Mutta viikkoa ennen juhlia alkoi hovissa levitä huhu, että yksi tynnyreistä olisi myrkytetty. Myrkky oli niin voimakasta, että pisarakin viiniä saastuneesta tynnyristä riittäisi kasvattamaan viisimetriset sierainkarvat kaikille tynnyristä siemailleille. Pahinta oli, että vaikka myrkyn vaikutus sitä juoneelle oli sataprosenttisen varma, myrkytyksen itämisaika oli jotain yhdestä vuorokaudesta kuuteen vuorokautta, eikä ennen sierainkarvojen äkillistä kasvua voinut mitenkään päätellä, oliko nauttinut myrkytettyä viiniä vai ei. Kuningas päättää testata viinikellarinsa ministereillään. Mikä on vähin määrä ministereitä, joka kuninkaan on uhrattava, jotta hän varmasti saisi selville, mikä tynnyreistä on myrkytetty?

Kuvaskannaus: JPS68/Wikimedia Commons (Public domain)

Ongelman ratkaisu löytyy täältä.

0

Rahojen punnitus

|

Kahdestatoista samannäköisestä rahasta yksi on väärennetty. Se on joko hieman liian kevyt tai liian painava. Käytettävissä on tasapainovaaka. Mikä on vähin määrä punnituksia, jolla voit varmasti selvittää, mikä rahoista on väärä ja onko se liian kevyt vai liian painava?

Tämäntyyppiset punnitusongelmat ovat hyvin klassista ongelmamatematiikkaa. Kiitoksia pulmasta Johannes Jermakalle Australiaan! Ongelman ratkaisu on tässä.

Kuva: Michael Coughlan/Flickr (CC BY-SA)

Kuva: Michael Coghlan/Flickr (CC BY-SA)