čtvercova síť

Anonym Lenemyj17.11.2016 21:04 Nahlásit
Jirka si nakreslil čtvercovou síť s 25 čtverečky, viz obrázek. Poté chtěl každý čtvereček
vybarvit tak, aby stejně vybarvené čtverečky neměly společný žádný vrchol.
Kolik nejméně barev musel Jirka použít?

Odpovědi

Přidat odpověď ▾

Diskuze

Anonym Lafijyw20.11.2016 11:08 Nahlásit
4 barvy. Hlavní problém je u čtverečků, které mají kolem sebe 8 dalších. Těch osm nelze obarvit méně než třemi barvami, aniž by došlo k situaci, kdy dva čtverečky stejné barvy mají shodný vrchol. Pokud si označím čtverečky od prostředního horního ve směru hodinových ručiček A až H. Použiji barvu č. 1 na střed a barvu č. 2 na čtvereček A, pak stejnou barvu dle zadání mohou mít už jen čtverečky D a F a nebo čtvereček E. Řešení jsou v zásadě jen dvě: barva č. 2 pro ADF, barva č. 3 pro BEH a barva č. 4 pro CG. Ve druhém řešení: barva č. 2 pro AE, barva č. 3 pro CG a barva č. 4 pro BDFH. Zbytek už lze použitými čtyřmi barvami obarvit obdobně.
Přidat komentář do diskuze ▾