Зимний турнир Архимеда 2022 · 6–7 кл., №2.2

Условие

В замке живут Рыцари и Лжецы. Рыцари всегда говорят правду, Лжецы всегда лгут. Известно, что все жители разного возраста и количество золотых монет у всех разное. Каждый житель замка высказал два утверждения: 1) «Нет трёх жителей старше меня», 2) «Хотя бы у пяти жителей больше золотых монет, чем у меня». Могло ли это быть? Если да, сколько жителей могло быть в замке (укажите все ответы)?

О задаче

Олимпиада: Турнир Архимеда, XXXI зимний турнир
Предмет / классы: Математика · 6–7 классы, единый вариант
Дата: 30 января 2022

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

Самостоятельное исследованиеСобери замок

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

Своя гипотеза

Собери замок

Сначала дай прогноз. Потом выбери число жителей и расставь их по возрасту и по монетам: нажми на жителя, затем на другого в той же колонке — они поменяются местами. Модель проверит оба утверждения каждого и покажет, кто рыцарь, кто лжец, а у кого противоречие.

Без JavaScript модель не работает. Нарисуй два столбика мест — по возрасту и по монетам — и закрась места, где утверждение верно. Каждому рыцарю нужны два закрашенных места, каждому лжецу — два незакрашенных. Пример для восьми жителей — в шаге 5.

Начни с небольшого замка, например из $6$ жителей. Выстрой их по возрасту и по числу монет и для каждого проверь оба утверждения: у кого оба верны, у кого оба неверны, а у кого одно верно, а другое нет? Удобно делать это в модели «Собери замок»: она отмечает жителей, у которых одно утверждение верно, а другое нет, — такой житель не может быть ни рыцарем, ни лжецом. Получится ли обойтись без противоречий? А если жителей больше или меньше?

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

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

Подсказка 1

Каждое утверждение зависит только от одного порядка. Первое — только от места жителя по возрасту, второе — только от его места по числу монет. Выясни, на каких местах по возрасту первое утверждение верно и на каких местах по монетам верно второе.

Подсказка 2

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

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

Первое утверждение: смотрим на возраст

Утверждение «Нет трёх жителей старше меня» говорит о том, сколько жителей старше говорящего. Это число легко увидеть, если выстроить всех по возрасту: первым — самого старшего, вторым — следующего и так далее. Старше жителя на $1$ -м месте нет никого, старше жителя на $2$ -м месте — один житель, на $3$ -м — двое, на $4$ -м — уже трое.

«Нет трёх жителей старше меня» значит: старше меня меньше трёх жителей. Если старших трое или больше, то трёх жителей старше говорящего найти можно, и утверждение неверно. Поэтому:

у жителей на $1$ -м, $2$ -м и $3$ -м местах по возрасту первое утверждение верно;
у каждого, кто стоит на $4$ -м месте или дальше, оно неверно.

Итак, первое утверждение верно ровно у трёх самых старших жителей. Если же жителей меньше трёх, оно верно у всех.

Второе утверждение: смотрим на монеты

Со вторым утверждением поступим так же, только выстроим жителей по числу монет: первым — самого богатого. Богаче жителя на $1$ -м месте нет никого, на $2$ -м — один житель и так далее: на $5$ -м — четверо, на $6$ -м — уже пятеро.

«Хотя бы у пяти жителей больше золотых монет, чем у меня» значит: богаче меня пять жителей или больше. Поэтому:

у пяти самых богатых (места с $1$ -го по $5$ -е) второе утверждение неверно;
у каждого, кто стоит на $6$ -м месте или дальше, оно верно.

Если в замке не больше пяти жителей, то у каждого не больше четырёх других жителей, и второе утверждение неверно у всех.

На рисунке ниже оба порядка. Под каждым местом написано, сколько жителей старше (или богаче) того, кто на нём стоит, и верно ли там утверждение.

Верно ли утверждение, зависит только от места в своём порядке. По возрасту первое утверждение верно лишь на трёх первых местах. По монетам второе неверно на пяти первых местах и верно на всех следующих. Голубой — верно, жёлтый — неверно.

Рыцарь или лжец: оба верны или оба неверны

Рыцарь говорит только правду — у него оба утверждения верны. Лжец только лжёт — у него оба неверны. Житель, у которого одно утверждение верно, а другое нет, не может быть ни рыцарем, ни лжецом. Значит, если всё это могло быть, то у каждого жителя оба утверждения верны или оба неверны.

Сразу проверим маленькие замки. Пусть жителей не больше пяти. Тогда по шагу 2 второе утверждение неверно у всех. А у самого старшего жителя первое утверждение верно: старше него никого нет. Одно утверждение верно, другое неверно — противоречие. Значит, жителей в замке хотя бы шесть.

Считаем рыцарей и лжецов

Теперь жителей хотя бы шесть. Значит, в замке есть и три самых старших, и пятеро самых богатых, и выводы шагов 1 и 2 можно применить к каждому жителю.

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

По монетам. У пяти самых богатых второе утверждение неверно — рыцарями они быть не могут, значит, это лжецы. У всех остальных второе утверждение верно — это рыцари. Выходит, лжецов ровно $5$ — это пятеро самых богатых.

Каждый житель — рыцарь или лжец, поэтому всего жителей

3+5=8.

Проверим с другой стороны: по монетам рыцари — все, кроме пятерых самых богатых, то есть $8-5=3$ жителя. Столько же, сколько по возрасту, — подсчёты согласны.

Посмотрим, что ломается при других числах. При $6$ и $7$ жителях по монетам рыцарей было бы $6-5=1$ и $7-5=2$ а при $9$ и больше — $4$ и больше. По возрасту же их всегда ровно $3$ График ниже показывает это для замков от $1$ до $12$ жителей.

