binääriluvut

2

Ajatustenlukutemppu

|

Valmistele neljä lappua tai korttia tai taulua, joihin kirjoitat seuraavat luvut:

  1. 1, 3, 5, 7, 9, 11, 13, 15
  2. 2, 3, 6, 7, 10, 11, 14, 15
  3. 4, 5, 6, 7, 12, 13, 14, 15
  4. 8, 9, 10, 11, 12, 13, 14, 15

Tämän jälkeen käske temppusi uhrin ajatella jotain kokonaislukua väliltä 1-15. Sitten kysyt, mistä kaikista lapuista hänen lukunsa löytyy. Tämän jälkeen pamautat välittömästi hänen ajattelemansa luvun. Saat luvun helposti laskemalla yhteen ensimmäisen luvun jokaisesta lapusta, jonka toverisi mainitsee. Jos siis vaikka hän olisi ajatellut lukua 13, hän olisi sanonut, että luku löytyy tauluista 1, 3 ja 4, jonka jälkeen laskisit vain 1+4+8=13.

Temppu on hämmästyttävän hauska ja helppo. Se tuli vastaan Rob Eastawayn ja Jeremy Wyndhamin kirjassa Why do Buses Come in Threes? Viikon helppo kysymys on tietenkin se, miksi temppu toimii.

Ratkaisu: Kuten Mikko kommentoikin, ovat tempun taustalla lukujen 1-15 nelibittiset binääriesitykset. Esimerkiksi 13=1101_2, eli se saadaan laskemalla 1\cdot 2^3+1\cdot 2^2+ 0\cdot 2^1+1. Jokainen luku, jossa viimeinen bitti on ykkönen, on lapussa 1. Vastaavasti toiseksi viimeistä ykköstä tarvitsevat luvut ovat lapussa 2, toisen bitin ykköset lapussa 3 ja ensimmäisen bitin ykköset lapussa 4.

Temppu on kuten sanottua erittäin helppo, mutta aion käyttää sitä jatkossa opettaessani binäärilukujen käyttöä. Erittäin hyvää oppituntimateriaalia!

2

Uusi vuosi

|
Kuva: Maria Morri/Flickr (CC BY-SA 2.0)

Kuva: Maria Morri/Flickr (CC BY-SA 2.0)

Vuoden 2016 alku tarkoitti binäärilukuna hauskannäköistä siirtymää vuodesta 11111011111 vuoteen 11111100000.

On myös olemassa tapoja esittää luku 2016 vain yhtä numeroa ja joitakin laskutoimitussymboleja käyttäen. Koska 2016=2^5\cdot 3^2\cdot 7, on se jaollinen muiden muassa luvuilla 2, 3, 6, 7 ja 9, joten se voidaan totta kai kirjoittaa tylsästi esimerkiksi 3+3+3+\cdots riittävän monta kertaa. Tämän viikon vaikeana kysytään kuitenkin hieman kiehtovampaa tapaa esittää luku 2016.

Pystytkö esittämään luvun 2016, jos käytettävissäsi on vain yksi numero korkeintaan viisi kertaa sekä mitä tahansa laskutoimitussymboleja? Tai pystytkö keksimään jonkin muun kuin pelkkään yhteenlaskuun perustuvan tavan hyödyntää yhtä yksinumeroista lukua?

 

Ratkaisu: Uusi vuosi on aina numeronikkareille uusi hauska haaste. Kuinka ollakaan, suosikkimatemaatikkoihini kuuluva Alex Bellos kysyi vuoden 2016 rakentelemista The Guardianin palstallaan. Sieltä löytyi esittämääni ongelmaan vaihtoehtoinen ratkaisu, jota en ollut itse ajatellut. Nimittäin Bellosin ratkaisu on 2016=(4+4)\cdot(4^4-4).

Itseäni silti naurattaa vielä enemmän alkuperäinen löytöni uudenvuodenyöltä Twitteristä. Pelleilläänpä vähän binomikertoimilla. Nyt huomataan, että \binom{64}{2}=2016. Edelleen 2^6=64 ja \binom{4}{2}=6 ja vielä 2^2=4. Pysyttekö mukana? Tästä saadaan riemukkaasti, että

    \[2016=\binom{2^{\binom{2^2}{2}}}{2}.\]

Alex Bellos kysyi myös sitä, kuinka vuosi 2016 voitaisiin esittää lukujen 10, 9, 8, 7, 6, 5, 4, 3, 2 ja 1 avulla. Hän sai valtavasti vastauksia, joista hillittömin oli Sebastian Radun vastaus:

    \[2016=[(10\sqrt{9}\cdot 8! / 7) \quad (\mbox{modulo }6^5)] + 4!\cdot 3!\cdot 2! + \arccos 1.\]

Hyvää uutta vuotta 2016 toivoo Opettaja H:n pulmakulman henkilökunta.

