Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 18. 12. 2018 23:02
Diskretní matematika, grafy
Dobrý den, chtěl bych se zeptat na jednu úlohy z diskrétní matematiky, zadání je následovné: V šachovnici mxm je 2m políček obarveno modře. Na jedno z políček umístníme věž. Věží budeme pohybovat z modrého políčka opět na modré políčko, přičemž se budeme chtít pohybovat střídavě vodorovně a svisle. Dokažte, že je možné věž umístnit tak, že když s ní budeme vhodně pohybovat, vždy budeme mít možnost udělat další tah. Nevím si s touhle úlohou rady. Dekuji.
Offline
#2 18. 12. 2018 23:54
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4246
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Diskretní matematika, grafy
Jaký je zdroj dotazu?
Jde to zobecnit na obdélník m x n, přičemž je obarveno m+n polí (m>1,n>1) . Můžeš zkusit vyřešit pro m=2 a obecné n, pak rozšířit pro všechna m.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#5 29. 12. 2018 21:39
- check_drummer
- Příspěvky: 4894
- Reputace: 105
Re: Diskretní matematika, grafy
↑ Torme:
Ahoj, nevím jestli název "grafy" v názvu tématu má evokovat použití grafů, ale pokusil jsem se o to.
Dokažme indukcí podle m, rozlišme následující případy (lze ukázat, že jiné možnosti nenastanou):
1) Alespoň jeden řádek a alespoň jeden sloupec obsahují (každý zvlášť) 1 nebo méně modrých polí. Pak tento řádek a sloupec odstraníme a na zbylou šachovnici lze použít indukční předpoklad.
2) Každý řádek obsahuje právě 2 modrá pole. (Případ, kdy každý sloupec obsahuje právě 2 modrá pole lze vyřešit stejně.) Sestrojíme graf, jehož vrcholy jsou sloupce šachovnice a i,j jsou spojeny hranou, pokud existuje řádek, jehož pole v i-tém i j-tém sloupci mají modrou barvu. Lze ukázat, že takovýá graf má m vrcholů a m hran (díky první větě bodu 2)), z čehož již lze ukázat, že plyne, že musí obsahovat cyklus, což indukuje onu nekonečnou cestu věží.
"Máte úhel beta." "No to nemám."
Offline