Zábava s angličtinou: kvázipalindrómy

V poslednej dobe mám menej času na blog (začal sa semester) ale v rámci oddychu sem občas niečo malé pridám. Dnes som sa trochu pohral s anglickým frekvenčným slovníkom a vyhľadal som také štvor- a viacpísmenové slová, ktoré majú význam aj keď ich prečítame odzadu (akési kvázipalindrómy; možno to má nejaké oficiálne meno). Pozrite si ich zoznam; víťazmi sa pre mňa stali dvojice tinker-reknit, live-evil a repel-leper. :-)

Poznámka 2.10.: Mišov komentár ma primäl k tomu, aby som (pomocou počítača) vyhľadal aj tie anglické jednoslovné "kvázipalindrómy", ktoré nie sú v základnom tvare. Je ich celkom dosť (tu je zoznam) a to mi určite ešte nejaké chýbajú.

Zábava s angličtinou: palindromes

palindrome: a word, line, verse, number, sentence, etc., reading the same backward as forward, as "madam".

Pokúste sa v priebehu troch minút napísať čo najviac anglických jednoslovných palindrómov, t.j. slov, ktoré sa čítajú rovnako odpredu aj odzadu, pričom nepočítame vlastné podstatné mená, skratky a citoslovcia. Koľko ste ich našli? (Slovo "madam" sa nezapočítava :-)

Skontrolujte si správnosť podľa tohoto zoznamu, ktorý som vygeneroval v R-ku pomocou frekvenčného slovníka. Svoj výsledok prosím zaznačte do formulára v pravom stĺpci blogu. (Poll sme už ukončili; výsledky si môžete pozrieť na obrázku na konci príspevku.)

Poznámka 29.9.: Do zoznamu palindrómov som doplnil niektoré slová, ktoré nie sú v základnom tvare. Samozrejme, stále nemôžem s istotou tvrdiť, že môj zoznam je kompletný.

Počítame šesťuholníky II

Máme šesťuholník, ktorého všetky vnútorné uhly sú 120 stupňov, pričom dĺžka strán AB a DE je n₁, dĺžka strán BC a EF je n₂ a dĺžka strán CD a FA je n₃ (kde n₁, n₂ a n₃ sú prirodzené čísla). Tento šesťuholník pokryjeme rovnostrannými trojuholníkmi so stranami dĺžky 1. Koľko pravidelných (rovnostranných) šesťuholníkov sa dá nájsť vo vzniknutom obrazci?

Na ilustračnom obrázku máme znázornený prípad n₁=2, n₂=3 a n₃=5, kde nájdeme 30 pravidelných šesťuholníkov (8 takých, ktoré majú strany dĺžky 2 a 22 takých, ktorých strany majú dĺžku 1).

Pomocou Katkinho riešenia predchádzajúceho príkladu by nemal byť problém túto úlohu vyriešiť. Riešenie indukciou môže byť užitočná nezávislá kontrola.

Počítame šesťuholníky

Nasledovná úloha ma opäť napadla pri hre s Agátkou a geomagom. Je samozrejme veľmi jednoduchá, avšak riešenie je netradične príjemné.

Koľko pravidelných šesťuholníkov je možné nájsť na obrázku veľkého pravidelného šesťuholníka so stranami dĺžky n, ktorý je poskladaný z rovnostranných trojuholníkov so stranami dĺžky 1?

Na ilustračnom obrázku je znázornený prípad n=2, pre ktorý je správna odpoveď 8; jeden pravidelný šesťuholník má strany dĺžky 2 a 7 ďalších šesťuholníkov má strany dĺžky 1.

Poznámka 22.1.: Vidím, že sa nemáte k činu, čo ma trochu mrzí, pretože mám pripravené zovšeobecnenie tejto úlohy a nechcem ho uviesť skôr, ako máme vyriešený tento špeciálny prípad. Aby som Vás trochu inšpiroval, zobrazil som situáciu pre n=3:


