Леонард Эйлер атындағы олимпиада,2010-2011 оқу жылы, қорытынды кезеңнің 2-ші туры

$9 \times 9$ тор көзді тақтаға ең көп дегенде бір бірін жемейтіндей(сондай ақ, өзінің түсімен бірдей пешканы) қанша қара және ақ пешка қоюға (пешка, өзінің түсіне тәуелсіз кез келген шаршыға қоюға болады) болады? Ақ пешка нөмері үлкен көршіес екі диоганальді жейді, ал қара пешка нөмері төмен екі көршілес диоганальді жейді (сур. қараңыз).

( А. Антропов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Ответ. 56.
Решение. Пример с 56 пешками показан на рисунке. Оценка. Заметим, что в каждом прямоугольнике из трех строк и двух столбцов стоит не более 4 пешек. Действительно, если в нем стоит хотя бы 5, то тогда на одном из цветов заняты все три клетки и пешка из центральной строки бьет одну из двух оставшихся. Следовательно, в любом прямоугольнике из 9 строк и 8 столбцов стоит не более 48 пешек (так как его можно разбить на 12 прямоугольников $3\times 2$). Допустим, нам удалось поставить 57 пешек. Тогда в девятом столбце должно стоять хотя бы 9 пешек, т.е. ровно 9. Но тогда в восьмом столбце стоит не более 2 пешек (так иначе нашлась бы пешка, стоящая не в первой и не в последней строке, которая бы била какую-то пешку из девятого столбца). Но тогда в восьмом и девятом столбцах вместе не более 11 пешек, а во 2-7 столбцах — не более 36 пешек (их можно разбить на 9 прямоугольников $3 \times 2$). Получается, что в первом столбце должно быть 10 пешек — противоречие.