Бихте ли ми помогнали със следната задача:
Клетките на квадрат n x n са оцветени в черен и бял цвят със следното условие: не могат да бъдат в един цвят никои четири клетки, в които се пресичат два реда и два стълба. Колко най-много може да бъде n?
Отг.: n = 4.
Първо ще докажем, че при n ≥ 5 винаги може да намерим два стълба и две колони такива, че четирите клетки, в които те се пресичат са едноцветни.
Нека n ≥ 5. Разглеждаме долния ляв квадрат с размери 5 × 5, който е част от квадрата n × n.
Най-лявата колона на квадрата 5 × 5 съдържа 5 клетки и следователно, според принципа на Дирихле, поне три от клетките са оцветени в един и същ цвят. Без ограничение на общността може да приемем, че трите едноцветни клетки са черни.
Разглеждаме само тези три реда на квадрата 5 × 5, чиято най-лява клетка е черна (може да имаме повече от три реда, чиято най-лява клетка е черна, но избираме само три). Ще наричаме тези редове „черни”.
Разглеждаме клетките, в които трите черни реда пресичат всяка от останалите четири колони (без най-лявата) на квадрата 5 × 5. Ще наричаме тези клетки „пресечни”. Ако има колона, която съдържа поне две черни пресечни клетки, то тази колона, първата колона и двата черни реда, които съдържат двете черни пресечни клетки ще се пресичат в четири черни клетки.
Ч . . . Ч . . .
. . . . . . . . .
Ч . . . Ч . . .
Нека няма колона (освен най-лявата), която съдържа две черни пресечни клетки. Тогава има четири варианта за оцветяване на пресечните клетки в една колона:
Б Б Б Ч
Б Б Ч Б
Б Ч Б Б
Нека има колона, която съдържа три бели пресечни клетки. Ще наричаме тази колона „бяла”. Всяка от останалите три колони съдържа поне по две бели пресечни клетки (няма колона, която съдържа две черни пресечни клетки). Избираме една от останалите три колони и тогава избраната колона, бялата колона и двата черни реда, които съдържат двете бели пресечни клетки от избраната колона ще се пресичат в четири бели клетки.
Ч . . . Б . . . Б . . .
. . . . Б . . . . . . .
Ч . . . Б . . . Б . . .
Нека няма колона, която съдържа три бели пресечни клетки. Тогава пресечните клетки в четирите колони (без най-лявата) могат да бъдат оцветени по три различни начина:
Б Б Ч
Б Ч Б
Ч Б Б
Следователно, има две колони, в които пресечните клетки са оцветени по един и същ начин. Ще наричаме тези две колони „еднакви”. Двете еднакви колони и двата черни реда, които съдържат двойките бели пресечни клетки от еднаквите колони ще се пресичат в четири бели клетки.
Ч . . . Б . . . Б . . .
Ч . . . Б . . . Б . . .
Сега трябва да конструираме пример за квадрат 4 × 4, в който няма два стълба и две колони такива, че четирите клетки, в които те се пресичат да са едноцветни.
Б Ч Б Ч
Ч Б Ч Б
Б Б Ч Ч
Ч Ч Б Б
P.S. Хубава, нелека състезателна задача.