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ý!
otestovat 2^25 variacii :)
OdpovedaťOdstrániťmichal: :-) Samozrejme, počítač by to zvládol, aj keď urobiť 33 554 432 nie celkom triviálnych testov konfigurácií by asi trvalo hodnú chvíľku (pre každú konfiguráciu treba zisťovať prítomnosť obdĺžnika s rovnako ofarbenými vrcholmi, čo je, ak to chceme robiť efektívne, zaujímavý problém sám o sebe). Ale ak sa niekomu chce, môže to skúsiť.
OdpovedaťOdstrániťtaka konfiguracia neexistuje:
OdpovedaťOdstrániťprvy riadok stvorca obsahuje aspon tri cierne xxx, kazdy riadok pod tymito ciernymi aspon dve biele:
xxx
00
00
0 0
preto v poslednom riadku obdlzink vznikne
Neexistuje! Ten argument je jasný... Takže som mohol hľadať koľko som chcel. Fajn.
OdpovedaťOdstrániťPokúsim sa na túto tému vymyslieť nejaké zaujímavé variácie.
len aby z toho nevznikol otvoreny problem Ramsayovskeho typu(vid odkaz):)
OdpovedaťOdstrániťjezmar: Mne to hneď trochu pripomenulo Ramseyove čísla (kedysi som máličko študoval pravdepodobnostnú metódu, ktorej typickým prípadom použitia je práve určenie hraníc na Ramseyove čísla.) Možno by sme mohli formulovať nasledovnú úlohu, ale tá by bola asi zabijácka. Pre jednoduchosť vyjadrovania nazvime každý obdĺžnik, ktorý má rovnako zafarbené vrcholy a jeho strany sú rovnobežné s priamkami základnej mriežky, ako "monochromatický obdĺžnik" :-)
OdpovedaťOdstrániťPre dané prirodzené čísla r,f, aké je minimálne S(r,f), že každý štvorec veľkosti S(r,f)xS(r,f) z kameňov f rôznych farieb musí obsahovať aspoň r monochromatických obdĺžnikov?
Keďže (už pre f=2), ako sa dá ľahko presvedčiť, štvorec 4x4 nemusí obsahovať ani jeden monochromatický obdĺžnik (to je dobrý termín nie? :), tak S(1,2)=5. Ešte by som si dovolil tipnúť, že aj S(2,2)=5, lebo najmenší počet monochromatických obdĺžnikov, ktoré som na mriežke 5x5 dosiahol, bol 2. Ale aké sú však ďalšie hodnoty funkcie S je úplne vo hviezdach.
Možno by však niekto vedel určiť aspoň nejaké hranice. Ja jednu strašne hrubú mám: S(r,2)<=5k, kde k je najmenšie také, že k^2>=r :)
Anonymný: krásny dôkaz!
OdpovedaťOdstrániťÁno, je to veľmi bystrý dôkaz; je trochu škoda, že sa nám autor nepodpísal.
OdpovedaťOdstrániťMožno by som mohol ešte dodať, že na mriežke 4x5 sa konfigurácia "bez monochromatických obdĺžnikov" dá nájsť. Čiže 5x5 je najmenšia obdĺžniková mriežka, na ktorej to nejde. Ten dôkaz inak skutočne využíva to, že ako jeden, tak aj druhý rozmer mriežky je aspoň 5. Pekné.
vivat monochromaticky obdlznik!
OdpovedaťOdstrániťtazke(az kombinatoricke) ulohy, ten tvoj odhad mi uplne staci, popravde dolezite je akurat to ze existuje nejaky:)
skusim ukazat jeden spodny(dost mizerne takze neodporucam citat)
Povedzme ze na stvorci BxB hraju hru dve farby(striedavo ofarbuju policka, vyhrava kto prvy ofarbi r obdlznikov). Ak II zahra remizu tak BxB stvorec mozno ofarbit tak aby neobsahoval 2r monodlznikov a teda S(2r,2)>B.(pozn.:I ma neprehravajucu strategiu podla nejakej znamej vety)
Def.: k-uniformny hypergraf je taky graf ktoreho kazdu hranu tvori prave k vrcholov
teraz trik
existuje taka veta(erdos, selfridge): na k-uniformnom hypergrafe s menej ako 2^(k-3) hranami ma II remizujucu(neprehravjucu) strategiu(v hre kde striedavo s I ofarbuju vrcholy grafu s cielom ofarbit celu hranu)
aspon dufam
povedzme ze r monodlznikov sa zarata za r iba ak su vsetky po dvoch disjunktne co sa tyka vrcholov(zneuzitie zadania, sorac), potom
kazda r-tica (disjunktnych) obdlznikov je hrana (kazda hrana ma teda 4r vrcholov), dla vety ak je hran menej ako 2^(4r-3) tak stvorec mozno ofarbit bez toho aby bolo 2r obdlznikov mono.
stvorec BxB ma c=BB(B-1)(B-1)/4 obdlznikov, teda menej ako (c nad r) hran(to su iba tie disjunktne), preto
ak (c nad r)<2^(4r-3) tak S(2r,2)>B
pre r=1 dostavame S(2,2)>2 :) pre velke r je dokonca odhad stale efektivnejsi
pomocou pouzitej vety sa da dokazat(dodnej najlepsi) spodny odhad pre ramzej cisla(probabilistic method ktoru spominas je vsak efektivnejsia metoda). Mozno to aspon trochu poukazuje na spolocne vlastnosti tych uloh, i ked pouzitim tej "univerzalnej vety" sa da dokazat vselico, iste sa da pouzit aj efektivnejsie na nasu ulohu nez tak ako som to ukazal. Mozno je dokonca moj odhad trivialny, neviem neoveroval som to, netrufam si...