Škótska tancovačka

Ako ste si iste všimli, 4 mesiace som na blog nič nenapísal. Sorry! Samozrejme, mám na to kokteil subjektívnych a objektívnych výhovoriek. Stačí ak spomeniem, že po období zmien, hektického cestovania a sťahovania na nové pôsobisko som opäť pocítil pevnú pôdu pod nohami, a môžem sa teda vrátiť k písaniu príspevkov.

Práve som doznámkoval svoj prídel úloh matematickej súťaže pre 11-12 ročných žiakov škótskych základných škôl. Jedna z celkového počtu piatich úloh ma celkom zaujala. Dúfam, že vás trošku pobaví!

Úloha #38: John, Willie, Andy a Greig pozvali svoje ženy na tancovačku. V jednom momente počas zábavy Flo tancovala s Willie-m, Hettie s manželom pani Beeb, Mary s manželom pani Hettie, Andy s Greigovou manželkou a Greig tancoval s Willie-ho ženou. Podarí sa vám identifikovať manželské páry?

Herónov vzorec

Obsah trojuholníka so stranami dĺžok a, b, c je možné vypočítať pomocou Herónovho vzorca:

, pričom .

Herónov vzorec možno dokázať jednoduchou stredoškolskou matematikou, dva stručné dôkazy nájdete na horeuvedenej Wiki adrese. Včera som pri uvažovaní nad jednou Radovou úlohou prišiel na jeden celkom milý dôkaz. Musím však poznamenať, že môj dôkaz má dve nevýhody: 1) platí iba pre trojuholníky s maximálnym uhlom nepresahujúcim 90 stupňov (hlavný problém) a 2) vyžaduje si narábanie s vektormi (menší problém). Nájdete ho aj Vy?

Úloha #37: Pomocou triku z úlohy# 36 dokážte platnosť Herónovho vzorca pre všetky netupouhlé trojuholníky.

Trojuholník na súradnicových osiach

Akúkoľvek úsečku AB je možné “vložiť” do roviny tak, že vrchol A leží na osi x a vrchol B na osi y. Tento triviálny fakt som použil na riešenie Radovej úlohy o Medoide trojice bodov. Dokážte, že platí nasledovné zovšeobecnenie* tohoto tvrdenia:

Úloha #36: Ľubovoľný netupouhlý** trojuholník ABC je možné “vložiť” do priestoru tak, že bod A leží na osi x, B na osi y a C na osi z.

Zdá sa, že toto tvrdenie môže byť užitočným trikom pri riešení rôznych úloh s trojuholníkmi. Úloha #37, ktorú onedlho zverejním (pozn.: už sa stalo), bude obsahovať jednu možnú aplikáciu ktorá mi prišla na um pri pokuse o riešenie zovšeobecnenia Radovej úlohy.

* Skutočne ide o zovšeobecnenie, pretože úsečka je konvexným obalom dvoch bodov a trojuholník konvexným obalom troch bodov.

**Ivansml si všimol, že pôvodné tvrdenie bolo chybné (nebolo obmedzené len na netupouhlé trojuholníky). Vďaka, Ivan!

Nepotrebná nerovnosť

Včera večer som pri skúmaní vlastností jednej skupiny množín vrámci mojej práce narazil na nasledovný problém. Potreboval som minimalizovať istú funkciu jednej premennej na intervale [0,1] — toto minimum mi totiž dáva hornú hranicu na hodnotu istého parametra ktorý ma veľmi zaujíma. Vypočítal som teda jej deriváciu a potreboval som ukázať, že je nekladná na danom intervale. Toto sa ukázalo byť ekvivalentné nasledovnému tvrdeniu.

Úloha #35: Dokážte, že pre každé platí nerovnosť .

Dnes ráno som si všimol, že som včera spravil vo výpočte hlúpu chybičku: zamenil som jedno plus za mínus. Úloha sa automaticky zmení na úplne inú, a teda riešenie horeuvedeného problému ma už nezaujíma. Naštastie odhad parametra ktorý som dostal po opravení chyby je kvalitnejší.

Som zvedavý koľko rôznych riešení sa vám podarí nájsť; ako zvyčajne, píšte ich do komentárov.

Biohádanka #1: Hluchý netopier

