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?