úloha na důkazy
Dobrý den,
chtěl bych Vás znovu poprosit o pomoc, vůbec si nevím rady s touto úlohou:
V rovině je dán konečný počet přímek a ty ji dělí na části. Dokažte, že tyto části je možno vybarvit dvěma barvami tak, aby každá část byla byla vybarvena celá jednou barvou a aby žádné dvě sousední části (tj. části oddělené úsečkou, polopřímkou nebo přímkou) nebyly vybarveny jednou barvou.
Předem Vám všem moc děkuji.
Honza
chtěl bych Vás znovu poprosit o pomoc, vůbec si nevím rady s touto úlohou:
V rovině je dán konečný počet přímek a ty ji dělí na části. Dokažte, že tyto části je možno vybarvit dvěma barvami tak, aby každá část byla byla vybarvena celá jednou barvou a aby žádné dvě sousední části (tj. části oddělené úsečkou, polopřímkou nebo přímkou) nebyly vybarveny jednou barvou.
Předem Vám všem moc děkuji.
Honza
Odpovědi
Diskuze
1: Začnu první přímkou a každou polorovinu vybarvím jinou barvou - podmínka je zjevně splněna (pro N=1)
2: Přikreslím další přímku do obrazce s N přímkami, který "je správný" (splňuje podmínku). V jedné polorovině takto rozděleného obrazce barvy nechám být, ve druhé polorovině je v každé části "invertuju", tj. vzájemně zaměním první a druhou. Obrazec bude zase "správný" protože:
2a: Části, kterými nová čára neprochází, splňovaly podmínku už předtím a budou ji splňovat i nadále, protože nezáleží na tom, která barva je která - jen se v té polorovině vyměnily, ale vztah vzájemné odlišnosti se nezměnil.
2b: Části, které nová přímka rozdělila na dvě nové, budou také správné, protože podle popsaného postupu bude mít každá z těch dvou nových částí jinou barvu (jedna tu původní, druhá tu vyměněnou).
2c: Žádné jiné části v obrazci nejsou, takže jsou po provedení toho kroku správné všechny (pro N+1)
Čímž je nejen důkaz proveden, ale je nalezen i postup, jak obarvení provést. Což nemusí platit vždy - někdy důkaz, že něco jde, ještě neznamená, že vím jak :-).