1

Viiniä kuninkaan juhliin – ratkaisu

|

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. – – 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?

Kuten aiemmassa ongelmassa mainittiin, on binääriluvuilla lukuisia sovelluksia. Myös tämä ongelma ratkeaa lukujen muuttamisella binäärijärjestelmään. Kertauksen vuoksi: luvun binääriesityksellä tarkoitetaan luvun esittämistä kakkosen potenssien avulla. Näin siis esimerkiksi 13=1\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0=1101_2. Koska 2^9=512 ja 2^{10}=1024, ongelma voidaan ratkaista vähimmillään kymmenen ministerin avustuksella.

Liitetään jokaiseen tynnyriin yksilöllinen 10-bittinen binääriluku; lisätään tarvittaessa luvun eteen nollia. Esimerkiksi 6. tynnyri olisi 0000000110 ja 789. tynnyri 1100010101. Tämän jälkeen järjestetään ministerit järjestykseen ensimmäisestä kymmenenteen. Tynnyrin binääriluvun bitti (1 tai 0) kertoo, pitääkö kunkin ministerin maistaa tynnyristä vai ei. Tässä esimerkiksi ensimmäinen ja toinen ministeri eivät maistaisi 6. tynnyristä, mutta maistaisivat 789. tynnyristä. Kolmannen ministerin ei tarvitsisi maistaa kummastakaan, kun taas esimerkiksi tynnyristä numero 245 (eli binäärisenä 0011110101) hän maistaisi, kuten myös neljäs, viides, kuudes, kahdeksas ja kymmenes ministeri.

0

Venäläisen talonpojan kertolasku – ratkaisu

|

Otetaan esimerkiksi vaikkapa tulo 117\cdot 324. Homma toimii seuraavasti: jaetaan toista luvuista toistuvasti kakkosella. Jakojäännöksestä ei tarvitse välittää, vain kokonaiset lasketaan. Näin edetään, kunnes ollaan päästy ykköseen. Viereiseen sarakkeeseen aletaan puolestaan kertoa toista luvuista toistuvasti kakkosella. Kun ollaan päästy yhtä pitkälle kuin vasemmalla, vedetään yli kaikki ne luvut, jotka vastaavat parillista lukua vasemmanpuoleisessa sarakkeessa. Jäljelle jäävät luvut lasketaan yhteen, ja halutun tulon arvo on saatu. Kysymys kuuluu, miksi tämä menetelmä toimii mille tahansa kokonaislukujen tulolle.

Venäläisen talonpojan kertolaskun taustalla on lukujen binääriesitys. Binäärijärjestelmä toimii aivan kuten meille tuttu kymmenjärjestelmäkin, mutta kymmenen sijaan kantalukuna on luku 2. Kun siis esimerkiksi

    \[17034=1\cdot 10^4+7\cdot 10^3+0\cdot 10^2+3\cdot 10^1+4\cdot 10^0,\]

on binääriesityksessä käytettävissä vain numerot 0 ja 1. Siis vaikkapa 23 on binäärilukuna 10111, koska

    \[23=16+4+2+1=1\cdot 2^4 + 0\cdot 2^3+1\cdot 2^2+1\cdot2^1+1\cdot 2^0.\]

Näyttökuva 2015-8-29 kello 20.37.00

Miten tämä sitten liittyy venäläisen talonpojan kertolaskuun? Ideana on muodostaa toisen tulontekijän binääriesitys ja kertoa sillä tulon toista tekijää. Binääriesityksen muodostaminen luvulle on helppoa. Jaetaan luku ensin toistuvasti kakkosella, kunnes jäljellä on vain ykkönen. Luetaan binääriesitys alhaalta ylöspäin. Jos jaon tulos on ollut pariton (eli jakojäännös on jäänyt), on tarvittava bitti 1, jos taas jako on parillinen, bitiksi valitaan 0. Näin voidaan selvästi toimia riippumatta siitä, mikä kokonaisluku on kyseessä.

Näin toimien huomaame luvun 117 binääriesityksen olevan 1110101, sillä 

    \[117=1\cdot 2^6+1\cdot 2^5+1\cdot 2^4+0\cdot 2^3+1\cdot 2^2+0\cdot 2^1+1\cdot 2^0.\]

Nyt laskemamme laskutoimitus onkin periaatteessa 324\cdot (2^0+2^2+2^4+2^5+2^6) eli

    \[324+324\cdot 4+324\cdot 16+ 324\cdot 32+324\cdot 64,\]

joka tietenkin on oikeanpuoleisten yliviivaamattomien lukujen summa. Hauskaa ja melko helppoa, eikö?

Binääriluvuilla on lukematon määrä sovelluksia. Jos mainitsen niistä yhden, voi kukin päätellä niitä jokusen lisää. Nimittäin kaikki maailman tietokoneet perustuvat binäärijärjestelmään.