Физтех 2024/25 · Математика · 9 кл., №10 — решение · Отборочный этап

Условие

Учитель математики договорился с пришедшими на кружок $23$ учениками, что они выберут, кто из них будет лжецом (всегда лгать), а кто — рыцарем (всегда говорить правду). После чего учитель раздал ученикам карточки с числами, причём числа на всех карточках различны. Ученики встали по кругу и посмотрели карточки соседей. После этого каждый из учеников сказал: «Число на моей карточке больше, чем у моих соседей». Какое наибольшее количество учеников могут сказать: «Число на моей карточке меньше, чем у моих соседей»?

О задаче · 9 класс

Олимпиада: Физтех (МФТИ)
Этап: Отборочный этап, первый тур (1 попытка)
Предмет / класс: Математика · 9 класс
Сезон: 2024/25

Кто из учеников рыцари, если все сказали первую фразу? Кто из рыцарей и кто из лжецов может сказать вторую фразу? В модели переставляй числа по кругу и следи, кто может сказать «меньше». Ниже можно сверить ответ.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеУченики по кругу

Пробуй свои варианты. Разбор останется закрытым.

Исследуй задачу

Ученики по кругу

Как расставить числа, чтобы как можно больше учеников могли сказать «меньше»?

Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.

Подсказка для решения без модели

Если модель не открылась, попробуй так. Нарисуй 7 учеников по кругу и раздай им числа 1–7. Отметь тех, у кого число больше обоих соседей (рыцари), и тех, у кого меньше обоих. Кто может сказать вторую фразу?

Подсказка 1

Рыцарь говорит правду, поэтому рыцари — ровно те, чьё число больше, чем у обоих соседей. Все остальные — лжецы, и для них первая фраза ложна.

Подсказка 2

Вторую фразу рыцарь сказать не может. Лжец может — если она для него ложна. Кто точно не может её сказать? Посмотри на учеников с самым большим и самым маленьким числом.

Разобрать решение по шагам

Кто рыцарь, а кто лжец

Все сказали «моё число больше, чем у соседей». Для рыцаря это правда, поэтому рыцари — это ровно те ученики, чьё число больше, чем у обоих соседей. Для каждого лжеца фраза ложна: его число меньше, чем хотя бы у одного соседа.

Кто может сказать «меньше»

Рыцарь может сказать только правду, а его число больше соседних, — фразу «моё число меньше, чем у соседей» он сказать не может.

Лжец может её сказать, только если она ложна, то есть если его число не меньше, чем у обоих соседей.

Ученик с наибольшим числом — рыцарь (его число больше соседних), он не может сказать вторую фразу. Ученик с наименьшим числом — лжец, но для него вторая фраза была бы правдой, и сказать её он тоже не может. Значит, вторую фразу могут сказать не больше $23 - 2 = 21$ ученика.

Пример на 21 ученика

Раздадим по кругу карточки $1, 2, 3, \ldots, 23$ Рыцарь один — с числом $23$ (у него соседи $22$ и $1$ ). У каждого ученика с числом от $2$ до $22$ один сосед меньше, а другой больше: первая фраза для него ложна (он лжец), и вторая тоже ложна — сказать её он может. Не могут только ученики с числами $23$ и $1$ Итого $21$

Проверка

Полный перебор всех расстановок по кругу для $n$ от $3$ до $8$ учеников показывает, что вторую фразу могут сказать не больше $n - 2$ человек, и это значение достигается (тест модели). Для $23$ учеников расстановка $1, 2, \ldots, 23$ даёт $21$ В других версиях учеников $19$ $18$ и $15$ — ответы $17$ $16$ и $13$

Ответ

$21$

Ответ

$21$

Главная идея

Рыцари — локальные максимумы; вторую фразу не могут сказать ни ученик с наибольшим числом, ни ученик с наименьшим, а пример 1, 2, …, n по кругу показывает, что остальные n − 2 могут.

Рыцари и лжецы с одной и той же фразой у всех — сначала понять, кто есть кто, затем отдельно оценка и пример.

Где легко ошибиться

Считать, что вторую фразу могут сказать только рыцари; забыть, что лжец с наименьшим числом не может её сказать; привести оценку без примера.

Источник и авторство

Олимпиада «Физтех» · математика · 9 класс · 2024/25 · отборочный этап, первый тур (1 попытка). Задача 10, версия с ID 3574 — первая в официальном файле; другие версии этого номера (ID 3577, 3576, 3575) можно выбрать в модели.

Официальные условия (PDF организатора, стр. 9) ↗ · Ответы и решения организатора ↗ · Архив заданий олимпиады ↗

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до знакомства с решениями организатора; затем ответ совпадает с ответом организатора («Решения М9 1 попытка 2024», стр. 10 ↗: ID 3574: 21; ID 3577: 17; ID 3576: 16; ID 3575: 13.). Сверены все четыре официальные версии этого номера.

Продолжить тему: Высказывания и логические выводы →

Тема, знания и приёмы

Высказывания и логические выводы · Нужна школьная база

Рыцари и лжецы
Оценка и пример

Приёмы решения: Логический вывод и исключение вариантов · Оценка и достижимость

Задать вопрос по задаче →