Chaotický trojfarebný trojuholník

Chaotickým k-farebným trojuholníkom veľkosti n nazvime trojuholník poskladaný z 1+2+...+n kameňov k farieb, ktorý neobsahuje žiadnu trojicu kameňov rovnakej farby umiestnených vo vrcholoch trojuholníka so stranami rovnobežnými so základným trojuholníkom.

Formulujeme si jednu teoretickú úlohu a jednu súťaž pre všetkých, ktorí si myslia, že sú programátorskí machri.

Úloha: Dokážte, že existuje najväčší trojfarebný chaotický trojuholník. Inými slovami, ukážte, že existuje prirodzené číslo n také, že trojfarebný chaotický trojuholník veľkosti n už principiálne nie je možné skonštruovať. Môžete použiť Peťove riešenie predchádzajúceho príkladu a Van der Waerdenovu vetu, na ktorú nás upozornil Nanyk.

Súťaž: Pomocou počítača nájdite trojfarebný chaotický trojuholník s veľkosťou aspoň 15, t.j. väčší ako ten, ktorý som našiel ja:


Nie som si úplne istý s tým, že existuje väčší trojfarebný chaotický trojuholník ako ten môj, ale považujem to za veľmi pravdepodobné. Môj trojuholník je totiž výsledkom krátkeho výpočtu jednoduchého programu v pomalom jazyku R. Každopádne ak sa do riešenia tejto úlohy pustíte, pošlite nám najväčší trojfarebný chaotický trojuholník aký nájdete.

28.8.: Mišo našiel chaotický trojfarebný trojuholník veľkosti 16! Tu je:


Kto Miša prekoná má môj obdiv! To už ale bude asi poriadne ťažké...

Neexistujúce trojuholníky

Na rozdiel od predchádzajúcej úlohy, vyriešenie nasledovného problému si vyžaduje len trochu postrehu a systematický postup.

Z čiernych a bielych kameňov sa snažím poskladať rovnostranný trojuholník so základňou "dĺžky" 5 kameňov ale tak, aby neobsahoval žiadny "monochromatický" rovnostranný trojuholník, t.j. trojuholník, ktorého strany sú rovnobežné so stranami základného trojuholníka a ktorého vrcholy tvoria kamene rovnakej farby. Otázka znie: dá sa to?

Na obrázku je jeden môj neúspešný pokus. (Inak mienim napísať už len tri blogové príspevky o konfiguráciách farebných kameňov a prejdem na niečo iné. Sľubujem :-)

Poznámka 27.8.: Veľmi pekné riešenie tohoto príkladu napísal na svoj blog Peter.

Me3ce

Predstavme si, že vedľa seba kladieme farebné kamene. Monochromatická ekvidištantná trojica, skrátene me3ca, bude každá taká trojica kameňov rovnakej farby, pre ktorú platí: vzdialenosť prvého a druhého kameňa tejto trojice je rovnaká ako vzdialenosť druhého a tretieho kameňa tejto trojice. Na ilustračnom obrázku som znázornil sériu 10 kameňov dvoch farieb, ktorá obsahuje až 5 me3íc.

Ako sa môžete sami ľahko presvedčiť (napríklad otestovaním všetkých 512 možností na počítači), každá séria pozostávajúca z deväť kameňov dvoch farieb už nutne obsahuje nejakú me3cu. Osem kameňov dvoch farieb však me3cu obsahovať nemusí; všimnite si napríklad postupnosť 0X0XX0X0. Takže s dvomi farbami je otázka existencie bezme3cových sérií jednoduchá. Ukazuje sa však, že pre tri farby je to oveľa ťažšie:

Existuje také prirodzené číslo n, že každá séria n kameňov troch farieb obsahuje aspoň jednu me3cu?

Sám na túto zdanlivo jednoduchú otázku neviem odpovedať; môj polhodinový limit na jej vyriešenie nestačil. Preto sa opäť s dôverou obraciam na Vás. :-) Vzhľadom na to, že tento problém nie je triviálny, môžete do komentárov uvádzať nielen úplné riešenie, ale aj každý potenciálne užitočný postreh.

Poznámka 26.8.: Ako v komentári upozornil Nanyk, tento problém je zhodou okolností známy a veľmi ťažký a odpoveď je kladná pre ľubovoľný počet farieb a ľubovoľnú dĺžku ekvidištantnej série. Pre tri farby je maximálna bezme3cová séria dĺžky 26, napríklad

