2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Задача по рыцарей и лжецов
Сообщение30.10.2022, 13:27 


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

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 14:15 
Аватара пользователя


01/11/14
1647
Principality of Galilee
Я правильно понимаю, что в ответе должен прозвучать список из 35 человек? Или же список лжецов только из опрошенных?

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 14:42 


30/10/22
4
Ответом является лишь число

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 14:59 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
klopa в сообщении #1568269 писал(а):
Ответом является лишь число
Не про этот ответ вопрос.
Выбирается группа из N человек. Каждый из них указывает на 35 лжецов. При каком минимальном N по этим указаниям можно выявить хоть одного лжеца. Так?

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 15:03 


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

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 15:27 


30/10/22
4
TOTAL в сообщении #1568272 писал(а):
klopa в сообщении #1568269 писал(а):
Ответом является лишь число
Не про этот ответ вопрос.
Выбирается группа из N человек. Каждый из них указывает на 35 лжецов. При каком минимальном N по этим указаниям можно выявить хоть одного лжеца. Так?

Да, так.

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение30.10.2022, 21:01 


14/01/11
2916

(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.$

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение31.10.2022, 12:10 
Аватара пользователя


27/02/12
3706
klopa в сообщении #1568261 писал(а):
лжецы, которые могут соврать (а могут сказать и правду)

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

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение31.10.2022, 12:25 


05/09/16
11467
klopa в сообщении #1568261 писал(а):
лжецы, которые могут соврать (а могут сказать и правду),

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

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

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение31.10.2022, 12:58 


18/09/21
1676
wrest в сообщении #1568406 писал(а):
А что отвечает лжец на вопрос "кто лжецы"? Даёт список 35 случайно выбранных из 50 имён?
Даёт произвольный список 35 из 49 (исключая себя самого).
("произвольный", а не "случайный", т.к. "случайный" подразумеввет некий случайны процесс, а он может выдавать следуя какой-то системе, про которую мы ничего не знаем.)

-- 31.10.2022, 13:03 --

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

-- 31.10.2022, 13:08 --

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

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение31.10.2022, 13:27 


14/01/11
2916
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.$

 Профиль  
                  
 
 Re: Задача по рыцарей и лжецов
Сообщение31.10.2022, 13:51 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group