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