Правдорубы vs лжецы.

[e_kaspersky]

Всем приятных трудовых будней!

А чтобы они, будни, получились совсем весёлыми, у меня есть для вас хорошая задачка :) Не пугайтесь! - в этот раз она не вполне арифметическая. Она логическая и социальная. Про то, как, наплевав на карантины и пандемии, большая толпа из тридцати друзей и просто знакомых собралась на шашлыки с пивом. Они расселись за

Comments

[pyka_npu3paka]

условие конечно с подвохом
лжец может сказать как правду, так и солгать
вероятность того, что правдоруб скажет правду =1, а у лжеца вероятность узнать правду =0.5.
х у нас число лжецов, у - правдорубов.
(0.5х+у)/30 =z - средняя вероятность узнать правду. Но z не может быть по условию задачи быть меньше единицы. Правду-то мы должны узнать!) Получается, что единственный ответ х=0.

[mikluha_maklai]

Ответ. При X=8.
Доказательство.
1. Будем обозначать через 1 (0), когда правдоруб или лжец говорит, что справа от него правдоруб (лжец).
2. Сидящие рядом n правдорубов (P) выдадут последовательность ответов в виде n-1) единиц и затем 0. Сидящие левее левого правдоруба лжецы могут удлинить последовательность единиц, но не могут укоротить ее.
3. Сидящие рядом k лжецов (L) могут выдать последовательность из максимум (k-1) единиц и затем 0.
4. Обозначим через N максимальное число правдорубов, сидящих рядом, и через K максимальное число лжецов, сидящих рядом. Если при любой рассадке лжецов N>K, то правдоруб (один из) определяется как тот, который стоит справа в самой длинной последовательности единиц.
5. В случае 30 максимально допустимое число лжецов 8. Покажем, что при 8 лжецах всегда N>K, рассматривая смежные группы лжецов.
* 1 группа (все лжецы сидят рядом). K=8, N=22, N>K.
* 2 группы. K<=7, N>=11, N>K.
* 3 группы. K<=6, N>=8, N>K.
* 4 группы. K<=5, N>=6, N>K.
* 5 групп. K<=4, N>=5, N>K.
* 6 групп. K<=3, N>=4, N>K

[e_kaspersky]

Верно!

[mikluha_maklai]

Я посмотрел, как максимально допустимое количество лжецов (B) зависит от числа людей за столом (A). Ответ интересный. В таблице приведены результаты для A от 1 до 154. Таблица может быть легко продолжена.

==================
A B C
------------------
1-2 0 2
3-4 1 2
5-7 2 3
8-10 3 3
11-14 4 4
15-18 5 4
19-23 6 5
24-28 7 5
29-34 8 6
35-40 9 6
41-47 10 7
48-54 11 7
55-62 12 8
63-70 13 8
71-79 14 9
80-88 15 9
89-98 16 10
99-108 17 10
109-119 18 11
120-130 19 11
131-142 20 12
143-154 21 12
==================

колонка A - число людей за столом
колонка B - максимально допустимое количество лжецов
колонка C - мощность A: помогает понять, как устроена таблица и как продолжить ее

[e_kaspersky]

Занятное наблюдение :)
Тогда непонятно - почему в исходной задаче было 30? (я именно так её и услышал).