Всесиб 2024, отборочный этап, 7 класс, задача 3

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

(Найдите ответ и докажите, что он максимален.)

Ответ

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

Покажем, что это число достижимо. Пронумеруем рыцарей от до , и пусть -й рыцарь выбил -го, после чего каждый из рыцарей с номерами от до выбил соответственно рыцаря с номером от до . Лжецы же пусть как-то повыбивали друг друга, чтобы их осталось . Итого, ответом является число .

Только ответ.

Доказательство того, что рыцарей осталось не более .

Верный пример на рыцарей. Складывается с предыдущим пунктом.

Идейно верный пример, но в нём может быть оставшийся лжец, выбивший ровно одного рыцаря.

-2

Максимум: 7

Похожие задачи

Всесиб 2025, отборочный этап, 7 класс, задача 3

(7 баллов) На острове располагаются три города, все жители которых являются либо рыцарями, которые всегда говорят правду, либо лжецами, которые всегда врут. Однажды каждый житель острова заявил: «В одном из других городов лжецов живёт меньше, чем в моём городе». Может ли на этом острове проживать ро

Средняя

Комбинаторика

Всесиб 2025, отборочный этап, 9 класс, задача 2

(7 баллов) В некоторой группе из не менее, чем трёх человек, произошёл обмен письмами такой, что для каждых двух человек A и B либо A послал письмо B, либо B послал письмо A, но не одновременно и то и другое. Кроме того, для любых трёх человек A, B и C выполняется условие: если A послал письмо B, а

Средняя

Комбинаторика

Всесиб 2022, отборочный этап, 8 класс, задача 4

(7 баллов) Как-то раз в средневековой Англии за круглым столом собрались 2021 человек. Каждый из них был либо рыцарем, который всегда говорил правду, либо лжецом, который всегда лгал, причём среди присутствовавших имелся хотя бы один рыцарь и хотя бы один лжец. Кроме того, известно, что в этот день

Средняя

Комбинаторика

Всесиб 2024, отборочный этап, 8 класс, задача 3

(7 баллов) Дан клетчатый квадрат 4 × 4. Вася разрезал его по линиям сетки на четыре части одинаковой площади. Могли ли у него получиться 4 различных многоугольника?

Средняя

Геометрия

Комбинаторика