Шаг за шагом
Ошибка.
Попробуйте повторить позже
100 человек пришли на представление в шляпах. Фокусник поменял местами их шляпы. После этого каждую минуту каждый человек
находил свою шляпу и передавал тому, у кого эта шляпа в данный момент находилась, ту шляпу, которая в этот момент была у
него самого. (Если на каком-то шаге у человека 
оказывается шляпа, принадлежащая человеку 
, а у человека 
оказывается шляпа, принадлежащая человеку самому 
, то на следующем шаге у 
оказывается шляпа, принадлежащая 
).
Фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам, но при этом это произошло бы как можно позже. Через сколько минут, самое позднее, это может произойти в первый раз?
Источники:
Подсказка 1
Условие про то, как передвигаются шляпы достаточно сложное, поэтому, чтобы хорошо его понять, нужно самому подвигать шляпы на каком-то количестве человек. Давайте рассмотрим какого-то человека А₀, так как мы сами вводим обозначения, то давайте изначально его шляпа была у А₁. Тогда человека, держащего шляпу А₁, назовём А₂ и так далее. В какой момент цепочка А₀- А₁-А₂ остановится? Обязательно поймите, почему это точно произойдёт.
Подсказка 2
Цепочка остановится в момент, когда шляпа какого-то Аₙ₋₁ окажется у Aₖ, которого мы уже записывала в нее. Тогда чему может быть равно k?
Подсказка 3
Через минуту шляпа А₀ окажется у того, кто держал раньше шляпу А₁, то есть у А₂, шляпа А₁ будет у А₃. Тогда можно сделать вывод, что для каждого k шляпа Aₖ через минуту окажется у Aₖ₊₂.
Подсказка 4
Через m минут шляпа Aₖ будет находиться у человека с номером k + 2ᵐ. Тогда при каком количестве человек шляпа сможет вернутся к исходному владельцу? Воспользуйтесь тем, что Aₖ = Аₙ₊ₖ.
Подсказка 5
Шляпа может вернуться к исходном владельцу только в случае, если количество человек в цикле является степенью двойки! По условию фокусник изначально раздал шляпы так, чтобы в итоге они вернулись к своим настоящим хозяевам. Это значит, что все 100 человек разобьются на некоторое количество циклов (цикл из одного человека тоже может быть). Но мы уже получили условие на длины циклов. Тогда какая может быть наибольшая, учитывая ограничение в 100 человек?
Рассмотрим некоторого человека, назовём его 
. Пусть его шляпа изначально оказалась у какого-то 
, шляпа 
оказалась у 
, и
т.д. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то 
его шляпа окажется у какого-то
, который был уже нами пронумерован ранее. При этом это может быть только 
, т.к. про всех остальных мы уже знаем, откуда
взялись находящиеся у них шляпы.
Значит, шляпа 
в начале представления оказалась у 
и мы получили так называемый цикл из 
человек. Для удобства будем
считать, что 
и т.д., чтобы иметь возможность говорить, что каждый человек с номером 
передал свою шляпу
человеку с номером 
(то есть, мы на самом деле нумеруем людей остатками (классами вычетов) при делении на 
).
После того, как джентльмены передадут свои шляпы, шляпа 
окажется у того, у кого раньше была шляпа 
, то есть у 
, шляпа
окажется у 
и т.д. Шляпа каждого 
окажется у 
. После второй передачи шляпа каждого 
окажется у 
и т.д.
Через 
минут шляпа 
окажется у 
.
Если это тот же человек, что и 
, разность их номеров, то есть 
, должна делится на 
. Значит, шляпа может вернуться к
исходном владельцу, только если количество человек в цикле является степенью двойки. При этом фокусник хочет, чтобы был цикл как
можно большей длины.
Самая большая степень двойки, не превосходящая 100, это 
. Фокусник в начале должен разбить пришедших на представление на
циклы, длины одного из которых равна 64, а длины остальных — меньшие степени двойки, не важно какие. Тогда через 6 минут все шляпы
окажутся у своих настоящих владельцев (у некоторых они окажутся раньше, но в этот момент это впервые произойдёт для всех
сразу).
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