У скольких жителей верно каждое утверждение — для замков от

1

до

12

жителей. Синие кружки — первое утверждение: столько рыцарей «по возрасту». Зелёные квадраты — второе: столько рыцарей «по монетам». Совпадают эти числа только при

8

жителях.

Пример: восемь жителей

Осталось показать, что восемь жителей действительно могли так сказать. По шагу 4 рыцари — три самых старших, и при этом их второе утверждение должно быть верным: по монетам они должны стоять на трёх последних местах, то есть быть тремя самыми бедными. Остальные пятеро — лжецы, им достаются пять первых мест по монетам. Проще всего взять список по возрасту и перенести трёх самых старших в его конец — получится список по монетам.

Пусть жители по старшинству — Аня, Боря, Вика, Гоша, Даша, Егор, Женя, Зоя (Аня старше всех). По монетам, от самого богатого: Гоша, Даша, Егор, Женя, Зоя, Аня, Боря, Вика. Например, у Гоши $8$ монет, у Даши $7$ у Егора $6$ у Жени $5$ у Зои $4$ у Ани $3$ у Бори $2$ у Вики $1$ Проверим каждого.

Аня, Боря, Вика: старше них $0$ $1$ и $2$ жителя — первое утверждение верно. Богаче каждого из них хотя бы пятеро — Гоша, Даша, Егор, Женя и Зоя, — второе тоже верно. Это рыцари, и они сказали правду.
Гоша, Даша, Егор, Женя, Зоя: старше каждого из них хотя бы трое — Аня, Боря и Вика, — первое утверждение неверно. Больше всего богачей у Зои: богаче неё Гоша, Даша, Егор и Женя — всего четверо, а у остальных лжецов ещё меньше. Значит, и второе утверждение у них неверно. Это лжецы, и они солгали.

Возрасты у всех разные, числа монет тоже. Значит, так могло быть: в замке $8$ жителей — $3$ рыцаря и $5$ лжецов. На рисунке ниже этот пример показан так же, как в модели: два порядка и линии между местами каждого жителя.

Пример из шага 5. Слева жители по возрасту, справа — по монетам (число монет — в жёлтом кружке). Линия соединяет два места одного жителя: синие линии — рыцари, у них оба места «верные»; оранжевые — лжецы, у них оба места «неверные». По монетам порядок тот же, что по возрасту, только трое старших перенесены в конец, поэтому линии идут двумя пучками.

Проверка

Проверим ответ по-другому — по местам, а не по жителям. Рыцарю нужно «верное» место в обеих колонках, лжецу — «неверное» в обеих. По возрасту «верных» мест три, по монетам «верные» — все места после пятого.

При $7$ жителях «верных» мест по монетам только два — $6$ -е и $7$ -е. Трём самым старшим их не хватит: кто-то из них окажется среди пятерых самых богатых, и у него первое утверждение верно, а второе нет.
При $9$ жителях «верных» мест по монетам четыре — с $6$ -го по $9$ -е, а жителей с верным первым утверждением только трое. Одно из этих мест займёт кто-то не из трёх старших, и у него первое утверждение неверно, а второе верно.
При $8$ жителях «верных» мест по три с каждой стороны. В примере шага 5 на трёх последних местах по монетам стоят Аня, Боря и Вика — ровно трое самых старших.

В модели «Собери замок» видно то же: при $7$ и $9$ жителях, как ни переставляй, хотя бы одна красная пунктирная линия остаётся. Независимо от рассуждения компьютерный перебор всех расстановок для замков от $1$ до $10$ жителей нашёл замки без противоречий только при $8$ жителях.

Ответ

Да, могло. Жителей в замке могло быть только $8$ $3$ рыцаря — три самых старших и одновременно три самых бедных — и $5$ лжецов. Например, жители по старшинству — Аня, Боря, Вика, Гоша, Даша, Егор, Женя, Зоя, а монет у них соответственно $3$ $2$ $1$ $8$ $7$ $6$ $5$ и $4$

Ответ

Главная идея

Каждое утверждение зависит только от одного порядка: первое — от места по возрасту, второе — от места по богатству. Поэтому тип жителя можно найти дважды: по возрасту рыцари — три самых старших, по монетам лжецы — пятеро самых богатых. Сложив, получаем, что жителей $3+5=8$ остаётся построить пример.

Признаки: рыцари и лжецы произносят одинаковые фразы о своём месте в каком-то порядке («старше меня», «богаче меня», «выше меня»). Выстрой жителей по каждому признаку, найди места, где фраза верна, и сосчитай рыцарей и лжецов с каждой стороны.

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

Ошибиться на единицу на границе: решить, что у пятого по богатству уже пятеро богаче него. На самом деле богаче него только четверо — сам он в их число не входит, — и второе утверждение у него неверно. С такой ошибкой «рыцарей по монетам» выходит на одного больше, и подсчёт даёт $7$ жителей вместо $8$ Та же ловушка в первом утверждении: у четвёртого по старшинству старших ровно трое, и «Нет трёх жителей старше меня» у него уже неверно.

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

Турнир Архимеда · XXXI Зимний турнир · 30 января 2022 · математика · единый вариант для 6 и 7 классов. Официальная задача 2.2, 7 баллов.

Условия задач (PDF организатора) ↗ · Условия и решения ↗ · Страница турнира ↗

Условие — из официального PDF. Подсказки, объяснение и модели — Popov Academy. Решение проверено; результат сопоставлен с официальными материалами.

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

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

Высказывания и логические выводы · Начальный вход

Рыцари и лжецы: правдивые и ложные утверждения
Смысл слов «хотя бы» и «нет трёх»
Место в упорядоченном списке

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

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