V poslednom čase sa čoraz viac zaujímam o biológiu. Je to zaujímavé, lebo ma v škole nikdy obvzlášť nebavila. Mal som ju ako každý na základke vo forme prírodovedy a dva roky na gympli;  k vysokoškolskej som sa nikdy nedopracoval. Keď sa na to spätne pozerám, veľký podiel na mojom nezáujme mal fakt, že nám bolo všetko podávané v hotovej forme. Takéto a takéto orgány má slimák, toto je stavba listu rastliny a pod. Ako je to už u nás zvykom, dôraz bol kladený na memorovanie. Môj novoobjavný “bio-talent” má korene v tom, že som sa akosi náhodou (a konečne!) dostal k zdroju/zdrojom, alebo k ľuďom (najmä Dawkins a referencie z jeho kníh), ktorí o živote/zvieratách/bunkách/génoch hovoria úplne inak. Dôraz nekladú na opis, ale na proces objavu. “Prečo je toto takto a nie inak? Ako sme na to prišli? Kedy a kto? Je to už konečná odpoveď?” Je to ako detektívka, lúštenie hádanky. A ja mám detektívky a hádanky rád. Napokon, preto sa aj venujem matematike.

Nebudem už ďalej filozofovať a prejdem rovno k podstate veci. V rubrike biohádanka budem pre vás vyberať otázky z oblasti biológie na ktoré existujú (alebo aj nie?) zaujímavé odpovede. Odpoveď si môžete vymyslieť a formulovať ako hypotézu — v takom prípade ju čo najlepšie ale stručne zargumentujte. Ak sa vám ju podarí niekde nájsť (kniha, internet, známy), uveďte zdroj. Nie všetky biohádanky budú mať 100% odpovede, veď v živote je oveľa viac záhad nevyriešených ako tých na ktoré už máme odpovede.

Tu je prvá biohádanka:

Biohádanka #1: Je známe, že netopiere sa v noci pohybujú vzduchom pomocou ultrazvuku. Deje sa to tak, že vydávajú veľmi intenzívne vysokofrekvenčné škreky, ktoré sa potom odrážajú od objektov. Odraz zvukových vĺn sa vráti do ucha netopiera a v mozgu sa analyzuje pomocou sofistikovaného zabudovaného “softwéru”. Škreky sú skutočne nesmierne intenzívne. Ako to, že netopier neohluchne?

Poznámka 4.5.2009: Táto rubrika je venovaná môjmu kamošovi Šimonovi Tóthovi, s ktorým sme sa na átriákoch nasmiali do popuku na jeho bio-pikoškách.

Nebezpečné poznanie

Čo majú spoločné Georg Cantor, Ludwig Boltzmann, Kurt Gödel a Alan Turing? Okrem toho, že všetci boli velikánmi vo svojom odbore, či už to bola matematika, fyzika, logika alebo teoretická informatika, každý z nich zahynul za tragických okolností.

Georg Ferdinand Ludwig Phillipp Cantor (1845–1918) bol nemeckým matematikom, zakladateľom teórie množín. Sprecíznil pojem nekonečna a vybudoval teóriu transfinitných čísel. Táto práca ho stála veľa psychických síl, bola nesmierne vyčerpávajúca a pomaly ale isto nahlodávala jeho mentálne zdravie a vieru v Boha. Cantor veril, že je božím poslom; svoje práce o nekonečne ponímal ako náhľad do absolútna. Od približne štyridsiateho roku života trpel chronickou depresiou, často sa liečil v psychiatrických inštitúciách a ako 72 ročný zomrel na infarkt v mentálnom sanatóriu.

Ludwig Eduard Boltzmann (1844–1906) bol rakúskym fyzikom, spoluzakladateľom štatistickej mechaniky a termodinamiky. Bol jedným z prvých advokátov atomickej teórie: jeho kinetická teória plynov predpokladala existenciu “atómov”. Väčšina rakúskych fyzikov a vedcov tej doby však ich existenciu popierali –  Bolzmann vydal nemalé psychické úsilie a mnoho času na obhajovanie svojich teórií. Je pravdepodobné, že trpel maniodepresívnou poruchou — mal časté depresie a viackrát sa pokúsil o sebevraždu. To sa mu napokon podarilo počas dovolenky v Duíne — obesením.

