МОШ 2026, 10 класс, задача 3
Имеется двести шариков ста цветов, по два шарика каждого цвета. Фокусник
разложил их произвольным образом в сто коробочек, по два шарика в коробочку, где что
лежит — игрок не знает. За ход игрок указывает на любые две коробочки, после чего фокусник
незаметно для игрока выбирает по шарику из этих коробочек и меняет их местами. Если в какойто момент в каждой коробочке будут лежать разноцветные шарики, ведущий выдаёт игроку
приз. Может ли игрок действовать так, чтобы гарантированно получить приз, как бы фокусник
ни менял шарики?
Ответ: да, может.
Решение. Разобьём все коробочки на пар подряд идущих и пронумеруем эти пары слева направо. Будем говорить, что применяем операцию для одной из этих пар, если мы указываем на две коробочки этой пары. Назовём пару плохой, если хотя бы в одной из коробочек данной пары лежат одноцветные шарики, иначе назовём пару хорошей. Заметим, что если мы указываем на плохую пару, то она обязательно становится хорошей. Докажем следующую лемму.
Лемма. Для любого натурального существует последовательность операций к первым парам, при которой гарантированно существует момент, когда все эти пар становятся хорошими.
Доказательство. Будем использовать индукцию по . Для просто применяем одну операцию к первой паре.
Докажем переход. Пусть утверждение леммы выполянется для , докажем его для . Применим последовательность операций из предположения индукции для первых пар. После этого применим операцию к -ой паре, а потом еще раз повторим последовательность операций для первых пар. Таким образом, независимо от того, была ли -ая пара изначально плохой или хорошей, найдётся момент, когда все первые пар будут хорошими. Переход доказан.
По лемме для у нас существует последовательность операций, при которой все пар в какой-то момент гарантированно станут хорошими, что и требовалось.