Условие
На совместный симпозиум лжецов (всегда лгут) и правдолюбов (всегда говорят правду) собрались 100 участников, среди которых не все лжецы и не все правдолюбы. Каждые два участника либо знакомы, либо незнакомы друг с другом. Каждый ответил «да» или «нет» на вопрос «Знакомы ли вы?» про каждого из остальных. Какое наименьшее
количество ответов «да» могло быть получено?
Решение
Пусть на симпозиуме $n$ лжецов и $100-n$ правдолюбов. По условию $1\leqslant n\leqslant 99$. Посмотрим на какого-нибудь лжеца и какого-нибудь правдолюба. Если они знакомы, то правдолюб скажет «да», а если незнакомы, то лжец скажет «да». В любом случае будет ровно один ответ «да» для каждой такой пары, а всего пар $n(100-n)$. Минимальное значение этого выражения равно 99 и достигается при $n=1$ или $n=99$, так как если $2\leqslant n\leqslant 98$, то $n(100-n)\geqslant 2\cdot 50 = 100 > 99$. Таким образом, в любом случае будет не менее $99$ ответов «да». Пример, когда это значение достигается: $99$ лжецов и $1$ правдолюб, и все друг с другом знакомы.
Ответ
$99$.
Замечания
См. также задачу
67444.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Московская математическая олимпиада |
|
год |
|
Год |
2025 |
|
Номер |
88 |
|
класс |
|
Класс |
11 |
|
задача |
|
Номер |
1 |