S národnosťou Kurta Gödela (1906–1978) je to komplikovanejšie. Narodil sa v Brne do etnicky nemeckej rodiny za Rakúska-uhorska, po jeho rozpade po 1. svetovej vojne sa stal občanom Československa, neskôr sa presťahoval do Rakúska a bol jeho občanom. Keď  fašistické Nemecko anexovalo Rakúsko, stal sa občanom Nemecka. Nuž a napokon po 2. svetovej vojne emigroval do USA a stal sa americkým občanom. Preslávil sa svojimi vetami o neúplnosti, v ktorých dal de-facto negatívnu odpoveď na druhý Hilbertov problém. Ako aj naši predošlí hrdinovia, v neskoršom veku trpel mentálnou nestabilitou a strachom z otrávenia, kvôli ktorému odmietal jesť. Extrémnou hladovkou, ktorou znížil svoju váhu až pod hranicu 30kg, spáchal fyziologickú samovraždu.

Alan Mathison Turing (1912–1954) bol britským matematikom, logikom a otcom informatiky. Formalizoval pojem algoritmu a počítača pomocou konceptu, ktorý sa neskôr stál známy pod názvom Turingov stroj. Pomohol zostrojiť jeden z prvých elektronických počítacích strojov. Bol homosexuál, čo bolo v tej dobe v Anglicku považované za mentálnu poruchu. Bol donútený k “chemickej kastrácii” injekciami estrogénu. Táto záležitosť ho podľa všetkého doviedla k samovražde — otrávil sa kyanidom. Okolnosti jeho smrti však zostávajú neisté.

V roku 2008 stanica BBC odvysielala dokumentárny cyklus s názvom Dangerous Knowledge (Nebezpečné poznanie) o priekopníckej práci a tragike života práve týchto štyroch osobností vedy. Tento 90 minútový film (v anglickom jazyku) mám v offline verzii už nejaký čas. Včera som zistil, že je momentálne sprístupnený na Google Video, a teda ho tu môžem na blogu nalinkovať:

Poznámka 2.5.2009: Môj predchádzajúci článok o Logicomixe sa týka tej istej témy — “šialenosti” hľadania základov matematiky.

Logicomix: komix o šialenstve hľadania základov matematiky

Christos Papadimitriou je profesorom teoretickej informatiky na Berkeley (University of California, Berkeley). Jeho kniha kombinatorická optimalizácia je klasikou. Okrem iného je Prof. Papadimitriou priekopníkom algoritmickej teórie hier*: nového odboru, ktorý spája teoretické a algoritmické prístupy informatiky s myšlienkami a konceptami teórie hier (nedávno vyšla táto knižka; môžem ju zapožičať ak by mal niekto eminentný záujem).

Christos sa popri akademickej práci angažuje aj v tvorbe komixu o hľadaní základov matematiky. Tento komix neopakovateľným a prístupným spôsobom zachytáva obdobie dlhé 60 rokov, čas v ktorom mnohí hľadači pravdy a logiky sveta, ako napríklad Georg Cantor a Kurt Gödel, prišli v snahe o zahryznutie sa do plodov stromu poznania o zdravý rozum. Rozprávačom príbehu, samozrejme fiktívnym, nie je nikto iný ako sám Bertrand Russell — filozof, matematik, ateista, pacifista a historik.

Ak sa chcete dozvedieť niečo o tvorbe komixu z úst samotných tvorcov (napríklad: ako je tvorba komixu podobná procesu konštrukcie matematického dôkazu?), pozrite si nasledovné tri krátke videá:

(*) Mimochodom, počas môjho PhD štúdia som absolvoval predmet CS 684: Algorithmic Game Theory, prednášaný Evou Tardos, spoluautorkou vyššie spomenutej knihy (dokonca mám na to aj dôkaz, hehe). Jeden z najlepších predmetov aké som kedy absolvoval!

Tréning 1.9: Trojuholník z päťuholníka

Aký tréning? O čo ide? Nazrite najmä sem (heuristiky a stratégie) a sem (extremálny princíp). Tu je v poradí už deviata úloha seriálu o heuristikách a stratégiách riešenia matematických úloh extremálnym princípom (EP). Poteším sa akémukoľvek riešeniu, nemusí byť nutne založené na EP.

