Взвешивания и количество информации
Ошибка.
Попробуйте повторить позже
Имеется лента длины миллион с записанной на ней последовательностью нулей и единиц. Паре игроков предложено сыграть против казино
в следующую игру: каждый из них говорит 
или 
после чего вскрывается очередное число с ленты. Если оказывается, что оба его
угадали, то казино выплачивает им 
в противном случае берет с них 
Один из игроков заранее знает всю последовательность
чисел на ленте. Увы, ему запрещено как-либо передавать эту информацию своему партнеру — он может только делать
ходы в игре. При этом они могут договориться о стратегии до начала игры. Как должны действовать партнеры, чтобы не
проиграть?
Подсказка 1
Попробуем устроить стратегию так, что знающий всю ленту, будет определять достаточно много ходов своего партнера наперед. Например, можно ли договориться о такой стратегии, чтобы своими десятью ходами знающий ленту определял следующие десять ходов партнера?
Подсказка 2
Заранее можно договориться о том, что означают десять ответов первого для ответов следующего. Пусть они построят стратегию так, что будет ровно 3 ошибки и 7 правильных ответ, всего есть 3240 способов договориться об этом! А можно ли за первые 20 ходов закодировать еще какую-нибудь информацию о следующих ходах?
Подсказка 3
Рассмотрим следующие 11 ходов. Последовательностей из нулей и единиц всего 2048, что меньше 3240, а потому за первые 20 ходов можно построить информацию о следующих 11 символах и наверняка их угадать! Как теперь полностью выглядит стратегия?
Подсказка 4
Верно! Нужно разбить ленту на участки по 31 и 2 последние клетки, и повторять действия циклично. Остается проверить, что в этом случае партнеры не проиграют!
Разобьем ленту на 
участков из 
числа и останется 
последние клетки. Стратегия будет повторяться отдельно для каждого
участка.
Провидец (тот, кто знает всю ленту заранее) может первыми 
ходами задать следующие 
ходов своего партнера. И пускай он это
сделает так, что среди них будет 
поражения и 
побед, теперь посчитаем, сколькими способами он может это сделать. 
— способов
выбрать позиции на ленте для поражения и 
способа выбрать вариант поражения(оба не угадали цифру, ошибся только партнер, ошибся
только провидец), всего 
Рассмотрим оставшиеся 
позиций. Количество возможных последовательностей из 
и 
будет 
что меньше чем 
Тогда каждой последовательности можно сопоставить некоторую комбинацию из ошибок, то есть в первые 
ходов передать информацию
о последующих 
символах и гарантированно угадать их.
Теперь посчитаем, сколько денег они получат с такой стратегией за 
ход. За первые 
ходов проиграли не более 
монет. За
последующие 
проиграли в точности 
выиграли 
И в последующие 
ходов забирают 
монеты. По итогу игроки в плюсе
хотя бы на 
монеты.
Повторив данную стратегию на всех участках будет заработано хотя бы 
а на последних двух клетках можно
проиграть не более 
монет.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
