Zadanie
Frázu „nájsť obdĺžnik“ v pôvodnej verzii zadania sme nahradili jasnejším vysvetlením.
Prečo dokázal byť Istanbul takým vojensky významným bodom? Bo spor.
Bospor a Dardanely sa striedali v ofarbovaní šachovnice veľkosti \(7 \times 3\). Bospor ofarboval políčka červenou a Dardanely modrou. Dokážte, že po ofarbení všetkých políčok vieme nájsť také \(4\) políčka rovnakej farby, ktoré tvoria obdĺžnik (teda ich stredy sú vrcholy pravouhlého rovnobežníka) so stranami rovnobežnými s mriežkou šachovnice.
Skúsme nájsť tabuľku \(7 \times 3\) takú, že tam nebudú štyri políčka rovnakej farby, ktoré tvoria tvoria obdĺžnik.
Každé z troch políčok stĺpca môže byť ofarbené dvoma rôznymi farbami, a teda existuje \(2^3=8\) možností, ako môžu byť ofarbené jednotlivé stĺpce. V každom takomto ofarbení sú aspoň dve políčka rovnakej farby. Ak by dva zo stĺpcov boli ofarbené rovnako, tak by sa z políčok farby, čo v týchto stĺpcoch prevažuje, dal vytvoriť obdĺžnik. Tým pádom náš hľadaný obdĺžnik musí mať všetky stĺpce rôzne.
Keďže stĺpcov je \(7\) a rôznych ofarbení stĺpca je \(8\), tak z \(8\) rôznych ofarbení stĺpcov využijeme práve \(7\), a teda existuje aspoň jeden stĺpec, pre ktorý platí, že sú všetky jeho políčka ofarbené rovnakou farbou. Označme túto farbu \(F\).
Dokopy existujú \(3\) možné ofarbenia stĺpca, ktoré majú práve dve políčka ofarbené farbou \(F\). Keďže využívame každé ofarbenie okrem jedného práve raz, tak pre aspoň dva zo zvyšných šiestich stĺpcov platí, že dve z ich políčok sú ofarbené farbou \(F\). Keď teda zoberieme stĺpec, ktorý je celý ofarbený farbou \(F\) a jeden z týchto minimálne dvoch stĺpcov, tak políčka s farbou \(F\) určite budú tvoriť obdĺžnik.
Z toho vyplýva, že v tabuľke \(7 \times 3\) bude musieť byť vždy aspoň jeden takýto obdĺžnik zo štvorčekov rovnakej farby. A to dokonca bez ohľadu na to, koľko je ktorej farby na plániku.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.