Úloha #34: (a) Je možné zo strán každého konvexného päťuholníka vybrať tri a poskladať z nich trojuholník? (b) A čo ak povolíme nie len strany ale všetky tetivy, t.j. úsečky spájajúce ľubovoľné dva vrcholy a prechádzajúce vnútrom päťuholníka? (c) Napokon, aká bude odpoveď keď trojuholník máme povolené “skladať” iba z tetív?

Poznámka 29.4.2009: Úloha (c) je z knihy Arthura Engela, Problem-Solving Strategies.

Poznámka 1.5.2009: Všetky tri časti sú už vďaka vám vyriešené, riešenia nájdete v komentároch.

Ako zbaliť policajtku alebo kalendár v hlave

Moja dcérka Amálka sa narodila 3. marca 2006. Neviem si práve spomenúť aký to bol vtedy deň v týždni. Stavil by som sa, že to bol piatok, ale nie som si už stopercentne istý. Napriek zjavnej degradácii kvality mojej pamäte (a možno práve kvôli nej!) ešte dokážem v hlave narýchlo spraviť nasledovnú jednoduchú kalkuláciu:

.

Áno, bol to piatok!

Toto leto sa žení Matúš, brat mojej manželky a lásky Marianky. Dátum si pamätám, bude to 27. 6.2009. Mala by to byť sobota, veď tak to u nás chodí… Ale ktovie, niekedy bývajú svadby aj v piatok alebo nedeľu. Treba si to overiť! Kalendár pri sebe nemám a tvárme sa, že práve nie som lenivý predviesť trošku mentálnej aritmetiky. Tu je:

.

Tak veru hej, je to tá sobota!

Chcete sa naučiť tento pekný a užitočný trik? Ako vidíte, výpočty sú vcelku jednoduché, takže sa netreba ničoho obávať! Chce to len trošku tréningu. Keď som sa s tým minulé leto zabával, spýtal som sa na rok narodenia okrem iných aj predavačky v novinovom stánku a policajtky na policajnej stanici keď som si šiel po vodičák! Bola to parádna zábava, mysleli si, že som telepat (i keď som im povedal, že to počítam)!

Začneme rýchlym a stručným popisom celého algoritmu. Povedzme, že pracujeme z dátumom narodenia mojej dcérky (3. marca 2006). Dátum pozostáva z troch čísel: 3 (deň v mesiaci), 3 (mesiac) a 2006 (rok). Každému z týchto čísel priradíme istý kód, podľa presne určených pravidiel opísaných nižšie. Kódy potom spočítame a na výsledok sa pozrieme modulo 7; t.j. všímame si len zvyšok po delení číslom 7. Ak napríklad dostaneme číslo 5, ide o piatok! Nula znamená nedeľu, jednotka pondelok, dvojka utorok a tak ďalej. Zostáva už len opísať ako dostaneme spomínané tri kódy.

Deň v mesiaci. Toto je veľmi ľahké. Deň v mesiaci vydelíme číslom 7 a ponecháme si len zvyšok, čo bude náš kód. Napríklad pri dátume 3.3.2006 je to trivialita, číslo 3 po delení sedmičkou dáva zvyšok 3. V prípade Matúšovej svadby je nabližším menším násobkom sedmičky k číslu 27 číslo 21. Keďže 27 = 21 + 6, zvyšok je teda rovný 6.

Keďže aj tak nakoniec všetko počítame modulo sedem, v prípade šestky si ja osobne v hlave zapamätám radšej -1. Konečný výsledok bude rovnaký a mentálna aritmetika sa mierne uľahčí.

Mesiac. Tu sa treba nabifľovať nasledovnú tabuľku číselných kódov prislúchajúcich jednotlivým mesiacom:

6*  =  Január
2*  =  Február
2  = Marec
5  = Apríl
0  = Máj
3  = Jún
5  = Júl
1  = August
4  = September
6  = Október
2  = November
4  = December

Nabifľovať je ten správny termín: čím rýchlejšie dokážete v hlave priradiť mesiacu v roku jeho číslo, tým rýchlejšie sa dopracujuete k odpovedi a tým pôsobivejšie bude celý kúsok vyzerať. Január a február sú zvýraznené hviezdičkou preto, lebo v prestupnom roku tu nastáva výnimka: januáru vtedy treba priradiť číslo 5 a februáru 1.

