Kameny na šachovnici
Úloha číslo: 3476
Kolika způsoby lze umístit osm kamenů na šachovnici \(4 \times 4\) tak, aby se na šachovnici vyskytovaly čtyři kameny ve stejném řádku nebo stejném sloupci?
Řešení
Označme \(A_i\) ta rozestavení, kdy je obsazeny celý \(i\)-tý řádek pro \(i\in\{1,…,4\}\) a kde je zcela vyplněn \((i-4)\)-tý sloupec pro \(i\in\{5,…,8\}\).
Platí \(|A_i|=\binom{12}{4}=495\). Pro průniky \(A_i \cap A_j\) je třeba rozlišit tři situace: když obsadíme dva řádky, tedy \(i,j\in\{1,…,4\}\), má průnik jen jeden prvek, protože už žádné kameny nezbývají. Stejná úvaha platí i pro dvojici sloupců. Když obsadíme nějaký řádek a také sloupec, zůstane jeden kámen a ten je možné umístit na libovolné ze zbývajících devíti políček.
Průniky tří množin jsou prázdné, na obsazení tří řádků anebo sloupců nemáme dost kamenů.
Celkem \(|\bigcup\limits_{i=1}^8 A_i|=8\binom{12}{4}-2\binom{4}{2}-4^2{\cdot} 9=3\,804\).
Odpověď
Hledaných rozestavení je 3 804.
