V šachovnici m × m máme 2m políček obarveno modře. Na jedno z modrých
políček umístíme věž. Věží se můžeme pohybovat pouze po modrých
políčkách, přičemž vždy musíme střídat vodorovný a svislý směr pohybu.
Dokažte, že v libovolném rozestavění modrých políč
netreba dokazat nahodou to, ze aj ked modre rozostavis tak ako je oridzinl sachovnica, tak ze stale ti niekde vznikne modry stvorec 2X2 po ktorom sa mozes do osaletia hybat?
moment, ale to, ze sa moze pohybovat len po modrych znamena, ze tam zacne a ukonci pohyb, alebo ze cely pohyb sa odohrava na modrych?
pretoze v tom druhom pripade ak rozostavis modre tak, ze sa budu dotykat len rohom alebo podobne ako v @9 , cele to pada, nemas ziaden pohyb, lebo tych modrych je ovela menej nez vsetkych policok.
a aky velky moze byt pohyb? moze prejst celu dlzku jednym pohybom, alebo sa za pohyb berie len krok o 1?
@15 aha, tak potom staci, ze bude v kazdom rade a stlpci min. 2 alebo 0, nie? pretoze, ked sa raz napr. horizontalne dostanes na nejake policko, potrebujes sa odtial vertikalne dostat, musi tam byt este jedno.
Ja by som to robila takou nejakou indukciou. (Dufam, ze som pochopila zadanie prikladu
Pre m = 2 to plati.
Teraz predpokladajme, ze to plati pre vsetky cisla az po M, a chceme to dokazat pre M+1.
1. Ak existuje riadok R a stlpec S taky, ze maju dokopy nanajvys 2 modre policka, skrtneme ich. Tym dostaneme sachovnicu MxM na ktorej je prinajhorsom 2*M modrych policok (lebo bolo 2*(M+1) a skrtli sme maximalne 2), cize z indukcneho predpokladu, na tomto zvysku sachovnice existuje ten chceny cyklus modrych policok.
2. Ak ziadna takato dvojica R a S neexistuje, tak tvrdim, ze kazdy riadok a kazdy stlpec obsahuje prave 2 policka.
Dokaz: Bez ujmy na vseobecnosti, povedzme, ze je tam riadok R v ktorom je maximalne 1 modre policko. Potom ale v kazdom stlpci musia byt aspon 2, neratajuc toto jedno (pretoze inak by sme dostali stlpec S taky ze R+S maju max 2 modre policka). Cize na sachovnici je minimalne 2*(pocet stlpcov) + 1 modrych policok, co je ale viac ako 2*(pocet stlpcov) = kolko ich ozaj je.
Cize kazdy riadok (a podobne, kazdy stlpec) ma aspon 2 modre policka. Kedze dokopy ich je 2*(M+1), musi mat kazdy riadok / stlpec PRAVE 2 take.
No, ale teraz proste zacni v lubovolnom modrom policku a napr. zacni v riadku. Je tam prave 1 dalsie modre policko: chod nanho. Teraz v tomto stlpci je tiez prave 1 dalsie modre policko: chod nanho. Teraz v tomto riadku ... a tak dalej. Modrych policok je konecny pocet, a ty v kazdom kroku mozes pokracovat, takze eventuelne skocis na nejake, na ktorom si uz bola. Tadaaa, mas cyklus.
Je mozne ze to ide ovela jednoduchsie.. a ospravedlnujem sa, ze vysvetlujem ako trt, nikdy mi to moc neslo.
@qwer28@piter09 pripadne ma skuste skontrolovat, ak sa vam chce a nie je to az take nezrozumitelne
Roleta je špeciálny inkognito mód, ktorým skryješ obsah obrazovky pred samým sebou, alebo inou osobou v tvojej izbe (napr. mama). Roletu odroluješ tak, že na ňu klikneš.
19 komentov
napr. (1-modré políčko, 0-biele)
1 1 1 0
0 1 0 0
0 0 1 1
0 1 0 1
m+(m-1) je maximalny pocet modrych policok ktore sa daju zostavit tak aby sa nedalo hybat do nekonecna. Ale ci je to dokaz to nevim. asi nie XD
Ach, nás toto čaká v letnom semestri ...
pretoze v tom druhom pripade ak rozostavis modre tak, ze sa budu dotykat len rohom alebo podobne ako v @9 , cele to pada, nemas ziaden pohyb, lebo tych modrych je ovela menej nez vsetkych policok.
a aky velky moze byt pohyb? moze prejst celu dlzku jednym pohybom, alebo sa za pohyb berie len krok o 1?
kazdopadne by som rad videl riesenie tejto ulohy
To znamená, že tam pohyb začne a ukončí, teda medzi dvomi modrými môžu byť aj biele políčka. môže prejsť ľubovoľnú dĺžku to je zrejmé už.
no neviem teraz co s tym
HAHAHAHAHA
dnes mi nejde... a čo?
Pre m = 2 to plati.
Teraz predpokladajme, ze to plati pre vsetky cisla az po M, a chceme to dokazat pre M+1.
1. Ak existuje riadok R a stlpec S taky, ze maju dokopy nanajvys 2 modre policka, skrtneme ich. Tym dostaneme sachovnicu MxM na ktorej je prinajhorsom 2*M modrych policok (lebo bolo 2*(M+1) a skrtli sme maximalne 2), cize z indukcneho predpokladu, na tomto zvysku sachovnice existuje ten chceny cyklus modrych policok.
2. Ak ziadna takato dvojica R a S neexistuje, tak tvrdim, ze kazdy riadok a kazdy stlpec obsahuje prave 2 policka.
Dokaz: Bez ujmy na vseobecnosti, povedzme, ze je tam riadok R v ktorom je maximalne 1 modre policko. Potom ale v kazdom stlpci musia byt aspon 2, neratajuc toto jedno (pretoze inak by sme dostali stlpec S taky ze R+S maju max 2 modre policka). Cize na sachovnici je minimalne 2*(pocet stlpcov) + 1 modrych policok, co je ale viac ako 2*(pocet stlpcov) = kolko ich ozaj je.
Cize kazdy riadok (a podobne, kazdy stlpec) ma aspon 2 modre policka. Kedze dokopy ich je 2*(M+1), musi mat kazdy riadok / stlpec PRAVE 2 take.
No, ale teraz proste zacni v lubovolnom modrom policku a napr. zacni v riadku. Je tam prave 1 dalsie modre policko: chod nanho. Teraz v tomto stlpci je tiez prave 1 dalsie modre policko: chod nanho. Teraz v tomto riadku ... a tak dalej. Modrych policok je konecny pocet, a ty v kazdom kroku mozes pokracovat, takze eventuelne skocis na nejake, na ktorom si uz bola. Tadaaa, mas cyklus.
Je mozne ze to ide ovela jednoduchsie.. a ospravedlnujem sa, ze vysvetlujem ako trt, nikdy mi to moc neslo.
@qwer28 @piter09 pripadne ma skuste skontrolovat, ak sa vam chce a nie je to az take nezrozumitelne