Задание №180830: Командная олимпиада 2021
Даны натуральные числа 𝑛 и 𝑘, причем 𝑛 ⩾ 𝑘. В группе из 𝑛 человек каждый либорыцарь,которыйвсегдаговоритправду,либолжец,которыйвсегдалжет.Антонможет задать всякому человеку следующий вопрос: «Какова чётность количества рыцарей в множестве 𝐴?», где 𝐴 — подмножество группы из 𝑛 людей, в котором всего 𝑘 человек. Ответ на этот вопрос может быть «чётно» или «нечётно». При каких 𝑘 и за какое минимальное число вопросов можно узнать про каждого, кем он является?
Что проверяет это задание
Задание относится к теме «Командная олимпиада 2021» и рассчитано на уровень 8 класса. Для решения понадобятся:
- анализ условия
- выбор формулы
- проверка вычислений
Источник: Турнир математических боёв и командная олимпиада МЦНМО — официальный архив · 2021
Качество материала
Показываем, из чего состоит страница и можно ли проверить материал по первоисточнику.
Последняя проверка решения:
Происхождение задания
- Банк заданий
- Турнир математических боёв и командная олимпиада МЦНМО — официальный архив
- Организатор
- МЦНМО
- Год материала
- 2021
- Материалы
- 1 файл
Связанные понятия
План самостоятельного решения
- Перепишите известные данные и отдельно сформулируйте, что требуется найти или доказать.
- Свяжите условие с темой «Командная олимпиада 2021» и выберите подходящее правило, формулу или способ рассуждения.
- Запишите промежуточные шаги: это помогает заметить потерянный знак, случай или логический переход.
- Сверьте результат со всеми ограничениями условия и только затем откройте подробный разбор.
Ориентировочное время: 15 минут.
Закрепить тему
После разбора попробуйте решить ещё десять заданий по предмету «Математика». Вариант формируется заново, а ответы можно сразу проверить.
Решение по шагам
Ответ: при чётных 𝑘 можно за 𝑛 вопросов.
Решение. Давайте всем людям раздадим остатки по модулю 2. Рыцари получат 1, а лже-
цы0. Еслиспросить человека счислом 𝑝 промножество 𝐴,то вкачестве ответамы полу-
чим число
(𝑝 + 1) + ∑ 𝑎 (mod 2).
𝑎∈𝐴
Если 𝑝 лежит в множестве 𝐴, то мы узнаем сумму набора из 𝑘 − 1 числа, иначе из 𝑘 + 1
числа.Если𝑘нечетно,тозамениввсехрыцарейналжецов,алжецовнарыцарей,унасне
поменяютсясуммыпонаборам.Тогдамынесможемничегопонятьнипроодногочело-
века. Тогда 𝑘 должно быть четным. Понятно, что нужно минимум 𝑛 вопросов, т.к. всего
вариантовраспределениялжецовирыцарей2𝑛,анакаждыйвопроснамотвечаютодним
из двух вариантов. Спросим у всех про фиксированное множество 𝐵. Просуммировав по
5
суммам для людей из множества 𝐵 мы получим число
(𝑘 − 1)(∑ 𝑏) = ∑ 𝑏 (mod 2).
𝑏∈𝐵 𝑏∈𝐵
Последнееверно,т.к.𝑘−1нечетно.Тогда,принимаявовниманието,чтокаждыйдалпро
𝐵 ответ
(𝑝 + 1) + ∑ 𝑏 (mod 2).
𝑏∈𝐵
мы узнаем все про каждого человека.
Используемые формулы
(𝑘 − 1)(∑ 𝑏) = ∑ 𝑏 (mod 2).
Самопроверка после решения
- Я использовал все данные из условия и не добавил неподтверждённых предположений.
- Каждый переход в рассуждении объяснён правилом, формулой или ранее доказанным фактом.
- Ответ соответствует вопросу, а обозначения и единицы измерения записаны однозначно.
- Я сравнил свой ход решения с разбором и понял причину каждого отличия.
Типичные ошибки
- Не проверить область допустимых значений.
- Потерять знак при переносе или раскрытии скобок.
- Не выполнить обратную подстановку.