Věže na šachovnici
Úloha číslo: 3658
Na šachovnici \(8 \times 8\) je 33 věží. Dokažte, že mezi nimi najdeme 5 věží, které se navzájem neohrožují.
Řešení
Věže musejí obsadit alespoň pět řádků, zvolíme pět nejplnějších.
Rozborem případů zjistíme že pátý nejplnější má alespoň jednu věž: \(8+8+8+8+1\), čtvrtý nejplnější alespoň dvě: \(8+8+8+2+2+2+2+1\), třetí alespoň tři: \(8+8+3+3+3+3+3+2\), druhý alespoň čtyři: \(8+4+4+4+4+3+3+3\) a první alespoň pět: \(5+4+4+4+4+4+4+4\).
Z pátého nejplnějšího vybereme libovolnou věž, pak ze čtvrtého nejplnější vybereme věž tak, abychom se vyhnuli sloupci s již vybranou věží, atd. až po nejplnější řádek.