6-я Международная Жаутыковская олимпиада, 2010 год

Прямоугольник, образованный линиями клетчатой бумаги, разбивается на фигурки трех видов: равнобедренные прямоугольные треугольники с основанием в две клетки квадраты из одной клетки , и параллелограммы , ограниченные двумя сторонами и двумя диагоналями клеток (фигурки могут быть ориентированы произвольным образом). Докажите, что в любом разбиении количество фигурок третьего вида четно.

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

Отметим некоторую зависимость квадратов и параллелограммов.

1)

Возьмём любую строку из $m$ ячеек, в угловой квадрат может поместиться либо квадрат полностью, либо диагональ проведённая из левого верхнего угла(то есть это либо сторона треугольника либо сторона параллелограмма по условию).

Для удобства примем квадрат за $0$ диагональ вида $«\»$ как $1$ и $«/»$ как $2$ , тогда $11, \ 22$ это есть параллелограммы.

Строка $m$ как уже ранее было описано может начинаться одним из четырёх вариантов, это $01, \ 11, \ 12,\ 00$ и оканчиваться $20, \ 12, \ 00, \ 22$ то есть всего $16$ вариантов.

Рассмотрим случай когда строка имеет вид $01.....20$ отметим что перед $0$ может стоять только $2$ а после $1$ иначе получим не полное замощение, так же перед $2$ только $1,2$ после $0,1,2$ и перед $1$ только $0,1,2$ после $1,2$ откуда следует что случаи $010,020$ невозможны.

Если в $01.....20$ расстояние между началом и концом имеет четное количество ячеек то заполним ее полностью $1$ тогда мы получим четное количество параллелограммов, разбив по парам и меняя $1$ на $2$ (не обязательно все) очевидно будет получать по прежнем четное количество параллелограммов, значит при нечётном количестве ячеек получаем нечетное количество параллелограммов.

В случае если на определённом промежутке между $01$ и $20$ будет находится $0$ выделяем начало $01$ и $0$ в промежутке и приходим к аналогичному случаю что и описывалось ранее.

Применяя те же рассуждения к остальным $15$ случаям, приходим к необходимому и достаточному правилу заполнения прямоугольника

1.

Если $m$ четное и в ней четное количество квадратов, то в ней находится четное количество параллелограммов (в том числе и $0$).

2.

Если $m$ так же четное но в ней нечётное количество квадратов, то в ней находится нечётное количество параллелограммов.

3.

Если $m$ нечётное и в ней четное количество квадратов , то в ней находится нечётное количество параллелограммов

4.

Если $m$ нечётное и в ней нечётное количество квадратов, то в ней находится четное количество параллелограммов.

2)

Применяя это так же к столбцам и суммируя количество параллелограммов со строками , получаем общее количество параллелограммов.

Для доказательства требуемой чётности количества рассмотрим

такой набор, пусть имеется прямоугольник из $m$ строк и в каждой строке $n$ ячеек, то есть прямоугольник из $mn$ квадратов.

В $1$ столбце $(1,2,5,7...)$ где в скобках указаны в данном случае произвольным образом номера строк где имеются квадраты то есть в 1-ом столбце и 1-ой строке, 2 строке , 5 строке и т.д. положив общее количество чисел в скобках как $a_{1}$ по $(1)$ пункту получаем что если $m-a_{1}$ четное ,то в этом столбце находится четное количество параллелограммов , аналогично для всех тогда в итоге четность по всем столбцам можно определить , просуммировав все количество , то есть общее количество $mn-(a_{1}+a_{2}+...a_{n})=X$ надо доказать что и по строкам число будет той же четности что и $X$ что верно так, как по строкам получаем $mn-(b_{1}+b_{2}+...b_{m})=X$ где $a_{1}+a_{2}+...a_{n}=b_{1}+...b_{m}$так как просто распределение того же набора чисел в скобках в столбцах но только по строкам.

Откуда суммировав получаем четное число.

Пусть $n,n_2$ - количество клеток в данном прямоугольнике и количество фигурок второго типа, соответственно. Положим $a$, как количество параллелограммов, у которых одна пара оснований лежит на горизонтальной линии клетчатой бумаги. $b$, как все остальные параллелограммы. Поделим каждую клетку на 4 равных прямоугольных треугольника и рассмотрим следующие их чёрнобелые раскраски.

Из первой раскраски подсчётом черных элементов по модулю 2 несложно получить, что $a+n_2\equiv n\pmod2$. Из второй $b+n_2\equiv n\pmod2$. Поэтому $a\equiv b\pmod2$, откуда мгновенно следует требуемое.