Отгадай загадку и реши вопрос - 2 (правдецы и шизики)

[assassello]

Кидайте решения, не стесняйтесь.

[assassello]

Из решения для 3 выводится 22 для 23. Забавная задачка.

Рассказывайте.

[Буратино]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

[Lisa]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

Почти. У Б спрашивать не надо. Если ответ А нет, то С точно правдец. Если ответ А да, то Б точно правдец.

[perkins]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

если правдец знает кто шизик, а кто нет, то задача решается очень быстро, но я не уверен, что эта задача была поставлена

[assassello]

Отлично! теперь надо обобщить.

[assassello]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

если правдец знает кто шизик, а кто нет, то задача решается очень быстро, но я не уверен, что эта задача была поставлена

По условию задачи, все жители знают друг о друге. Давай быстрое решение.

[assassello]

Как масштабировать пока не понял.

Аналогично. Ждем Лизу!

[Буратино]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

Почти. У Б спрашивать не надо. Если ответ А нет, то С точно правдец. Если ответ А да, то Б точно правдец.

Логично второй вопрос не нужен.

[Lisa]

Как масштабировать пока не понял.

Аналогично. Ждем Лизу!

По индукции из решения для 3 Завтра напишу если никто больше не придумает.

[perkins]

если правдец знает кто шизик, а кто нет, то задача решается очень быстро, но я не уверен, что эта задача была поставлена

По условию задачи, все жители знают друг о друге. Давай быстрое решение.

ОК, это я пропустил

[perkins]

На троих вроде получается за два вопроса. Допустим есть трое А Б и С. Берем А и Б и спрашиваем у А правдец ли Б и спрашиваем у Б правдец ли А. Если оба сказали да то оба правдецы. если оба сказали нет или один сказал нет а второй да то С гарантированно правдец. Как масштабировать пока не понял.

Почти. У Б спрашивать не надо. Если ответ А нет, то С точно правдец. Если ответ А да, то Б точно правдец.

если А шизик, то кто Б и С мы знаем по дефолту, но если мы не знаем, что А шизик, то по его ответам мы не знаем кто Б и С

[lizacat]

Напомнило

[Lisa]

Решение для любого нечетного х с количеством Ш меньше половины.
Выстраиваем всех в шеренгу в произвольном порядке. Начиная с левого крайнего спрашиваем - твой сосед справа П? Если ответ да, сдвигаемся к следующему и задаем тот же вопрос. Когда получили ответ нет убираем обоих, у предыдущего левого спрашиваем про его нового соседа. Если самый первый ответ был нет, тоже убираем обоих и начинаем с нового левого крайнего. В конце или останется один и он точно П, или шеренга где все ответили да, крайний правый в ней точно П.
Про каждого участника вопрос задается максимум один раз, про первого левого ни разу. Количество вопросов не больше х-1.

[assassello]

Решение для любого нечетного х с количеством Ш меньше половины.
Выстраиваем всех в шеренгу в произвольном порядке. Начиная с левого крайнего спрашиваем - твой сосед справа П? Если ответ да, сдвигаемся к следующему и задаем тот же вопрос. Когда получили ответ нет убираем обоих, у предыдущего левого спрашиваем про его нового соседа. Если самый первый ответ был нет, тоже убираем обоих и начинаем с нового левого крайнего. В конце или останется один и он точно П, или шеренга где все ответили да, крайний правый в ней точно П.
Про каждого участника вопрос задается максимум один раз, про первого левого ни разу. Количество вопросов не больше х-1.

Вау! Кажется у нас новый чемпион!!

Я еще не проверил, но выглядит очень похожим на правду. Красивый ответ из категории "ну как я сам-то сразу не догадался!?"

[Буратино]

Вопросов будет гораздо больше чем 22. Скорее 33-34

[Буратино]

Сорри коррекция вопросов будет не 34 а 44.

[perkins]

для трех схема рабочая
ШПП: 11, 01
ПШП: 01, 00
ППШ: 10

для пяти:
ШШППП: 1111, 0011, 0111, 1011
ШПШПП: 1011, 0011, 1001, 0001
ШППШП: 1101, 0101, 1100, 0100
ШПППШ: 1110, 0110
ПШШПП: 0111, 0011, 0001, 0101
ПШПШП: 0101, 0000, 0001, 0100
все варианты не расписывал, но одинаковые варианты ответов дают разные комбинации Ш и П. Да, находится П, но кто есть П, а кто Ш сказать точно нельзя.

[Буратино]

У меня по моему есть более оптимальное доработаю и выложу. должно быть в районе 30 вопросов.

[Lisa]

Вопрос задачи найти хотя бы одного П. Определять принадлежность всех не требуется.