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.
nefunguje uz pouzita metoda aj tu?:
OdpovedaťOdstrániť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
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"?
OdpovedaťOdstrániťminimalne n asi nenajdem, to by som musel vyplnit n-1xn-1 obdlznik bez monodlznika
OdpovedaťOdstrániť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:)
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.
OdpovedaťOdstrániť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ú ...
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
OdpovedaťOdstrániťjasne, "chaos" je tuna len intuitivny pojem, v matike je vela "chaotickych" utvarov:), najlepsi priklad su asi prvocisla(teda ich poloha v N)
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.
OdpovedaťOdstrániťje to pekne ked vznika taka "sien nevyriesenych problemov"
OdpovedaťOdstrániť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
Á Nanyk, Ty máš blog; super. Vidím, že sa zaoberáš základmi matematiky, logikou a filozofiou. To sú facinujúce veci...
OdpovedaťOdstrániťČ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š.