22 augusta 2008

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.

8 komentárov:

Nanyk povedal(a)...

nefunguje uz pouzita metoda aj tu?:

pre dost velke n musi prvy riadok obsahovat dost velke m farieb x

riadok pod tymito x-ami moze obsahovat nanajvys jedno x

preto obsahuje dost velke t farieb 0

kazdy riadok pod tymito t 0-ckami
moze obsahovat nanajvys jedno x a jedno 0, teda obsahuje t-2 farieb 3

farba 3 tak vytvori obdlznik

Radoslav Harman povedal(a)...

Fajn, myšlienka je správna! Skús to ale spresniť tak, že o konkrétnom n dokážeš, že konfigurácia n×n už musí obsahovať monochromatický obdĺžnik. Skráta: Aké je minimálne to "dosť veľké n"?

Nanyk povedal(a)...

minimalne n asi nenajdem, to by som musel vyplnit n-1xn-1 obdlznik bez monodlznika

metoda zarucuje n<24

potom aspon 23/3~8 x-ov je v prvom riadku

pod nimi 7/2~4 0-ciek

>pod nimi aspon 4/3~2 x-ov

totalny chaos neni:)

Radoslav Harman povedal(a)...

Vetou aké je minimálne to "dosť veľké n" som myslel aké je minimálne n, pre ktoré funguje Tvoj dôkaz a nie pre aké minimálne n už každá konfigurácia n×n kameňov troch farieb obsahuje monodĺžnik. To by bola naozaj veľmi ťažká úloha.

Ale k tomu Tvojmu dôkazu: n=23 skutočne zaručuje aspoň 8 kameňov spoločnej farby (to by už inak zaručovalo aj n=22), nazvime ju x. A pod nimi by museli byť naozaj aspoň 4 kamene farby, ktorú nazveme 0, ak nechceme už v tomto riadku spraviť obdĺžnik z x-ov. Ale pod nimi by kľudne mohol byť napríklad riadok, x0++, kde + je tretia farba, nie? (Ide mi o to, aby sme to zdôvodnili úplne presvedčivo; inak samozrejme uvažuješ úplne správne.)

S tým "totálnym chaosom" to je dobrá poznámka v súvislosti s touto úlohou. Zdá sa totiž, že ak by sme mohli urobiť "nekonečne veľkú mriežku bez monodĺžnikov", tak by to musel byť "totálny chaos". Ale to by sa, aspoň mne osobne, zdalo aj pri požiadavke neperiodicky vydláždiť celú rovinu ak máme k dispozícii len dva druhy dlaždíc. A predsa také dláždenia existujú ...

Nanyk povedal(a)...

isteze, nenapisal som to presne..pod tymi 4roma nulami vzniknu dve + farby a tie mozno polozit na na styri pozicie len 6 sposobmi, co nasich 22 riadkom v pohode zvlada

jasne, "chaos" je tuna len intuitivny pojem, v matike je vela "chaotickych" utvarov:), najlepsi priklad su asi prvocisla(teda ich poloha v N)

Radoslav Harman povedal(a)...

OK nanyk. Super. Keďže si taký zdatný riešiteľ, mohol by si skúsiť aj niektoré ďalšie úlohy na QED, ktoré ešte nikto nevyriešil (alebo sa teda aspoň neunúval napísať svoje riešenie do komentárov). Všetky dosiaľ nevyriešené úlohy som dal pod spoločný link v časti "Označenia" na pravej strane blogu.

Nanyk povedal(a)...

je to pekne ked vznika taka "sien nevyriesenych problemov"

mozno by bolo prestiznejsie(lakavejsie) keby ich bolo menej:)
hlavne jednoduchoformulovatelnych

paradox: "jednoduchoformulovatelne" nie je jednoduchoformulovatelne

priznam sa, nejak ma nelaka riesit ich...aj tak su asi tazke

zaujimavejsie mi pride riesit problem: ako tazky moze byt taky maticky problem...a da sa vyriesit? co je v nasich silach?

na druhu stranu, to su tiez "len obycajne" problemy a asi sa vacsina problemov da na taky filozoficky podton preformulovat

no nic, skusim nejaky z nich vyriesit, ak to pojde, napisem

Radoslav Harman povedal(a)...

Á Nanyk, Ty máš blog; super. Vidím, že sa zaoberáš základmi matematiky, logikou a filozofiou. To sú facinujúce veci...

Čo sa týka tých nevyriešených problémov, tak väčšina z nich je pomerne ľahká, lebo riešenie poznám.

Snáď len dve (oblúky v Pascalovej pavučine a úplná charakterizácia odmocním ortogonálnych matíc) sú také, ktorých riešenie neviem a možno by som aj tie vedel, keby som sa im seriózne venoval. Seriózne však svoju kapacitu venujem skôr len skutočnému výskumu. Publish or perish, však vieš.