57-я Международная Математическая OлимпиадаГонконг, 2016 год

Найдите все положительные целые $n$, для которых в каждую клетку таблицы $n \times n$ можно записать ровно одну из букв $I$, $M$ или $O$ так, что:
• в каждой строке и в каждом столбце ровно треть составляют буквы $I$, ровно треть составляют буквы $M$, и ровно треть составляют буквы $O$; а также
• на каждой из диагоналей, количество клеток которой кратно трём, ровно треть составляют буквы $I$, ровно треть составляют буквы $M$, и ровно треть составляют буквы $O$.
Примечание: Если строки и столбцы таблицы $n \times n$ занумерованы числами от $1$ до $n$ в обычном порядке, то каждой клетке соответствует пара положительных целых чисел $(i, j)$, где $1 \times i$, $j \times n$. Для $n > 1$ в таблице суммарно есть $4n - 2$ диагоналей двух типов. Любая диагональ первого типа состоит из клеток $(i, j)$, для которых сумма $i + j$ постоянна, а любая диагональ второго типа состоит из клеток $(i, j)$, для которых разность $i - j$ постоянна.

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

Ответ: n делится на 9.

Сначала мы строим n = 9 и, как следствие, каждое число, кратное 9.

ИИИМММООО МММОООИИ

ОООИИИМММ IIIМММООО

МММОООИИ ОООИИМММ IIIМММООО

МММОООИИ ОООИИМММ

Теперь мы докажем 9 | н необходим.

Пусть n = 3k, что делит данную сетку на k2 подблоков (размером 3 × 3 каждый). Мы говорим, что мультимножество квадратов S является чистым, если буквы распределены между ними поровну; обратите внимание, что объединения чистых мультимножеств являются чистыми.

Рассмотрим следующие чистые множества (данные нам в условии задачи): • Все столбцы с индексом 2 (по модулю 3),

• Все строки имеют индекс 2 (по модулю 3) и

• Все 4k − 2 диагоналей, упомянутые в задаче.

Возьмите их профсоюз. Это покрывает центр каждого прямоугольника четыре раза, а каждую вторую ячейку ровно один раз. Мы заключаем, что набор центральных квадратов k2 чист, следовательно, 3 | k2 и так 9 | н, по желанию