Процессы и алгоритмы
Ошибка.
Попробуйте повторить позже
Фокусник вместе со своим помощником собираются показать следующий фокус. Помощник надевает фокуснику повязку на глаза,
приглашает на сцену случайного зрителя из зала и просит его написать последовательность из нулей и единиц длины 
Затем
помощник верно называет фокуснику номер и значение некоторого одного члена последовательности. Задача фокусника — отгадать 
других членов последовательности (т. е. назвать их номера и значения). Докажите, что они могут заранее договориться так, чтобы фокус
удался.
Источники:
Подсказка 1
Итак, у нас дана последовательность, и помощник называет номер и значение какого-то члена последовательности. Может, он выбирает элемент не случайно?
Подсказка 2
А нужно ли там рассматривать всю последовательность сразу, или достаточно будет какой-то ее части? Можем ли мы к тому же выбирать эти значения при помощи функции? Сколько значений должен угадать фокусник?
Подсказка 3
Для начала будем рассматривать последовательности, состоящие из 2025 последних элементов данной последовательности. Пусть за это будет отвечать функция f (она будет выдавать из некоторой последовательности x ее последние 2025 элементов). Давайте также обозначим за А множество всех последовательностей нулей и единиц длины 2025, за B — множество всех последовательностей длины 2025, в которых лишь одна единица, за С — все последовательности длины 2025, не включая элементы B. Какая будет длина у С? По какому принципу помощник может сообщать элемент?
Подсказка 4
Давайте также введем функцию g, нумерующую все элементы множества С. Давайте считать, что и помощник, и фокусник знают f и g. Пусть помощник увидел какую-то последовательность. Попробуйте разобрать случаи.
Подсказка 5
Если помощник увидит последовательность x, и f(x) ∈ C, тогда он сообщит элемент с номером g(f(x)). Какие еще случаи можно рассмотреть по аналогии? Не забудьте воспользоваться тем, что в последовательностях множества B ровно одна единица.
Подсказка 6
f(x) ∈ B, первая цифра x - 1 ⇒ сообщает значение и номер единицы из последовательности f(x). f(x) ∈ B, первая цифра x — 0. 1) Единица не на последнем месте ⇒ сообщает значение и номер следующего за ней нуля. 2) Единица на последнем месте ⇒ сообщает значение и номер первого нуля. Как тогда должен действовать фокусник, если ему известны значения функций и множества?
Подсказка 7
Пусть фокусник услышал число в диапазоне [1;2²⁰²⁵ - 2025]. Какой это будет случай?
Подсказка 8
Это случай f(x) ∈ C (⇒ фокусник услышал значение и номер элемента g(f(x))). Может ли он тогда восстановить последние 2025 элементов?
Подсказка 9
Заметим, что функция нумерации биективна, следовательно, по ней можно восстановить f(x). А что произойдет в остальных двух случаях?
Подсказка 10
Если фокусник услышит цифру с номером из [2²⁰²⁵ - 2024; 2²⁰²⁵], то f(x) ∈ B и либо это 0 из начала, либо 0 после единицы. Но мы знаем, что в последовательностях из B ровно одна единица. Какой вывод можно сделать?
Пусть 
— множество всех последовательностей из нулей и единиц длины 
Определим функцию 
сопоставляющую каждой
последовательности 
из 
последовательность, состоящую из её последних 
цифр. Пусть 
— множество всех
последовательностей из нулей и единиц длины 
в которых ровно один элемент равен 
а остальные равны 
а 
— множество
всех остальных последовательностей длины 
Тогда 
Введём функцию 
нумерации
для последовательностей из 
, т.е. функцию
взаимно однозначно сопоставляющую каждой последовательности из 
какой-то номер от 
до
Обе функции 
и 
известны как фокуснику, так и его помощнику.
Теперь опишем действия каждого из них. Пусть помощник увидел перед собой последовательность 
Тогда у него есть несколько
вариантов:
1) Если 
то он сообщает значение элемента под номером 
2) Если 
и первая цифра последовательности 
равна 
то помощник сообщает значение и номер единицы из
последовательности 
3) Если 
и первая цифра последовательности 
равна 
то помощник сообщает значение и номер того нуля, который
следует за единственной единицей в последовательности 
(такая единица единственна, так как эта последовательность
принадлежит множеству 
). Если же единица стоит на последнем месте, то помощник сообщает значение и номер первого
нуля.
Опишем действия фокусника.
1) Если он услышал цифру с номером из диапазона от 
до 
то он понимает, что это случай 1). Значит, по этому номеру с
помощью функции нумерации (ввиду её биективности) он может восстановить 
а значит, и последние 
цифр вместе с их
номерами.
2) Если он услышал цифру с номером из последних 
номеров, то он понимает, что это случай 2) или 3). Но в обоих случаях у нас у
последовательности 
последние 
цифр все нули, кроме одного. Из последних 
цифр он может отгадать 
других
цифры, так как одну уже назвал помощник. Также он может назвать самую первую цифру последовательности, так как
она в случаях 2) и 3) совпадает с той цифрой, что называет помощник. Значит, и в этом случае фокусник отгадает 
цифр.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
