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