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

[klopa]

На острове живут 50 человек, из которых 35 — лжецы, которые могут соврать (а могут сказать и правду), а оставшиеся 15 — рыцари, которые всегда говорят правду. Все жители острова знают, кто лжецы. Какое наименьшее число человек достаточно выбрать, чтобы спросив потом у каждого, кто именно лжецы, по ответам вычислить хотя бы одного лжеца?

[Gagarin1968]

Я правильно понимаю, что в ответе должен прозвучать список из 35 человек? Или же список лжецов только из опрошенных?

[klopa]

Ответом является лишь число

[TOTAL]

klopa в сообщении #1568269 писал(а):

Ответом является лишь число

Не про этот ответ вопрос.
Выбирается группа из N человек. Каждый из них указывает на 35 лжецов. При каком минимальном N по этим указаниям можно выявить хоть одного лжеца. Так?

[zykov]

Тут была похожая задача: рыцари и лжецы.

[klopa]

TOTAL в сообщении #1568272 писал(а):

klopa в сообщении #1568269 писал(а):

Ответом является лишь число

Не про этот ответ вопрос.
Выбирается группа из N человек. Каждый из них указывает на 35 лжецов. При каком минимальном N по этим указаниям можно выявить хоть одного лжеца. Так?

Да, так.

[Sender]

(47?)

Опроса $36$ островитян недостаточно. Допустим, среди них оказалось $35$ лжецов и один рыцарь, при этом каждый называет лжецами всех остальных опрашиваемых. Даже если знать, что все лжецы в списке опрашиваемых, их ответы абсолютно симметричны, и мы не сможем узнать, кто же единственный рыцарь среди них. Аналогичное рассуждение справедливо для любого $n<36.$Пусть опрашиваемых островитян $n\geqslant 37$. Среди них $r\geqslant 2$ рыцарей, так что их ответы совпадают, при этом все они указывают друг на друга, а также на $15-r$ среди оставшихся неопрошенными островитян как на рыцарей. Мы не сможем выделить лжеца, если опрашиваемые разделены на группы, представители каждой из которых называют рыцарями всех членов своей группы и недостающее до $15$ число неопрошенных островитян, причём число таких групп должно быть не менее $2$, поскольку при $n\geqslant 36$ как минимум одна группа содержит рыцарей, а значит, состоит из них. Пусть имеется $m\geqslant 2$ таких групп, численностями $2\leqslant n_i\leqslant 15,1\leqslant i \leqslant m$. Тогда $\sum\limits_{i=1}^{m}n_i=n,$ для всех $i, 1\leqslant i \leqslant m$ выполнено $50-n\geqslant 15-n_i$, т.е. $n-n_i\leqslant 35.$ Если не ошибаюсь, наименьшее $n$, не допускающее разбиения на слагаемые, удовлетворяющие этим условиям, это $47.$

[miflin]

klopa в сообщении #1568261 писал(а):

лжецы, которые могут соврать (а могут сказать и правду)

Не делает ли это условие задачу неопределенной?
Одно дело - иметь дело с честным лжецом, а другое - с лицемером.

[wrest]

klopa в сообщении #1568261 писал(а):

лжецы, которые могут соврать (а могут сказать и правду),

klopa в сообщении #1568261 писал(а):

Какое наименьшее число человек достаточно выбрать, чтобы спросив потом у каждого, кто именно лжецы, по ответам вычислить хотя бы одного лжеца?

А что отвечает лжец на вопрос "кто лжецы"? Даёт список 35 случайно выбранных из 50 имён? Или, в случае если лжец решил солгать, он даёт список из 15 имён и тогда мы точно понимаем что эти 15 рыцари? Или лжец решает солгать или сказать правду по каждому имени отдельно, и тогда мы получаем список от 0 до 50 имён?
То есть: сколько имён может быть в списке (ответе) лжеца?

[zykov]

wrest в сообщении #1568406 писал(а):

А что отвечает лжец на вопрос "кто лжецы"? Даёт список 35 случайно выбранных из 50 имён?

Даёт произвольный список 35 из 49 (исключая себя самого).
("произвольный", а не "случайный", т.к. "случайный" подразумеввет некий случайны процесс, а он может выдавать следуя какой-то системе, про которую мы ничего не знаем.)

-- 31.10.2022, 13:03 --

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

-- 31.10.2022, 13:08 --

Думаю, 45 недостаточно.
Т.к. это может быть 15 рыцарей и ещё два кластера лжецов по 15, которые друг друга называют рыцарями и всех других лжецами (т.е. такой кластер неотличим от тех 15 рыцарей).
Вот 46-ой уже не подходит под эту схему не подходит и наверно можно определить.

[Sender]

zykov в сообщении #1568413 писал(а):

Вот 46-ой уже не подходит под эту схему не подходит и наверно можно определить.

$46$ можно разделить на три группы по $11$ и одну в $13$ человек. Представители первых трёх называют рыцарями себя и всех четверых неопрошенных, а представители последней - себя и любых двоих из неопрошенных.

-- Пн окт 31, 2022 13:34:06 --

Вообще, для $n>36$ можно взять такие разбиения:

$$\begin{tabular}{l} 37=17\cdot 2 +3 \\ 38=11\cdot 3 +5 \\ 39=8\cdot 4 +7 \\ 40=8\cdot 5 \\ 41=5\cdot 7 +6 \\ 42=6\cdot 7 \\ 43=4\cdot 8 +11 \\ 44=4\cdot 11\\ 45=3\cdot 15 \\ 46=3\cdot 11 +13 \\ \end{tabular}$$

-- Пн окт 31, 2022 13:41:46 --

Для $n=47$ численности групп должны быть не менее $12,$ но $4\cdot12=48>47,$ а $47-3\cdot12=11,$ $11+3=14<15.$

[zykov]

Sender
Верно, 46 не подходит.
При 47 так уже не разбить, будет кто-то называющий рыцарем кого-то другого из другого кластера.
Осталось только доказать для 47 в простой форме.