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

Сложная
Комбинаторика
Источник:
Московская олимпиада школьников, Заключительный этап, 2025, 11 класс, Первый тур

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

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

Войдите, чтобы проверять ответы

Ответ: .

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

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

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

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

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

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

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

Чемпионат по футболу проходил в два круга. В каждом круге каждая команда сыграла с каждой один матч (за победу даётся три очка, за ничью одно, за поражение ноль). Оказалось, что все команды вместе набрали в первом круге 60% от общей суммы всех очков за два круга. Известно также, что победитель чемпи
Сложная
Комбинаторика

МОШ 2020, 11 класс, задача 4

Из шахматной доски 8 × 8 вырезали 10 клеток. Известно, что среди вырезанных клеток есть как чёрные, так и белые. Какое наибольшее количество двухклеточных прямоугольников можно после этого гарантированно вырезать из этой доски?
Сложная
Комбинаторика