Prestupný rok v Gregoriánskom kalendári je každý rok deliteľný číslom 4, okrem tých čo sú deliteľné číslom 100. Platí tu ale výnimka z výnimky, roky deliteľné číslom 400 sú prestupné! Tak napríklad rok 2000 je prestupný lebo je deliteľný číslom 400. Roky 1900, 1800 a 1700 nie sú prestupné napriek tomu, že sú deliteľné číslom 4. To preto, lebo sú to násobky stovky, ale nie násobky čísla 400.

Pre roky tvaru 20xy priestupnosť teda zistíme nasledovne: zistíme, či číslo xy je deliteľné štvorkou alebo nie. Ak je, ide o prestupný rok. Pre roky tvaru 19xy to platí tiež, ale s výnimkou roku 1900, ktorý nie je priestupný ná základe vyššiespomenutej  výnimky z výnimky.

Rok. Pre roky 2000 až 2099 spočítame kód roku nasledovne. Ak má rok tvar 2000 + x, potom kód roku bude , t.j. k číslu pripočítame jeho štvrtinu, pričom ignorujeme desatinné miesta. Tak napríklad pre rok 2006 je . Kód roku 2006 je teda . Kód roku 2012 je a roku 2009 zasa . Pri výpočte kódu pre roky 1900 až 1999 postupujeme rovnako, ale k výsledku ešte pripočítame jendotku. Tak napríklad roku 1977 prislúcha kód .

***

A to je všetko!

Nezabudnite mi do komentárov napísať ako ste sa s týmto matematicko-magickým trikom pobavili!

Poznámka 17.4.2009: Na obrázku hore je Axayacatlov kameň, Aztécky mytologický predmet zobrazujúci boha Slnka Tonatiuha, symbol piateho súčasného sveta, piateho slnka. Tonatiuhova tvár je zobrazená uprostred kamennej dosky, ktorá okrem iného symbolicky zobrazuje štyri predošlé obdobia a dá sa teda chápať ako akýsi symbolický kalendár. Nejde však o skutočný kalendár – Aztékovia používali minimálne dva kalendáre. Jeden bol svätský, agrárny a pozostával z 365 dní. Tonalpohualli — duchovný kalendár — pozostával z 260 dní (tonalli). Dvadsať bohov v ňom cyklicky striedalo vládu nad týždňom ktorý mal trinásť dní.

Poznámka 17.4.2009: V súvislosti s týmto článkom som práve narazil na zaujímavú fotku Baracka Obamu.

Sedem divov sveta Richarda Dawkinsa

Všade okolo nás je spústa úžasných vecí: vesmír, hviezdy, planéta Zem, život, bunka, DNA, matematika, veda, mozog, ľudské vynálezy, stavby, náboženstvá a nespočetný rad ďaľších. Ako také sa však javia iba oku schopnému onen úžas vidieť a oceniť. Klasických sedem divov sveta, presnejšie antického sveta architektúry, pozná azda každý: 1) Egyptské pyramídy, 2) Semiramidine visuté záhrady, 3) Artemidin chrám v Efeze, 4) Diova socha v Olympii, 5) Mauzóleum v Halikarnasse, 6) Ródsky kolos a 7) Alexandrijský maják.

Richard Dawkins — evolučný biológ, zanietený ateista, autor kníh ako Sebecký gén alebo Ilúzia boha, tvorca niekoľkých dokumentárnych filmov (napr. Nepriatelia rozumu alebo Génius Charlesa Darwina) — má svoj vlastný zoznam siedmych divov sveta:

1) pavučina
2) ucho netopiera
3) prsty pianistu
4) digitálny kód DNA
5) parabolické zrkadlo
6) embryo
7) David Attenborough 

Tak ako som to dnes  spravil ja, ponorte sa aj vy do hĺbky a krásy týchto siedmych navonok všedných vecí. Nechajte sa uniesť zanieteným rozprávaním Richarda Dawkinsa v jeho polhodinovom dokumente z roku 1997:

Budem rád ak sa v komentároch podelíte o svoje postrehy. Ako by vyzeral váš zoznam siedmich divov sveta?