algoritmit

0

Pennirinki

|

Seuraava pulma on Charles Lutwidge Dodgsonin alias Lewis Carrollin kirjasta Pillow-Problems vuodelta 1895. Kirjassa on 72 ongelmaa, jotka Dodgson kertoo kehitelleensä ja ratkoneensa päässänsä unettomina öinä. Kirjan ongelmien vaikeustaso vaihtelee hurjasta helpohkoihin, ehkäpä yläpäätä painottaen. Tämä ongelma on sieltä kevyemmästä päästä.

Viisi roistoa istuu ringissä ja jokaisella miehellä on yhtä monta penniä. Älykkäin heistä ehdottaa pientä pennipeliä. Ensinnäkin kaikki saavat numeron, älykkäin ykkösen, seuraava kakkosen, sitten kolmonen, nelonen ja vielä vitonen. Nyt älykkäin laittaa kaikki penninsä pussiin, antaa sen kolmoselle, jonka pitää ensin ottaa kummallekin naapurilleen pussista naapurin numeron osoittama määrä pennejä. Sitten kolmosen pitää laittaa pussiin puolet siitä määrästä pennejä, joka pussissa oli sen saapuessa hänelle. Sitten kolmonen antaa pussin vitoselle, joka antaa myös pussista pennit vierustovereille, lisää puolet siitä summasta, joka pussissa oli sen tullessa hänelle, ja antaa pussin kaksi paikkaa eteenpäin. Jos sattuisi käymään niin, että rahanlisäysvaiheessa itsellä ei olisi tarpeeksi rahaa pussin täydentämiseen, saisi kenen tahansa muun paitsi numero ykkösen pennipinosta täydentää puuttuvan määrän.

Kun pussi tulee takaisin ykköselle, hän nakkaa kaksi saamaansa rahaa pussiin, vetää pussin nyörit kiinni ja pakenee vauhdilla paikalta. Muut neljä roistoa jäävät hölmistyineinä katsomaan tyhjin käsin – ryökäle nappasi kaikki rahat! Kuinka monta penniä kullakin roistolla oli aluksi?

Ratkaisu: Olkoon kullakin konnalla aluksi k kolikkoa. Peli etenee seuraavasti:

  1. Numero 3 sai pussin jossa on k kolikkoa ja hän antoi pois 2+4=6 kolikkoa. Sitten hän laittaa pussiin \frac{k}{2} kolikkoa, joten pussiin jää k+\frac{k}{2}-6=\frac{3}{2}k-6 kolikkoa.
  2. Numero 5 jakaa pois 4+1=5 kolikkoa ja puolitoistakertaistaa pussissa olleen rahasumman. Loppusumma hänen vuoronsa jälkeen on siis \frac{3}{2}\left(\frac{3}{2}k-6\right)-5.
  3. Numero 2 jakaa pois 1+3=4 kolikkoa ja puolitoistakertaistaa pussin summan. Pussin rahamäärä on hänen jälkeensä \frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4.
  4. Numero 4 jakaa pois 3+5=8 kolikkoa ja puolitoistakertaistaa pussin summan. Pussin rahamäärä on hänen jälkeensä \frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4\right)-8.
  5. Numero 1 lisää pussiin kaksi kolikkoa, jonka jälkeen pussissa on 5k kolikkoa.

Tästä saadaan yhtälö 

    \[\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}\left(\frac{3}{2}k-6\right)-5\right)-4\right)-8+2=5k,\]

jonka ratkaisu on k=696.

Sivumennen sanoen: olisi ehkä jäänyt ratkaisematta ilman kynän ja paperin apua. Eli onnea vain Lewis Carrollille, jos päässään yöllä tämän pyöritteli loppuun asti.

5

Pyörivä pöytä ja helisevä tiuku

|

Pöydän pyörittely on matemaattisessa mielessä sangen kiehtovaa, oli sitten kyseessä epätasainen keittiön lattia tai väärässä järjestyksessä istuvat ritarit. Myös tässä ongelmassa tarvitsee pyöritellä pöytää.

Neliön muotoisen pöydän jokaisessa nurkassa on kolo, johon on asetettu juomalasi joko ylösalaisin tai oikein päin. Omituisella mekaniikalla laseihin on kytketty pieni tiuku, joka helähtää, mikäli kaikki lasit ovat samoin päin. Koloihin ei näe, mutta niihin pystyy työntämään käden niin, että tunnustelemalla selviää, kuinka päin lasi on. Lisäksi lasin pystyy kääntämään. Pöytää voidaan pyörittää keskipisteensä ympäri niin, että kun pyöriminen loppuu, ei mitenkään voida paljaalla silmällä päätellä, mikä koloista on mikäkin. Omituinen häkkyrä siis.

Pelataan seuraavanlaisin säännöin: pyöräytetään pöytää, jonka jälkeen työnnetään kädet yhtä aikaa mihin tahansa kahteen eri koloon. Koloissa voi tunnustella laseja ja sen jälkeen kääntää joko molemmat lasit tai vain toisen. Kumpaakaan lasia ei ole pakko kääntää. Tarkasteltavat kolot on kuitenkin valittava samanaikaisesti ja ennen kuin menee räpeltämään mitään. Tavoite on saada tiuku helisemään. Alkutilanne on muuten sattumanvarainen, mutta voidaan olettaa, että kaikki lasit eivät ole samoin päin (sillä silloinhan tiuku helisisi jo).

Mikä on pienin määrä pyöräytyksiä, jonka jälkeen tiu’un saa varmasti helisemään? Miten se tehdään?