RRYYRRYBYBBRBRRYRYYBRBBYBY

a je dokázané, že každá séria dĺžky 27 už nejakú me3cu obsahuje.

A ak si chcete privyrobiť 1000 dolárov stačí, keď pre každé k ukážete, že pre niektoré n menšie než 2 na k² platí, že každá séria kameňov dvoch farieb dĺžky n už obsahuje nejakú ekvidištantnú monochromatickú k-ticu. Túto odmenu Vám udelí jeden z najvýznamnejších žijúcich matematikov, Ronald Graham.

Neexistujúce obdĺžniky II

Z riešenia úlohy "neexistujúce obdĺžniky" plynie, že konfigurácia kameňov dvoch farieb na mriežke 5×5, alebo väčšej, musí nutne obsahovať aspoň jeden monochromatický obdĺžnik. Ak však máme k dispozícii kamene viacerých farieb, úloha sa skomplikuje.

Existuje vôbec nejaké prirodzené číslo n také, že akákoľvek konfigurácia n×n kameňov troch farieb obsahuje aspoň jeden monochromatický obdĺžnik?

Na ilustračnom obrázku je znázornená konfigurácia 7×7 kameňov troch farieb, ktorá žiadny monochromatický obdĺžnik neobsahuje. To znamená, že ak aj existuje n zo zadania našej úlohy, tak je minimálne 8.

Poznámka 1: Nanyk už našu úlohu vyriešil (pozri komentáre) a z jeho riešenia plynie, že ak je n aspoň 22, tak mriežka n×n kameňov troch farieb už určite obsahuje aspoň jeden monochromatický obdĺžnik. Ak sa chcete s týmto problémom ešte trochu pozabávať, môžete sa pokúsiť buď hornú hranicu 22 znížiť, alebo dolnú hranicu 8 zvýšiť.

Poznámka 2: Trochu som sa s tým hral a podarilo sa mi nájsť konfiguráciu 9×9 kameňov troch farieb neobsahujúcu monochromatický obdĺžnik; pozri obrázok:

Minimálne n, pre ktoré mriežka n×n troch farieb nutne musí obsahovať monodĺžnik, je teda medzi 10 a 22.

FErdóšove piškvorky

Včerajší problém sa nám podarilo úspešne vyriešiť a ešte sme k tomu pridali aj viacero ďalších zaujímavých nápadov. Obdĺžnik, ktorý má všetky vrcholy na kameňoch rovnakej farby, sme nazvali monochromatický obdĺžnik, alebo skrátene monodĺžnik.

Z komentárov ma zaujala hra, ktorú by som nazval "FErdóšove piškvorky", s nasledovnými jednoduchými pravidlami:

Dvaja hráči kladú na mriežku veľkosti n×n kamene, prvý hráč biele a druhý čierne. Vyhráva ten, kto ako prvý vytvorí zo svojich kameňov monodĺžnik.

Keďže na mriežke 5×5 obsahuje každá konfigurácia z kameňov dvoch farieb nejaký monodĺžnik, tak na tejto mriežke, alebo aj na akejkoľvek väčšej, nemôže táto hra skončiť remízou. Stačí si zobrať jednu sadu GO kameňov a môžete hrať! Zaujímavé by to bolo vtedy, ak by neexistovala jednoduchá vyhrávajúca stratégia. Keď si kliknete na ilustračný obrázok, spustí sa Vám animovaný gif jednej hry, v ktorej si biely vynútil výhru už po druhom ťahu čierneho.

Ak si FErdóšove piškvorky zahráte, napíšte nám do komentárov svoje dojmy.

Variant 1: Trochu som sa s tým pohral a vyzerá to tak, že v klasickej hre si biely vždy pomerne jednoducho vynúti výhru. Zaujímavou sa táto hra môže stať vtedy, keď trochu upravíme pravidlá:

Ja mám biele a Ty čierne kamene. Na začiatku Ty umiestniš moje dva biele a svoje dva čierne kamene kdekoľvek chceš, samozrejme tak, aby si mi otvorenie čo najviac sťažil a sebe čo najviac zjednodušil. Potom už kladieme kamene striedavo, t.j. ja biely kameň, Ty čierny a tak ďalej, až kým jeden z nás nevytvorí monodĺžnik.

