Úloha 5.u3: Buchty (3 b)

Zadáno v čísle 23.5.

Řešeno v čísle 23.7.

Zadání

Komárodlak má obdélníkový pekáč s $m \times n$ buchtami, každá je buď maková, nebo tvarohová. Komárodlak si všimnul, že v každém řádku i v každém sloupci je lichý počet makových buchet.

  1. Dokažte, že buď jsou $m$ i $n$ obě sudá, nebo obě lichá.

  2. Kolik existuje pro pekáč o daných rozměrech rozmístění buchet takových, že splňují podmínku v zadání?

Řešení

Nejprve si uvědomme, že součet lichého počtu lichých čísel je lichý, zatímco sudého počtu lichých čísel sudý (dokazatelné např. indukcí přes počet sčítanců). S uvážením lichého počtu makových buchet v každém řádku i každém sloupci lze pak celkový počet makových buchet na pekáči vypočítat buďto jejich vysčítáním přes řádky (součet $m$ lichých čísel) nebo přes sloupce (součet $n$ lichých čísel). Mají-li se tyto dva součty rovnat, dle předchozího musí být $m$ i $n$ obě sudá nebo obě lichá.

Pro druhou část nejprve libovolně vyplňme tabulku vyjma posledního sloupce a řádku. Zbývající nevyplněné políčko v každém řádku, resp. sloupci, lze zjevně vždy jednoznačně doplnit vhodnou buchtou na splnění podmínky lichého počtu makových buchet. Totéž platí i pro zbylé rohové políčko, neboť počty makových buchet doplněných do posledního sloupce a do posledního řádku mají stejnou paritu (důkaz podobně jako v první části, jen s uvážením, že v některých řádcích a sloupcích redukované tabulky mohl být makových buchet sudý počet). Počet vyhovujících kombinací je tedy roven počtu možných obarvení tabulky $(m-1)\times (n-1)$, což je $2^{(m-1)(n-1)}$.

Evžen