Myös tämä pulma on Martin Gardnerilta. Poimin sen mainiosta teoksesta The Colossal Book of Short Puzzles and Problems (W.W. Norton & Co, 2006). Pulman esitettyään Gardner jatkaa, että jos pöydässä olisi vain kaksi koloa, olisi ratkaisu tietenkin triviaali: kädet koloihin ja lasit samoin päin. Myöskään kolmikoloinen pöytä ei ole kovin vaikea ratkaistava. Jos ensimmäisellä yrityksellä molemmat lasit ovat samoin päin, käännetään ne toisin päin ja johan helisee. Jos taas ne ovat eri päin, käännetään ne molemmat esimerkiksi alassuin, jonka jälkeen toisella yrityksellä helinä on varma. Edelleen Gardner toteaa, että voidaan osoittaa, ettei viisikoloista pöytää pysty ratkaisemaan – ainakaan alle kolmekätisenä pyörittäjänä.

Ratkaisu: Viisi pyöräytystä riittää aina. Toimitaan näin:

  1. Otetaan vastakkaisissa koloissa olevat lasit ja käännetään ne molemmat ylöspäin. Jos tiuku ei nyt helise, jatketaan pyörittämistä.
  2. Otetaan vierekkäiset lasit ja käännetään ne ylöspäin, elleivät ne jo ole. Jos tiuku ei vieläkään helise, nyt tiedetään, että kolme laseista on ylöspäin ja yksi alaspäin. Pyöritetään pöytää uudestaan.
  3. Valitaan jälleen vastakkaiset kolot. Jos toinen laseista on alaspäin, käännetään se ja tiuku helisee. Jos taas molemmat ovat ylöspäin, käännetään toinen, jolloin välttämättä kaksi vierekkäistä lasia on ylöspäin ja kaksi vierekkäistä alaspäin. Pyöritetään edelleen.
  4. Valitaan kaksi vierekkäistä koloa. Jos lasit ovat samoin päin, käännetään molemmat ja tiuku helisee. Jos ne taas ovat eri päin, käännetään jälleen molemmat, jolloin varmasti kaksi vastakkaista lasia on ylöspäin ja toiset kaksi vastakkaista alaspäin. Pyöritetään.
  5. Valitaan vastakkaiset lasit ja käännetään ne molemmat toisin päin. Tiuku helisee.
0

Vedamatematiikkaa

|

Swāmī Bhāratī Kṛṣṇa Tīrtha (1884–1960) oli intialainen uskonoppinut ja matemaatikko, joka väitti kaiken matematiikan löytyvän muinaisista hindulaisista Veda-kirjoituksista johdetuista 16 suurasta ja 13 apusuurasta. Uskoo ken tahtoo (siis sen, mitä Swāmī Bhāratī Kṛṣṇa Tīrtha 1950-luvun lopulla kirjoittamassaan teoksessa väitti), mutta joka tapauksessa nämä yksinkertaiset säkeet antavat muutamia erittäin käyttökelpoisia – ja nopeita! – kikkoja päässälaskuun.

Keskitytään nyt toiseen suuraan, jonka nimi on Nikhilam Navatashcaramam Dashatah1. Se tarkoittaa suunnilleen, että ”kaikki yhdeksästä ja viimeinen kymmenestä”. Siinä kerrotaan kaksi lukuavedamatikka keskenään käyttäen apuna niiden etäisyyttä lähimmästä kymmenen potenssista. Kaksinumeroisilla luvuilla laskettaessa käytetään referenssilukuna sataa, kolminumeroisilla tuhatta ja niin edelleen. Otetaan esimerkiksi tulo 78\cdot 97. Kirjoitetaan luvut allekkain ja laitetaan niiden viereen toiseen sarakkeeseen niiden etäisyydet luvusta 100. Nyt tulon kaksi viimeistä numeroa saadaan kertomalla oikeanpuoleisen sarakkeen luvut keskenään: -22\cdot (-3)=66. Jos tässä tulossa olisi enemmän kuin kaksi numeroa, menisivät sadat muistinumeroiksi alkuosuuteen, eli esimerkiksi jos oltaisiin saatu 840, olisivat viimeiset kaksi numeroa 40 ja 8 lisättäisiin tulon alkuosuuteen. Vastaavasti jos tässä tulossa olisi vähemmän kuin kaksi numeroa, lisättäisiin nollia eteen.

Toisessa vaiheessa voidaan edetä neljällä eri tavalla, jotka kaikki tuottavat saman tuloksen. Voidaan laskea saman diagonaalin luvut yhteen. Tai voidaan laskea yhteen vasemmanpuoleisen sarakkeen luvut ja vähentää 100. Tai edelleen voidaan laskea oikeanpuoleisen sarakkeen luvut yhteen ja lisätä 100. Kuinka tahansa toimitaankaan, tulos on aina sama: 78-3=97-22=78+97-100=-22-3+100=75. Tulon kaksi ensimmäistä numeroa ovat siis 75. Ja kaikkiaan 78\cdot 97=7566, kuten kuka tahansa voi tarkistaa.

Viikon helppona tehtävänä on osoittaa, miksi tämä menetelmä toimii aina kaksinumeroisille luvuille.

Entäpä jos tehtävänä olisikin laskea vaikkapa 103\cdot 87? Tai 514\cdot 522? Viikon vaikea pulma on miettiä, miten tätä samaa tekniikkaa voisi soveltaa myös näihin tuloihin.

Tämä temppu parin sukulaisensa kanssa tuli vastaan Alex Bellosin (ainakin ensimmäisen puoliskonsa perusteella aivan loistavassa) kirjassa Alex’s Adventures in Numberland (Bloomsbury, 2010).