Variant 2: V komentári ma Nanyk presvedčil, že predchádzajúca obmena pravidiel už dáva rozhodujúcu výhodu čiernemu. Napadla ma však ďalšia obmena, ktorá stavia všetko na hlavu:

Dvaja hráči kladú na mriežku veľkosti 5×5 kamene, prvý hráč biele a druhý čierne. Ten, kto ako prvý vytvorí zo svojich kameňov monodĺžnik, PREHRÁVA.

Cieľom je teda prinútiť svojho súpera aby vytvoril monodĺžnik. Opäť, na základe výsledku predchádzajúcej úlohy vieme, že táto hra nemôže skončiť remízou.

Ak máte chuť, môžeme si dať prostredníctvom komentárov jednu partičku. Sĺpce označíme a-e a riadky 1-5. Keďže sa zdá jasné, že biely je v nevýhode, tak biely budem ja a začínam ťahom c3. :-)

Neexistujúce obdĺžniky

Počas poobedňajšej prestávky ma dnes napadol jeden rekreačný problém, ktorý som sa bezúspešne snažil vyriešiť asi pol hodiny a viac času naň neobetujem. Ale Vy možno budete úspešnejší.

Existuje taká konfigurácia 25 bielych a čiernych kameňov na mriežke 5 krát 5, že žiadna štvorica kameňov rovnakej farby neleží na vrcholoch spoločného obdĺžnika, ktorý má strany rovnobežné so stranami štvorca?

Na obrázku je znázornený jeden môj neúspešný pokus, v ktorom existujú až dva obdĺžniky s vrcholmi rovnakej farby. Keďže riešenie tohoto problému nepoznám, nemôžem zaručiť, že nie je veľmi ťažký!

Katalóg konvexných polyédrov

Pri riešení najnovšieho problému od Peťa ma napadlo, že by sme si mohli zadať nasledovnú úlohu trochu nezvyklého typu:

Na obrázku vyššie (kliknutím sa zväčší) zodpovedajú riadky počtu v vrcholov a stĺpce počtu e hrán. Do niektorých políčok som už doplnil telesá, ktoré majú príslušný počet vrcholov a hrán. Bod získava ten, kto ako prvý doplní do niektorého prázdneho políčka nejaký konvexný polyéder s príslušným počtom vrcholov a hrán, prípadne ak dokáže, že pre kombináciu v a e (spomedzi tých kombinácií, ktoré sú na obrázku) neexistuje žiadny konvexný polyéder s počtom vrcholov v a počtom hrán e.

Pochopiteľne, výhodu má ten, kto sa do riešenia pustí ako prvý, pretože neskôr sa budú hľadať príslušné telesá alebo dôkazy ťažšie. Nájdené telesá môžete popísať slovne (napríklad ako ich možno dostať z iných telies) v komentári k tomuto príspevku, alebo mi môžete poslať načrtnutý obrázok mailom. Pokúste sa riešiť daný problém vlastnými silami. Nikomu by nepomohlo, ak by ste vypátrali kompletné riešenie niekde na internete a potom sa ním tu prezentovali.

17.8.: Štyri polyédre doplnila Hugo.
18.8.: Ďalších päť polyédrov doplnila Hugo.
19.8.: Ešte ďalších päť polyédrov doplnila Hugo.
20.8.: Peťo ukázal nemožnosť konštrukcie 17-tich polyédrov.
20.8.: Posledné okienko zaplnila Hugo.

Ako Dumbledore udeľujem ešte 1 bod navyše pre Huga(u?) za pozitívne výsledky a Peťovi -1 bod za negatívne výsledky, čiže celkový výsledok zápasu Hugo-Peťo je 16:16. :-)

Geomag

Konštrukčná sada Geomag nie je lacný špás, ale čo by už človek nekúpil svojej jedinej dcérke, všakže. Základom Geomagu sú oceľové guličky a magnety v podobe tyčiniek, ktorých spájaním je možné vyrobiť množstvo priestorových modelov, napríklad základných trojrozmerných telies. Agátkina sada obsahuje okrem guličiek a tyčiniek aj farebné "výplne" v tvare rovnostranného trojuholníka, štvorca, kosoštvorca a pravidelného päťuholníka, ktoré je možné použiť na spevnenie, alebo skrášlenie vzniknutých konštrukcií.

