Kameny na gobanu II

Úloha číslo: 3764

Na gobanu je položeno několik kamenů tak, že v každém řádku i sloupci je 8, 9 nebo 10 kamenů.

Kolik nejvíce kamenů lze na desce ponechat tak, že aby v každém řádku i sloupci zůstal nejvýše jeden kámen?

Úlohu je obtížné spočítat přesně, proto postačí, určíte-li dolní a horní odhad lišící se o 1.

  • Nápověda

    Kolik lze vytvořit řádků takových, že budou zasahovat do méně sloupců, než je počet těchto řádků? Úvahu pak zobecněte a získáte odhad na deficit z deficitní Hallovy věty.

  • Řešení

    Dolní odhad lze získat s využitím deficitní Hallovy věty: na \(r\) řádcích je alespoň \(8r\) kamenů, zasahujících do \(\lceil\frac8{10}r\rceil\) sloupců. Pro \(r\le 19\) je \(\lceil\frac8{10}r\rceil=r-\lfloor\frac2{10}r\rfloor \ge r-3\).

    Patrně nejde o nejlepší dolní odhad – opírá se o situaci, kdy bychom v každém z 19 řádků použili jen prvních 16 sloupců, ale ve skutečnosti musíme zaplnit i zbylé tři.

    Pro horní odhad je možno nalézt konfiguraci dovolující výběr jen 17 kamenů: V prvních 10 řádcích je obsazeno prvních 8 sloupců; v následujících 9 řádcích rozložíme 10 kamenů do posledních 11 sloupců tak, aby každý sloupec měl 8 nebo 9 kamenů, viz obrázek.

    goban=řešení

    Už jen na prvních 10 řádcích smíme ponechat jen 8 kamenů, což vede na výběr nejvýše 17 kamenů.

  • Odpověď

    Na desce lze vždy ponechat alespoň 16 kamenů a existují situace, kdy nelze ponechat více jak 17 kamenů.

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze