Задание №149668: Задание 9.7

9.7. Пусть n — нечётное натуральное число. Дана таблица n × n. Расстоянием между двумя
клетками таблицы назовём наименьшее число шагов, за которое можно добраться от одной
клетки до другой, переходя каждый раз в соседнюю по стороне клетку (так, расстояние
между клетками, соседними по стороне, равно 1). R клеток таблицы окрашены в красный
цвет, а другие B клеток — в синий. Известно, что любая прямая, соединяющая центры
красной и синей клеток, не параллельна ни одной из диагоналей таблицы. Кроме того,
√
расстояние между любыми красной и синей клетками не равно n. Докажите, что R +
√
+ B ⩽ n.
Решение. Занумеруем строки сверху вниз, а столбцы слева направо числами от 1 до n;
каждую клетку будем обозначать как (r,c), где r — номер её строки, а c — номер её столбца.
Запишем в каждую клетку (r,c) остатки u и v от деления чисел r + c и r − c на n.
Предположим, что в клетках (r ,c ) и (r ,c ) записана одна и та же (упорядоченная)
1 1 2 2
пара остатков. Это значит, что r +c ≡ r +c (mod n) и r −c ≡ r −c (mod n). Скла-
1 1 2 2 1 1 2 2
дывая и вычитая эти два сравнения, получаем 2r ≡ 2r (mod n) и 2c ≡ 2c (mod n), а
1 2 1 2
поскольку n нечётно, то r ≡ r (mod n) и c ≡ c (mod n), то есть r = c и r = c .
1 2 1 2 1 1 2 2
Значит, в любых двух различных клетках написаны разные пары остатков.
Покажем теперь, что если в красной клетке (rr,cr) написаны остатки ur,vr, а в синей
клетке (r
b
,c
b
) — остатки u
b
,v
b
, то ur ̸= u
b
и vr ̸= v
b
. Предположим, что ur = u
b
. Числа
rr + cr и r
b
+ c
b
отличаются меньше, чем на 2n; поскольку они дают одинаковые остат-
ки при делении на n, они либо равны, либо отличаются на n. В первом случае прямая,
соединяющая центры этих клеток, параллельна диагонали таблицы, что невозможно по
условию. Во втором же, если, скажем, rr + cr = r
b
+ c
b
+ n, то (rr − r
b
) + (cr − c
b
) = n.
Оба слагаемых меньше n, поэтому оба они положительны. Тогда это равенство означает,
что расстояние между нашими клетками равно n, что также запрещено условием. Случай
vr = v
b
разбирается аналогично.

LII Всероссийская математическая олимпиада школьников

Пусть в красных клетках встречаются k остатков на первых местах и ℓ остатков на
вторых; поскольку каждая пара остатков задаёт клетку однозначно, получаем

(cid:18) (cid:19)2
k + ℓ
R ⩽ kℓ ⩽ .

Ответ: Пусть n — нечётное натуральное число. Дана таблица n × n. Расстоянием между двумя