Математикадан 58-ші халықаралық олимпиада, 2017 жыл, Рио-де-Жанейро

Келесі шарттар орындалатын барлық натурал $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 | н, по желанию