Задача 65099

Темы:    [ Шахматные доски и шахматные фигуры ] [ Примеры и контрпримеры. Конструкции ] [ Доказательство от противного ]

Сложность: 4 Классы: 8,9

Условие

Автор: Антропов А.

Какое наибольшее количество белых и чёрных пешек можно расставить на клетчатой доске 9×9 (пешку, независимо от её цвета, можно ставить на любую клетку доски) так, чтобы никакая из них не била никакую другую (в том числе и своего цвета)? Белая пешка бьёт две соседние по диагонали клетки на соседней горизонтали с бóльшим номером, а чёрная – две соседние по диагонали клетки на соседней горизонтали с меньшим номером (см. рисунок).

Решение

  Пример с 56 пешками показан на рисунке.

  Оценка. Пусть в прямоугольнике из трёх строк и двух столбцов стоит стоит хотя бы пять пешек. Тогда на трёх клетках одного из цветов стоят три пешки, и пешка из центральной строки бьёт одну из двух оставшихся. Следовательно, такое невозможно, и в любом прямоугольнике 3×2 стоит не более 4 пешек.
  Допустим, нам удалось поставить 57 пешек. В первых 8 столбцах (их можно разбить на 12 прямоугольников 3×2) стоит не более 48 пешек, а в девятом столбце, следовательно, – 9 пешек. Но тогда в восьмом столбце стоит не более двух пешек (иначе нашлась бы пешка, стоящая не в первой и не в последней строке, которая бы била какую-то пешку из девятого столбца). Итак, в восьмом и девятом столбцах вместе не более 11 пешек, в столбцах со второго по седьмой – не более 36 пешек (их можно разбить на 9 прямоугольников 3×2), а в первом – не более девяти. Итого, не более
9 + 36 + 11 = 56  пешек. Противоречие.

Ответ

56.

Источники и прецеденты использования

олимпиада
Название	Олимпиада имени Леонарда Эйлера (для 8 классов)
тур
Номер	3 (2011 год)
тур
задача
Номер	8