Zoo konvexných priestorových telies, ktoré majú všetky hrany rovnakej dĺžky a ktorých steny sú pravidelné n-uholníky, môžeme v zásade rozdeliť do piatich skupín: platónske telesá, archimedovské telesá, prizmy, antiprizmy a Johnsonove telesá. Na nasledovnom obrázku sú znázornené štyri Johnsonove telesá poskladané z Geomagu (kliknutím sa obrázok zväčší).


Konkrétne, na fotografiách sú augmented tridiminished icosahedron (vľavo hore), square gyrobicupola (vpravo hore), biaugmented pentagonal prism (vľavo dole) a bilunabirotunda (vpravo dole). Samozrejme, na zložitejšie telesá by sme potrebovali oveľa viac ako 31 tyčiniek a 24 guličiek, ktoré obsahuje naša sada. Vytrínový kúsok by mohol byť napríklad taký Parabigyrate Rhombicosidodecahedron.

Na koniec tohto príspevku ešte jedna oddychová úloha, ktorá je inšpirovaná tabuľkou v dolnej časti stránky mathworldu o Johnsonovych telesách.

Konvexné trojrozmerné teleso má n₃+n₄+n₅ stien, z toho n₃ trojuholníkových, n₄ štvorcových a n₅ päťuholníkových. Koľko má toto teleso vrcholov?

Štyri guličky

Obligátnou súčasťou zbierok úloh z rekreačnej matematiky sú príklady týkajúce sa váženia guličiek. Tú najznámejšiu úlohu tohoto typu sme už na blogu QED mali a ak by ste mali záujem, môžeme si tu formulovať aj inú podobnú klasiku. Dnes večer som však pre Vás vymyslel zbrusu nový príklad, ktorý sa tiež týka váženia. Na jeho vyriešenie nie je nutné poznať žiadnu vyššiu matematiku; odborné vzdelanie pri jeho riešení nepredstavuje veľkú výhodu. Logické myslenie však samozrejme áno.


Mám štyri na pohľad rovnaké guličky, pričom s istotou viem, že práve jedna z nich je buď ľahšia alebo ťažšia v porovnaní so zvyšnými tromi, ktoré majú presne rovnakú hmotnosť. Máme k dispozícii dvojmiskovú elektronickú váhu, ktorá vie oznámiť len dva rôzne výsledky a to: "hmotnosť v miske naľavo je väčšia ako hmotnosť v miske napravo", alebo "hmotnosť v miske napravo je väčšia ako hmotnosť v miske naľavo". Ak sa na miskách vážia rôzne hmotnosti, odpovie váha zaručene správne. Ale ak sa vážia rovnaké hmotnosti, zvolí váha každú zo svojich dvoch možných odpovedí s pravdepodobnosťou 1/2. Našim cieľom je zistiť, ktorá z guličiek je odlišná od ostatných dvoch a či je ľahšia, alebo ťažšia. Môžeme však vykonať maximálne 3 váženia. Aký systém váženia by ste zvolili?

Banachov-Tarskeho paradox: časť 3: baby

Samotný Banachov-Tarskeho paradox nie je vôbec jednoduché dokázať, pretože pozostáva z pomerne veľkého počtu krokov. Avšak existujú aj také tvrdenia, ktoré v sebe obsahujú podobný kolaps intuície ako Banachov-Tarskeho paradox, no ich formálny dôkaz je relatívne krátky. Tieto tvrdenia sa nazývajú "baby Banach-Tarski" a my si teraz jedno takéto baby ukážeme.

Povieme, že reálne čísla x a y z intervalu [0,1] sú "ekvivalentné", zapisujeme x~y, ak je rozdiel x-y racionálne číslo. Relácia "~" je takzvanou reláciou ekvivalencie, pretože platí a) x~x, b) ak x~y, tak y~x a c) ak súčasne x~y a y~z, tak aj x~z. Relácia ~ rozkladá interval [0,1] na disjunktné "triedy ekvivalencie", t.j. na množiny navzájom ekvivalentných čísiel.

Jednou z tých tried ekvivalencií je napríklad množina všetkých racionálnych čísiel v intervale [0,1]. Ak s je akékoľvek fixné iracionálne číslo, tak všetky tie čísla s+q z intervalu [0,1], pre ktoré je q racionálne číslo, tiež tvoria triedu ekvivalencie. Je zrejmé, že každá z týchto tried ekvivalencie je spočítateľná množina, ale samotný počet týchto tried je nespočítateľný.

