Задача про рыцарей и лжецов

[Karakurt]

На острове живут 100 рыцарей и 100 лжецов, у каждого из них есть хотя бы один друг. Рыцари всегда говорят правду, а лжецы всегда лгут. Однажды утром каждый житель произнес фразу «Все мои друзья — рыцари», либо «Все мои друзья — лжецы», причем каждую из фраз произнесло ровно 100 человек. Найдите наименьшее возможное число пар друзей, один из которых рыцарь, а другой — лжец. Объясните.

[RawonaM]

По-моему 50.
Достаточно только рыцарей рассмотреть: если менее 50 рыцарей скажут, что все их друзья — рыцари, то есть более 50 смешанных пар.
Если более 50 рыцарей скажут, что все их друзья — рыцари, то более 50 лжецов должны сказать, что их друзья лжецы, следовательно будет более 50 смешанных пар.

[Darkstar]

Слово "лгут" я понимаю как "говорят наоборот". Поскольку, если оно означает что-то другое задача усложняется...

Произведем вербальные замены для упрощения задачи. Мальчики всегда говорят правду, а девочки всегда лгут. Задача сэконимить на гетеро-браках, поскольку свадьбы стоят дорого. Теперь задача будет более наглядна и интуитивно понятна.

Первая фраза "Все мои друзья - мальчики" отражает только связи "м-м" и "ж-ж", поскольку мальчики говорят "как есть", а девочки всегда говорят наоборот. Она отражает только гомо-связи.
Ее можно выразить в виде 100 = м + ж, где м - кол-во мальчиков, ж- кол-во девочек, произнесших эту фразу.

При этом для гомо-связей пока теоретически возможны такие крайние ситуации: когда число девочек = 0, или число мальчиков = 0.

Однако в этом случае гетеро-браков вообще не будет, а они есть, исходя из второй фразы, которую произнесли 100 человек из 200 на острове.

Следовательно, мы приходим к выводу, что 50 мальчиков и 50 девочек исключены, поскольку образуют гомо-пары.

Далее рассмотрим вторую фразу "Все мои друзья - девочки", отражает только связи "м-ж" и "ж-м", поскольку мальчики говорят "как есть", а девочки всегда говорят наоборот. Она отражает только гетеро-связи.
Ее тоже можно выразить в виде 100 = м + ж, где м - кол-во мальчиков, ж- кол-во девочек, произнесших вторую фразу.

Теперь задача сводится к тому чтобы с помощью парных связей израсходовать эти 50 мальчиков и 50 девочек, причем требуется именно минимальное число гетеросвязей, чтобы сэкономить на свадьбах.

Возможна такая ситуация, когда 1 мальчик дружит с несколькими девочками, или наоборот 1 девочка с несколькими мальчиками. Однако такое образование связей слишком неэкономно, нам нужно их минимизировать. Тогда можно прийти к выводу, что каждый мальчик должен дружить только с одной девочкой. Всего их, как показано выше, по 50, следовательно получается 50 минимальных пар.

Как-то так... Может что-то и неправильно... Но вроде по-всякому крутил...