МОШ 2025, 11 класс, задача 1

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

(М. Евдокимов)

Ответ

Ответ: .

Решение. Пусть на симпозиуме лжецов и правдолюбов. По условию . Посмотрим на какого-нибудь лжеца и какого-нибудь правдолюба. Если они знакомы, то правдолюб скажет «да», а если незнакомы, то лжец скажет «да». В любом случае будет ровно один ответ «да» для каждой такой пары, а всего пар . Минимальное значение этого выражения равно и достигается при или . Таким образом, в любом случае будет не менее ответов «да». Пример, когда это значение достигается: лжецов и правдолюб, и все друг с другом знакомы.

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

МОШ 2023, 11 класс, задача 2

Какое наименьшее количество различных целых чисел нужно взять, чтобы среди них можно было выбрать как геометрическую, так и арифметическую прогрессию длины 5? (М. А. Евдокимов)

Сложная

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

МОШ 2022, 10 класс, задача 3

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

Сложная

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

МОШ 2021, 10 класс, задача 5

Пусть p и q — взаимно простые натуральные числа. Лягушка прыгает по числовой прямой, начиная в точке 0, каждый раз либо на p вправо, либо на q влево. Однажды лягушка вернулась в 0. Докажите, что для любого натурального d

Сложная

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

МОШ 2020, 10 класс, задача 2

Среди зрителей кинофестиваля было поровну мужчин и женщин. Всем зрителям понравилось одинаковое количество фильмов. Каждый фильм понравился восьми зрителям. Докажите, что не менее 3/7 фильмов обладают следующим свойством: среди зрителей, которым фильм понравился, не менее двух мужчин.

Сложная

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