Na obrázku je 1 pravidelný šesťuholník so stranou veľkosti tri, 7 pravidelných šesťuholníkov so stranou veľkosti 2 a 19 pravidelných šesťuholníkov so stranou veľkosti 1. Spolu je to teda 27 šesťuholníkov.

Hadamardova hypotéza

Sériu príspevkov týkajúcich sa konfigurácií kameňov by som chcel ukončiť jednou naozaj ťažkou úlohou. Tak ťažkou, že odoláva pokusom o vyriešenie už minimálne od tridsiatych rokov 20. storočia, no s veľkou pravdepodobnosťou nad ňou rozmýšľali už v 19. storočí James Sylvester a Jacques Hadamard. Ale kto vie? Možno je medzi Vami niekto, koho napadne nejaký veľmi originálny trik a stane sa slávnym...

Jedno z viacerých možných zadaní tejto úlohy je prekvapivo jednoduché:

Hadamardova domnienka: Nech n je akýkoľvek násobok štyroch a nech mriežka n×n má najnižší riadok ako aj najľavší stĺpec pokrytý čiernymi kameňmi. Je možné túto mriežku doplniť bielymi a čiernymi kameňmi tak, že každá dvojica riadkov ako aj každá dvojica stĺpcov má presne na n/2 pozíciách kamene rovnakej farby a na zvyšných n/2 pozíciách kamene rôznej farby?

Na ilustračnom obrázku je názorná ukážka, že to skutočne je možné pre n=4 a n=8:


Uveďme si ešte dve ekvivalentné formulácie Hadamardovej domnienky; prvá je klasická a druhú som pre Vás poprivymyslel ja.

Ekvivalentná formulácia 1: Existuje pre každé n, ktoré je násobkom štyroch Hadamardova matica H_n? Hadamardova matica H_n je taká matica typu n×n, ktorej prvky sú buď -1, alebo 1 a pre ktorú platí H_nH_n^T=nI_n, kde T označuje transpozíciu matice a I_n je jednotková matica rozmeru n×n.

Ekvivalentná formulácia 2: Nech n je akýkoľvek násobok štyroch. Dá sa vybrať n vrcholov (n-1)-rozmernej kocky tak, aby všetky vzájomné vzdialenosti týchto vrcholov boli rovnaké?

Všimnite si, že pre n=4 je podmienka z formulácie 2 splnená: Skutočne, ľahko nájdeme také štyri vrcholy klasickej trojrozmernej kocky, ktoré majú všetky vzájomné vzdialenosti rovnaké, t.j. tvoria vrcholy pravidelného štvorstenu:


Dôležitosť Hadamardovej domnienky umocňuje fakt, že Hadamardove matice nie sú len intelektuálnou zábavkou pre čistých matematikov, ale majú veľmi konkrétne aplikácie, napríklad v teórii kódovania, alebo pri navrhovaní štatistických experimentov.

Ak sa Vám nepodarí vyriešiť našu úlohu vo všeobecnosti, t.j. pre všetky násobky štyroch, môžete sa pokúsiť aspoň nájsť príslušnú konfiguráciu kameňov (Hadamardovu maticu, resp. n-ticu vrcholov kocky) pre konkrétny násobok štyroch. Najmenšia veľkosť, pre ktorú takáto konfigurácia ešte nie je skonštruovaná, je n=668.

Formuláciu 2 odporúčam pre tých, ktorí majú obzvlášť dobrú geometrickú predstavivosť. Stačí si totiž predstaviť 667 rozmernú hyperkocku a z jej približne 6×10²⁰⁰ vrcholov vybrať 668, ktoré tvoria vrcholy pravidelného 667 rozmerného simplexu.

Držím palce! :-)

Poznámka: Budúci týždeň som na konferencii, takže chvíľu nebudem písať na blog. Stay tuned!

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.