Kameny na gobanu

Úloha číslo: 3762

Na gobanu (desce \(18 \times 18\) polí pro hraní hry go) je položeno několik kamenů tak, že v každém řádku i sloupci je stejný počet kamenů. (Kameny se ve hře go pokládají na průsečiky, tedy na vrcholy mřížky \(19 \times 19\).)

Lze za této situace odebrat z desky několik kamenů tak, že v každém řádku i sloupci zůstane právě jeden kámen (aniž bychom zbylými jakkoli pohybovali)?

  • Řešení

    Vytvoříme bipartitní graf s oběma částmi \(R\) a \(S\) velikosti 19 tak, že vedeme hranu mezi vrcholy \(r_i\) a \(s_j\), pokud je na průsečíku \(r\)-tého řádku a \(s\)-tého sloupce položen kámen.

    Graf je bipartitní regulární, má tedy párování a to odpovídá pozici zbylých kamenů.

  • Odpověď

    Ano, vždy lze ponechat vhodnou skupinu kamenů.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze