Перейти к основному содержимому
  1. Математика
  2. ДВИ МГУ (математика)
  3. Задачи
  4. №18286

Задача №18286

Средне

Задача #18286

Комбинаторика и логика•10 баллов

Проверить решение?

Покажи своё решение — проверю и покажу, где ошибка

Решай похожие задачи

Потренируйся на похожих — ИИ проверит твои решения

#18280

Задача по теме "Комбинаторика и логика"

Средне
#18276

Задача по теме "Комбинаторика и логика"

Сложно
#20723

Задача по теме "Комбинаторика и логика"

Легко

Информация

ЭкзаменЕГЭ
Часть

2

Раздел

Задачи повышенной сложности

Тип задачи№90 Нестандартные задачи (архив)
ТемаКомбинаторика и логика
ИсточникМехмат МГУ, Письменный экзамен, 2009 год (механико-математический факультет МГУ; первая смена — задачи 1-4, вторая смена — задачи 5-8)
Откуда задача

Мехмат МГУ (архив)

Теги
Поочередный и одновременный выборФормулы числа сочетаний и перестановок. Бином НьютонаЧисла и их свойства

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

Обозначим через t число правдивцев, через l — число лжецов, а через n=t+l — общее число сотрудников.

Подсчёт общего числа ответов. Каждого из n сотрудников спросили про каждого из остальных n−1, поэтому всего прозвучало n(n−1) ответов. По условию ответов было 32+40=72, значит

n(n−1)=72.

Ключевое наблюдение: что отвечает сотрудник про другого. Рассмотрим упорядоченную пару «сотрудник A высказывается про сотрудника B» (при A=B). Разберём два случая.

  • A и B одного типа. Если оба правдивцы, то A честно говорит про правдивца B: ответ «правдивец». Если оба лжецы, то истина про B — «лжец», но A-лжец её переворачивает и говорит «правдивец». В обоих случаях ответ — «правдивец».
  • A и B разных типов. Если A правдивец, а B лжец, то A честно говорит «лжец». Если A лжец, а B правдивец, то истина «правдивец», лжец её переворачивает и говорит «лжец». В обоих случаях ответ — «лжец».

Итак, ответ «правдивец» даётся тогда и только тогда, когда спрашивающий и тот, о ком говорят, одного типа; ответ «лжец» — когда они разных типов. Это не зависит от того, кто именно из них кто.

Перевод в комбинаторику. Число упорядоченных пар одного типа равно

t(t−1)+l(l−1),

а число упорядоченных пар разных типов равно 2tl (пара «правдивец–лжец» считается в обоих порядках). Получаем систему

{t(t−1)+l(l−1)=32,2tl=40.​

Решение системы. Из второго уравнения tl=20. Преобразуем первое уравнение, используя n=t+l:

t(t−1)+l(l−1)=t2+l2−(t+l)=((t+l)2−2tl)−(t+l)=n2−2⋅20−n=n2−n−40.

Приравнивая к 32, получаем

n2−n−40=32⟺n2−n−72=0.

Корни n=9 и n=−8; по смыслу n>0, значит n=t+l=9. (Это согласуется с n(n−1)=9⋅8=72.)

Искомая разность. Используем тождество

(t−l)2=(t+l)2−4tl=92−4⋅20=81−80=1,

откуда ∣t−l∣=1.

Существование и контроль. Система t+l=9, tl=20 даёт пары (t,l)=(5,4) или (4,5) — целые неотрицательные значения, то есть конфигурация действительно реализуется (например, 5 правдивцев и 4 лжеца дают ровно 5⋅4+4⋅3=32 ответа «правдивец» и 2⋅5⋅4=40 ответов «лжец»).

Ответ: количество правдивцев и лжецов отличается на 1.