Условие
В каждой клетке доски размером 5×5 стоит крестик или нолик, причём никакие три крестика не стоят подряд ни по горизонтали, ни по вертикали, ни по диагонали. Какое наибольшее количество крестиков может быть на доске?
Решение
Пример расстановки 16 крестиков в соответствии с условием см. на рис. слева.
Оценка. Разобьём доску на центральную клетку и 8 прямоугольников размером 3×1 (рис. справа). В каждом прямоугольнике должен стоять хотя бы один нолик. Следовательно, ноликов на доске не менее восьми. Если и в центральной клетке стоит нолик, то крестиков – не больше, чем 16, и задача решена. Осталось рассмотреть случай, когда в центральной клетке стоит крестик.
Первый способ. Рассмотрим все клетки больших диагоналей (см. рис.).
Каждая пара соседних закрашенных клеток вместе с центральной клеткой образует тройку, в которой должен стоять хотя бы один нолик. Значит, в восьми закрашенных клетках стоят хотя бы четыре нолика. Следовательно, в каждом из прямоугольников размером 3×1, расположенных на краю доски, должно стоять хотя бы по одному нолику. Итого, уже не меньше, чем 8 ноликов. Но если в остальных клетках стоят крестики, то три крестика "в ряд" образуют крестики, соседние с центральным по горизонтали и по вертикали, что противоречит условию. Значит, ноликов не меньше девяти.
Второй способ. Рассмотрим 8 пар клеток, выделенных на рис. слева. В одной из клеток каждой пары должен стоять хотя бы один нолик, поэтому ноликов не меньше восьми.
Предположим, что в каждой выделенной паре клеток ровно один нолик и вне этих пар ноликов нет. Тогда в остальных клетках стоят крестики (рис. в центре). Рассмотрим четыре тройки клеток, выделенные на этом рисунке. В каждой из них уже стоит по два крестика, значит, между ними стоят нолики. Снова рассмотрим четыре из восьми ранее выделенных пар клеток (рис. справа). Мы уже выяснили, что в каждой паре ровно одна клетка с ноликом, значит, в другой клетке – крестик. Если поставить эти крестики, то в центре доски окажутся тройки крестиков, идущих подряд. Следовательно, и эта расстановка не удовлетворяет условию.
Ответ
16 крестиков.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Московская устная олимпиада для 6-7 классов |
|
год/номер |
|
Номер |
15 (2017 год) |
|
Дата |
2017-03-19 |
|
класс |
|
Класс |
6 класс |
|
задача |
|
Номер |
6.8 |
|
|
|
|
олимпиада |
|
Название |
Московская устная олимпиада для 6-7 классов |
|
год/номер |
|
Номер |
15 (2017 год) |
|
Дата |
2017-03-19 |
|
класс |
|
Класс |
7 класс |
|
задача |
|
Номер |
7.8 |
