|
|
 |
Условие
Имеется двести шариков ста цветов, по два шарика каждого цвета. Фокусник разложил их произвольным образом в сто коробочек, по два шарика в коробочку, где что лежит – игрок не знает. За ход игрок указывает на любые две коробочки, после чего фокусник незаметно для игрока выбирает по шарику из этих коробочек и меняет их местами. Если в какой-то момент в каждой коробочке будут лежать разноцветные шарики, ведущий выдаёт игроку приз. Может ли игрок действовать так, чтобы гарантированно получить приз, как бы фокусник ни менял шарики?Решение 1
Разобьём коробочки на $50$ пар произвольным образом и занумеруем эти пары натуральными числами от $1$ до $50$. Будем говорить, что мы применяем операцию к паре, если указываем на две коробочки из этой пары. Назовём пару плохой, если хотя бы в одной из её коробочек лежат шарики одного цвета, и хорошей в противном случае.Заметим, что если применить операцию к плохой паре, то она обязательно станет хорошей. Действительно, если в одной из коробочек лежат два шарика одного цвета, то в другой коробочке нет шариков этого цвета (так как каждого цвета всего два шарика). Поэтому после обмена в обеих коробочках окажутся шарики разных цветов. Докажем следующую лемму.
Лемма. Для любого натурального $n \leqslant 50$ существует конечная последовательность операций, применяемых к первым $n$ парам, при которой гарантированно найдётся момент, когда все эти $n$ пар будут хорошими.
Доказательство. Будем использовать индукцию по $n$. При $n=1$ достаточно применить одну операцию к первой паре.
Пусть утверждение верно для $n-1$. Докажем его для $n$. Сначала применим последовательность операций, соответствующую $n-1$ парам. Затем применим операцию к $n$-й паре, после чего снова применим ту же последовательность операций к первым $n-1$ парам.
Покажем, что в некоторый момент все первые $n$ пар будут хорошими. Действительно, после первого применения последовательности первые $n-1$ пар в некоторый момент становятся хорошими. Если в этот момент $n$-я пара также хорошая, то требуемое выполнено. Иначе применённая к ней операция делает её хорошей. После этого повторное применение последовательности к первым $n-1$ парам вновь в некоторый момент делает их все хорошими, при этом $n$-я пара уже остаётся хорошей. Переход доказан.
Итак, по лемме при $n=50$ существует последовательность операций, при
которой в некоторый момент все $50$ пар будут хорошими, то есть в каждой
коробочке будут лежать шарики разных цветов, что и требовалось.
Решение 2
Пусть всего цветов $n\geqslant2$, и есть $n$ коробок и $2n$ шариков (по 2 каждого цвета), разложенные в эти коробки. Докажем утверждение индукцией по $n$ — что существует алгоритм фиксированной конечной длины, зависящей только от $n$, который гарантирует игроку приз.
Когда коробочек две, в них обеих либо разноцветные шарики (и задача уже решена), или в обеих одноцветные, и тогда, указав на них, мы за один ход получаем требуемое.
Докажем переход индукции (когда коробочек больше двух). Отложим одну коробочку, сделаем индукционную проверку остальных (это возможно за конечное время по предположению индукции). Если в отложенной коробочке были разноцветные шарики, скажем красный и синий, отождествим мысленно красный и синий цвета, тогда для оставшихся коробок по индукции был момент, когда во всех них шарики разноцветные, в этот момент и у нас везде разноцветные шарики. Иначе была отложена «одноцветная» коробочка, тогда после окончания проверки сделаем одну операцию с отложенной коробочкой и какой-то ещё, теперь отложенная точно «разноцветная», и снова по индукции проверим остальные. Общее количество ходов не более чем на 1 больше удвоенного количества ходов для предыдущего значения $n$.
Решение 3
Пусть цветов сколько угодно, но каждого цвета не больше двух шариков, и есть $n$ пар коробок (по два шарика в каждой). Докажем индукцией по $n$, что хватит $2^n - 1$ ходов, чтобы когда-нибудь все коробки стали разноцветными.
Если пара коробок одна, то или до хода, или после обе коробочки разноцветные (так как если есть одноцветная коробочка, в ней лежат все шарики данного цвета, и, поменяв один из них на шарик из другой коробочки, получим везде разные цвета). Хватает одного хода.
Пусть пар $n > 1$. Отложив в сторону одну пару, делаем с оставшимися коробками $2^{n-1} - 1$ ходов, как умеем по предположению индукции. Затем делаем ход в отложенной паре и снова $2^{n-1} - 1$ ходов в остальных парах. В какой-то момент за эти $2^n - 1$ ходов все коробки были разноцветными.
Ответ
Да, может.Замечания
На Турнире городов 2026 года задача предлагалась в следующей формулировке:Имеется двести шариков ста цветов, по два шарика каждого цвета. Ведущий разложил их произвольным образом в сто коробочек, по два шарика в коробочку, где что лежит — игрок не знает. За ход игрок указывает на любые две коробочки, после чего ведущий незаметно для игрока выбирает по шарику из этих коробочек и меняет их местами. Если в какой-то момент в каждой коробочке будут лежать разноцветные шарики, игрок получит приз. Может ли игрок действовать так, чтобы гарантированно получить приз, как бы ведущий ни менял шарики?
