Решён
Задача о говорящих попугаях (Турлом, 2015) - решение

Олег Статистик • Математика •
3.6k
4

Помогите разобраться с задачей из книги Турлома 2015 года про говорящих попугаев.

Условие (вкратце): Есть 100 попугаев, каждый либо всегда говорит правду, либо всегда лжет. Их рассадили в ряд. Каждого попугая спросили: "Сколько лжецов сидит левее тебя?". Первый ответил 0, второй - 1, третий - 1, четвертый - 2, и так далее по определенной последовательности.

Вопрос: сколько среди них было лжецов?

Не могу понять логику. Если честный попугай говорит правду про количество лжецов слева, то как быть с тем что ответы не строго возрастают?

ЗадачиЛогикаМатематикаОлимпиада

4 ответа

Лучшие Новые Старые
Решение
83
Эксперт • 1 ответ

Ключ к решению - понять что говорит каждый тип попугая.

Пусть на позиции i сидит попугай, и слева от него реально L лжецов.

  • Если попугай правдивый: он скажет L (правду)
  • Если попугай лжец: он скажет любое число кроме L (ложь)

Теперь заметим важную вещь: если попугай сказал число k, и k совпадает с реальным количеством лжецов слева от него, то он правдивый. Если не совпадает - лжец.

Алгоритм:

  1. Проходим слева направо
  2. Поддерживаем счетчик реальных лжецов слева (изначально 0)
  3. Для i-го попугая: если его ответ = текущему счетчику, он правдивый. Иначе - лжец, увеличиваем счетчик на 1
  4. Переходим к следующему

В итоге считаем общее количество лжецов.

Без конкретной последовательности ответов дальше решить не могу, но логика такая.

Аватар Олег Статистик
Олег Статистик Автор

Спасибо огромное! Теперь понял, буду пробовать на конкретных числах

31
Участник • 1 ответ

Можно проще объяснить.

Если попугай говорит "слева от меня 5 лжецов", и это правда, значит он честный. Если это ложь, значит он сам лжец, и тогда слева от него НЕ 5 лжецов, а какое то другое число.

Последовательно проверяя каждого попугая и считая накопленное количество лжецов, можно определить тип каждого.

22
Эксперт • 1 ответ

У меня есть питоновский скрипт который решает такие задачи перебором. Если дашь конкретную последовательность ответов попугаев, могу прогнать.

def solve_parrots(answers):
    liars_count = 0
    liars = []
    for i, answer in enumerate(answers):
        if answer == liars_count:
            # Truth-teller
            liars.append(False)
        else:
            # Liar
            liars.append(True)
            liars_count += 1
    return liars_count, liars

Принцип работы: если ответ совпадает с текущим счетчиком лжецов, попугай честный. Иначе лжец, счетчик +1.

0
Участник • 3 ответа

не могу понять условие задачи, там все 100 попугаев опрашивают или только часть??

Написать ответ

Визуальный редактор (WYSIWYG)
Премодерация гостей

Вы отвечаете как гость. Ваш ответ будет скрыт до проверки модератором. Чтобы ответ появился сразу и вы получали репутацию — войдите в аккаунт.

Или войдите в систему
Будьте вежливы и соблюдайте правила платформы.