Республиканская олимпиада по математике, 2026 год, 9 класс

Бүтін $n\ge 4$ саны берілген. Кез келген екі $(a,b)$ және $(c,d)$ қара ұяшық үшін $|a-c|+|b-d|\ne n-1$ шарты орындалатындай өлшемі $n \times n$ болатын тақтада ең көп неше ұяшықты қара түске бояуға болады? (Мұнда $(x,y)$ арқылы $x$-ші қатар мен $y$-ші бағанның қиылысындағы ұяшық белгіленген. Тақтаның сол жақ төменгі бұрышындағы ұяшық бірінші қатар мен бірінші бағанның қиылысында орналасқан). ( Абдирасулов А. )

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

Пусть $n$ это размер доски. Условие $|a-c| + |b-d| \ne n-1$ означает что нельзя брать клетки на расстоянии ровно $n-1$.

Случай 1 когда $n$ четное. Расстояние $n-1$ в этом случае нечетное. Если покрасить доску в шахматном порядке то расстояние между любыми двумя черными клетками всегда четное. Значит условие $d = n-1$ никогда не выполнится. Максимум клеток в шахматной раскраске это $n^2 / 2$.

Случай 2 когда $n$ нечетное. Расстояние $n-1$ теперь четное. Обычная шахматная раскраска не подходит. Разобьем доску на пары клеток $(x, y)$ и $(x', y')$ на расстоянии $n-1$. Из каждой такой пары можно взять максимум одну клетку.

Для нечетного $n \ge 5$ можно построить пример внутри квадрата $(n-1) \times (n-1)$ в центре доски. Если покрасить его в шахматном порядке то максимальное расстояние между черными клетками будет $n-2$. Это меньше чем $n-1$ поэтому условие выполнено.

Количество закрашенных клеток в таком квадрате $(n-1) \times (n-1)$ будет равно $(n-1)^2 / 2$. Это и есть максимальный ответ для нечетного $n$. Например для $n=5$ ответ 8 а для $n=7$ ответ 18.

Ответ: $n^2 / 2$ для четного $n$ и $(n-1)^2 / 2$ для нечетного $n$