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