Všimnite si, že už tento rozklad intervalu [0,1] na triedy ekvivalencie je dosť nenázorný. Príslušné triedy ekvivalencie sú navzájom úplne "prepletené"; napríklad platí, že pre každé číslo x v intervale (0,1) a pre ľubovoľné dostatočne malé kladné ε obsahuje intervalík (x-ε, x+ε) nekonečne veľa prvkov z každej jednej tejto triedy ekvivalencie.

Každopádne, na základe axiómy výberu vieme z každej z týchto tried ekvivalencie vybrať po jednom čísle. Množina pozostávajúca z práve jedného zástupcu z každej triedy ekvivalencie sa nazýva Vitaliho množina a my ju budeme označovať symbolom V. (Samozrejme, takýchto výberov existuje nekonečne veľa, čiže aj Vitaliho množín je v zmysle našej definície nekončene veľa. My však budeme pracovať s jednou fixnou Vitaliho množinou V.)

Označme množinu racionálnych čísiel Q a množinu racionálnych čísiel v intervale [0,1] ako Q[0,1]. Keďže množiny Q[0,1] a Q sú obe nekonečné spočítateľné, tak existuje bijektívne zobrazenie f medzi množinami Q[0,1] a Q. To znamená, že pre každé racionálne číslo q existuje práve jedno racionálne číslo r z intervalu [0,1], pre ktoré platí f(r)=q.

Uvažujme nasledovné dva spočítateľné systémy množín.


Ľahko si dokážete platnosť nasledovných tvrdení.

1) Ako systém A, tak aj systém B pozostáva z navzájom disjunktných množín.
2) Každá množina zo systému A je podmnožinou intervalu [0,2].
3) Množiny systému B sú len posunutím množín systému A.
4) Zjednotenie množín zo systému B je množina všetkých reálnych čísiel.

Čiže, voľne povedané, množiny V+r, kde r je z Q[0,1], sa navzájom nijako neprekrývajú a všetky spoločne okupujú len istú časť intervalu [0,2]. No napriek tomu je ich možné poposúvať tak, že kompletne pokryjú celú reálnu priamku!

Ako je takéto niečo možné? Základom všetkých podobných paradoxov je existencia "nemerateľných množín", t.j. množín, ktorým principiálne nevieme priradiť "úhrnnú dĺžku" (v prípade štandardného Banachovho-Tarskeho paradoxu sa jedná o množiny, ktorým nie je možné nijako konzistentne priradiť "celkový objem"). V našom prípade je nemerateľnou množinu práve Vitaliho množina.

Dva znaky

Budeme hádzať mincou až pokým nepadne znak dvakrát za sebou. Koľko budeme potrebovať v strednej hodnote (t.j. "v priemere") hodov?

Toto je pomerne prirodzená a častá úloha, ktorej riešenie však nie je úplne triviálne. (Jej ekvivalentná formulácia sa vyskytuje napríklad v tejto Oxfordskej učebnici).

5.8.: Úlohu sme už nielenže vyriešili (pozri komentáre), ale Peťo prišiel s takým postupom, ktorý sa dá použiť na vyriešenie oveľa všeobecnejšej úlohy:

Robíme nezávislé experimenty, pričom každý experiment môže skončiť výsledkom "úspech" (s pravdepodobnosťou p), alebo výsledkom "neúspech" (s pravdepodobnosťou 1-p). Skončíme akonáhle zaznamenáme k úspešných experimentov za sebou. Aká je stredná hodnota všetkých experimentov, ktoré vykonáme?

Výsledok je nasledovný:


S prvou formulkou sa ľahšie počíta ak je k veľké číslo, druhá mi však pripadá krajšia. V špeciálnom prípade, ktorý zodpovedá pôvodnému zadaniu, máme p=1/2 a k=2, čiže výsledok je 6. Ak by sme napríklad hádzali kockou a čakali na padnutie troch šestiek za sebou, tak p=1/6 a k=3, čiže očakávaný počet hodov je 6+6²+6³=258 :-)

Inak uvažujem, že vypíšem súťaž, ktorú vyhrá ten z Vás, kto nám pošle najzaujímavejšiu matematickú úlohu. Čo Vy na to? Svoje názory, prípadne organizačné pripomienky môžete písať do komentárov k tomuto príspevku a tiež sa môžete vyjadriť v novej miniankete (v pravom stĺpci blogu).