Математические байки

И доказательство легко проводится по индукции по размерности (количеству участников) N. А именно — выделяем одну из координат (например, первую), и смотрим на наборы из конфигурации, где она принимает наименьшее возможное значение a_0.

Собственно, теперь уже легко доказать и общее утверждение. Только его проще доказывать в другую сторону — как утверждение "если есть конфигурация наборов в N-мерном пространстве, таких, что для любого набора и любой координаты есть набор, отличающийся от первого лишь по этой координате, то сумма координат принимает по меньшей мере N+1 значение". Каковое утверждение достаточно применить к той части таблицы Zoe, которая никогда не будет вычеркнута, и получить противоречие.

Тройка (2,2,2) — одна из четырёх (для сумм (6,7,8)), для которых, чтобы услышать "да", приходится задавать аж 19 вопросов:

(Картинка из той же статьи, и про саму статью я ещё скажу — ибо с ней тоже всё интересно.) На этом рисунке подписаны, правда, только тройки на границе — но понятно, как оно продолжается внутрь. А числа, которыми подписаны вершины этой таблицы, это номер вопроса, на котором этот набор будет вычеркнут. Скажем, все варианты вида (0,b,8-b), идущие вдоль правой стороны этого "треугольника", будут вычеркнуты первым же вопросом к A. Вариант (7,0,1) не будет вычеркнут вопросом к A — но будет вычеркнут следующим за этим вопросом к B. А вариант (7,0,0) будет вычеркнут на третьем вопросе — ибо единственная альтернатива с точки зрения C, (7,0,1), только что исключена.

И вот как выглядит таблица для набора сумм (6,7,8) —

Соответственно, Zoe при очередном ответе "нет" одного из участников вычёркивает из таблицы те наборы, для которых в таблице нет других наборов, отличающихся от данного только на число этого участника:

Так вот, её таблица на самом деле хранит в себе всю информацию, собранную в результате предыдущих ответов — так что очередной отвечающий (допустим, Бертран) может просто посмотреть на неё, найти в ней наборы, совпадающие с видимыми числами им остальных участников, и понять, однозначно ли это определяет его число. Если такой набор один, он говорит "да", иначе "нет".

А рассуждение тут очень изящное. Авторы вводят слепого арбитра, Zoe, которой известны числа на доске и которая слышит все ответы участников — но которой неизвестно ни одно из чисел на шляпах. И она ведёт таблицу возможных вариантов наборов — вычеркивая те, которые становятся невозможными после услышанных ответов.

(И немедленно вспоминаются, конечно, классические задачи про проводника и пассажиров с закопчёнными после туннеля лицами, или про чужеземца и голубоглазых островитян.)

Их много раз по кругу опрашивают: "знаете ли вы своё число", и ответы ("да" или "нет") слышны всем. Нужно доказать, что если вариантов на доске не больше, чем людей (скажем, как в примере выше), то рано или поздно кто-нибудь ответит "да".

Картинка из статьи —

Итак, задача: На шляпах (или на лбу) у нескольких людей (Артур, Бертран,...) написаны натуральные числа — так, что каждый видит все числа, кроме своего собственного. А на доске написаны варианты их суммы, среди которых один правильный. Например, пусть у участников на шляпах написаны просто три двойки — 2, 2, 2, — а на доске написаны 6, 7 и 8.

Возвращаясь к Конвею — давайте я расскажу о его статье под очень точным названием "A Headache Causing Problem".

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