Условие

100 мудрецов выстроены в колонну. На каждом колпак одного из 3 цветов. Каждый видит цвета колпаков впереди стоящих (но не свой и не задних). По очереди (начиная с задного) каждый называет цвет своего колпака; всех слышат. Кто не угадал — казнён.

Придумайте стратегию, спасающую максимум мудрецов гарантированно.

Подсказка: используйте остатки от деления на 3.

Решение

Идея

Сопоставим цветам числа: белый = 0, синий = 1, красный = 2. Тогда сумма «цветов» — это число по модулю 3.

Стратегия

Первый (задний) мудрец — единственный, кого нельзя гарантированно спасти, потому что он не видит ничьих колпаков, кроме впередистоящих, и его никто не подсказывает. Он жертвует собой ради передачи информации.

Он считает сумму чисел всех 99 видимых колпаков по модулю 3 и называет цвет, соответствующий этому остатку. Например, если сумма = 47, то 47 mod 3 = 2, он говорит «красный».

Его собственный цвет угадан с вероятностью 1/3.

Что делает 2-й (99-й сзади)

Он видит впереди 98 колпаков. Знает:

Сумма всех 99 (своего + видимых) по модулю 3 = что сказал первый.
Сумма 98 видимых.

Значит, его цвет = (сумма_первого - сумма_98) mod 3. Он называет этот цвет — гарантированно правильный.

Что делает 3-й

Он слышал ответы 1-го и 2-го. Знает:

Свой цвет + цвет 2-го + сумма 97 видимых = сумма_первого mod 3.
Сумма 97 видимых ему известна.
Цвет 2-го — его слышали.

Решает уравнение → знает свой цвет. Гарантированно правильно.

Итог

Мудрецы 2..100 спасены гарантированно — 99 мудрецов. Мудрец 1 — с вероятностью 1/3.

Ожидаемое число выживших: 99 + 1/3 ≈ 99.33.

Обобщение

Для k цветов и n мудрецов спасают n − 1 гарантированно (используют остатки по модулю k).

Псевдокод

# Сторона казни:
def sage_1_speak(visible_99):
    s = sum(visible_99) % 3
    return color_by_number(s)   # например 'красный'
 
def sage_i_speak(i, prev_answers, visible):
    # prev_answers — что сказали с 1-го по (i-1)-й
    # visible — цвета колпаков 100-i впереди стоящих
    parity_announced = number_of(prev_answers[0])     # что сообщил первый
    sum_so_far = sum(prev_answers[1:])                # цвета 2..i-1, угаданные точно
    sum_visible = sum(visible)                        # цвета i+1..100
    my_color = (parity_announced - sum_so_far - sum_visible) % 3
    return color_by_number(my_color)

Подводные камни

«Спасти всех 100» — невозможно: первый мудрец не имеет информации о своём колпаке.
Стратегия «один говорит цвет следующего» — спасает половину; не оптимально.
Только 2 цвета — известная задача, тоже через сумму mod 2 (чётность). 3 цвета — обобщение.
Не каждый «слышит всех» — в задаче подразумевается, что слышат всех; иначе стратегия рушится.

Эталонный ответ

Гарантированно спасаются 99 мудрецов, первый — с вероятностью 1/3.

Кодируем цвета числами 0, 1, 2. Первый мудрец называет цвет, соответствующий сумме mod 3 всех видимых им 99 колпаков. Каждый последующий вычисляет свой цвет, зная объявленную сумму и слышимые ответы.

Логика — 100 мудрецов и 3 цвета колпаков: спасти максимум