Задачи на чётность и инвариант

Решение

Число, кратное 6, может образовать подходящую пару только с другим кратным 6. Иначе их сумма не будет делиться на 6.

Посчитаем такие числа: 6, 12, …, 798. Поскольку $800 = 133 \cdot 6 + 2$, их ровно 133.

Но 133 — нечётное число. Разбить эти числа на пары невозможно: хотя бы одно останется без пары.

Источник задачи: Всероссийская олимпиада школьников по математике, школьный этап, 2016/17 учебный год, 10 класс, задача 2 — официальный архив ВсОШ, vos.olimpiada.ru

Решение

Поместим квадрат на координатную плоскость. Кузнечики сидят в точках $(0, 0)$, $(1, 0)$, $(0, 1)$, а вершина $(1, 1)$ свободна.

Если кузнечик прыгает из точки $(a, b)$ через точку $(c, d)$, он попадает в точку $(2c - a,\ 2d - b)$: точка $(c, d)$ должна быть серединой отрезка между прежним и новым положением. Все исходные координаты целые, и после каждого прыжка они снова будут целыми.

При этом первая координата меняется на $2(c - a)$, а вторая — на $2(d - b)$. Обе прибавки чётные. Значит, чётность каждой координаты каждого кузнечика сохраняется.

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

Источник задачи: карточка №79240 в архиве МЦНМО problems.ru — этот архив указан организаторами в официальном сборнике ММО 2008 года (страница 50 PDF). В карточке приведены условие, решение и атрибуция: Ю. И. Ионин, 36-я Московская математическая олимпиада, 1973 год, 8 класс, первый тур, задача 5

Решение

Обойдём круг по часовой стрелке. Каждую найденную разность запишем со знаком плюс, если большее число стоит перед меньшим, и со знаком минус, если после него. Тогда каждая записанная величина равна числу в текущей позиции минус число в следующей.

Сумма этих 11 величин равна нулю: каждое исходное число один раз прибавляется и один раз вычитается.

Но среди разностей семь нечётных: четыре единицы и три тройки. Знак числа не меняет его чётность. Сумма семи нечётных чисел и четырёх чётных должна быть нечётной, а ноль чётен. Получили противоречие.

Источник задачи: официальное условие и решение задачи 9.5, ВсОШ, региональный этап, 2009/10 учебный год, 9 класс, второй день, автор Р. Женодаров — в объяснении выше сохранён официальный ход; сокращение суммы и вывод о чётности пояснены подробнее

Решение

Пусть первоначально в вершинах семнадцатиугольника записаны числа: $a_1, a_2, \ldots, a_{17}$ (нумерация — по часовой стрелке). Тогда после указанной замены в вершинах будут записаны числа: $a_2 - a_3,\ a_3 - a_4,\ \ldots,\ a_{16} - a_{17},\ a_{17} - a_1,\ a_1 - a_2$.

Заметим, что сумма полученных семнадцати чисел равна 0. Следовательно, хотя бы одно из этих чисел — чётное. Значит, их произведение также чётное.

Источник задачи: ВсОШ, муниципальный этап в Москве, 2017/18 учебный год, 11 класс, задача 4 — условие и официальное решение, №11.4. Решение приведено по официальному разбору