Условие
На совместный симпозиум лжецов (всегда лгут) и правдолюбов (всегда говорят правду) собрались 12 участников, среди которых не все лжецы и не все правдолюбы. Каждые два участника либо знакомы, либо незнакомы друг с другом. Каждый ответил «да» или «нет» на вопрос «Знакомы ли вы?» про каждого из остальных. Какое наименьшее количество ответов «да» могло быть получено?
Решение
Рассмотрим каких-то двух участников и проанализируем их высказывания друг о друге. Если это два правдолюба, то на вопросы друг о друге оба либо дают ответ «да», если они знакомы, либо «нет», если незнакомы. Если это два лжеца, то, наоборот, знакомые лжецы отвечают «нет», а незнакомые – «да». Наконец, если один из знакомых участников – правдолюб, а другой – лжец, то правдолюб отвечает «да», а лжец – «нет»; если же они незнакомы, то, наоборот, правдолюб отвечает «нет», а лжец – «да».
Теперь ясно, что для достижения наименьшего количества ответов «да» необходимо, чтобы все лжецы были знакомы друг с другом, а все правдолюбы – не были. Если среди собравшихся $k$ правдолюбов, то лжецов $12-k$, и количество ответов «да» в этом случае равно $k(12-k)$, то есть количеству пар, состоящих из правдолюба и лжеца (в каждой такой паре ровно один раз звучит ответ «да», независимо от знакомства или незнакомства участников). Выражение $k(12-k) = 12k - k^2$ является квадратным трёхчленом с отрицательным старшим коэффициентом и вершиной $k_0 = 6$. Его наименьшее значение достигается при значениях $k$, наиболее удалённых от $k_0 = 6$, то есть при $k = 1$ и $k = 11$, и равно $11$. Это также легко проверить перебором значений $k = 1, 2, \ldots, 11$. Таким образом, 11 – наименьшее возможное количество ответов «да».
Ответ
11.
Замечания
См. также задачу
67459.
Источники и прецеденты использования
|
|
|
олимпиада |
|
Название |
Московская математическая олимпиада |
|
год |
|
Год |
2025 |
|
Номер |
88 |
|
класс |
|
Класс |
8 |
|
задача |
|
Номер |
2 |
