Částečné uspořádání

Úloha číslo: 3664

Mějme šachovnici \(4\times 4\) a v jejím levém dolním rohu postaveného jezdce. Na políčkách šachovnice zavedeme relaci \(\preceq\), kde \(a \preceq b\) znamená, že políčko \(a\) leží na některé z nejkratších cest jedcem z levého dolního rohu na políčko \(b\).

Kolik má \(\preceq\) maximálních prvků?

  • 2
  • 3
  • 4
  • Řešení

    Prohledáváním do šířky zjistíme, že nejdelší cesty končí v rozích – protilehlý roh ve vzdálenosti 2, zbylé dva rohy ve vzdálenosti 5. Ostatní políčka leží na nejkratších cestách délky 5.

  • Odpověď

    Správná odpověď je b.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze