Итак, задача:
На шляпах (или на лбу) у нескольких людей (Артур, Бертран,...) написаны натуральные числа — так, что каждый видит все числа, кроме своего собственного. А на доске написаны варианты их суммы, среди которых один правильный.
Например, пусть у участников на шляпах написаны просто три двойки — 2, 2, 2, — а на доске написаны 6, 7 и 8.
На шляпах (или на лбу) у нескольких людей (Артур, Бертран,...) написаны натуральные числа — так, что каждый видит все числа, кроме своего собственного. А на доске написаны варианты их суммы, среди которых один правильный.
Например, пусть у участников на шляпах написаны просто три двойки — 2, 2, 2, — а на доске написаны 6, 7 и 8.
Их много раз по кругу опрашивают: "знаете ли вы своё число", и ответы ("да" или "нет") слышны всем.
Нужно доказать, что если вариантов на доске не больше, чем людей (скажем, как в примере выше), то рано или поздно кто-нибудь ответит "да".
Нужно доказать, что если вариантов на доске не больше, чем людей (скажем, как в примере выше), то рано или поздно кто-нибудь ответит "да".
(И немедленно вспоминаются, конечно, классические задачи про проводника и пассажиров с закопчёнными после туннеля лицами, или про чужеземца и голубоглазых островитян.)
А рассуждение тут очень изящное. Авторы вводят слепого арбитра, Zoe, которой известны числа на доске и которая слышит все ответы участников — но которой неизвестно ни одно из чисел на шляпах. И она ведёт таблицу возможных вариантов наборов — вычеркивая те, которые становятся невозможными после услышанных ответов.
Так вот, её таблица на самом деле хранит в себе всю информацию, собранную в результате предыдущих ответов — так что очередной отвечающий (допустим, Бертран) может просто посмотреть на неё, найти в ней наборы, совпадающие с видимыми числами им остальных участников, и понять, однозначно ли это определяет его число. Если такой набор один, он говорит "да", иначе "нет".
Соответственно, Zoe при очередном ответе "нет" одного из участников вычёркивает из таблицы те наборы, для которых в таблице нет других наборов, отличающихся от данного только на число этого участника:
(Картинка из той же статьи, и про саму статью я ещё скажу — ибо с ней тоже всё интересно.)
На этом рисунке подписаны, правда, только тройки на границе — но понятно, как оно продолжается внутрь. А числа, которыми подписаны вершины этой таблицы, это номер вопроса, на котором этот набор будет вычеркнут. Скажем, все варианты вида (0,b,8-b), идущие вдоль правой стороны этого "треугольника", будут вычеркнуты первым же вопросом к A. Вариант (7,0,1) не будет вычеркнут вопросом к A — но будет вычеркнут следующим за этим вопросом к B. А вариант (7,0,0) будет вычеркнут на третьем вопросе — ибо единственная альтернатива с точки зрения C, (7,0,1), только что исключена.
На этом рисунке подписаны, правда, только тройки на границе — но понятно, как оно продолжается внутрь. А числа, которыми подписаны вершины этой таблицы, это номер вопроса, на котором этот набор будет вычеркнут. Скажем, все варианты вида (0,b,8-b), идущие вдоль правой стороны этого "треугольника", будут вычеркнуты первым же вопросом к A. Вариант (7,0,1) не будет вычеркнут вопросом к A — но будет вычеркнут следующим за этим вопросом к B. А вариант (7,0,0) будет вычеркнут на третьем вопросе — ибо единственная альтернатива с точки зрения C, (7,0,1), только что исключена.
Тройка (2,2,2) — одна из четырёх (для сумм (6,7,8)), для которых, чтобы услышать "да", приходится задавать аж 19 вопросов:
Собственно, теперь уже легко доказать и общее утверждение. Только его проще доказывать в другую сторону — как утверждение "если есть конфигурация наборов в N-мерном пространстве, таких, что для любого набора и любой координаты есть набор, отличающийся от первого лишь по этой координате, то сумма координат принимает по меньшей мере N+1 значение". Каковое утверждение достаточно применить к той части таблицы Zoe, которая никогда не будет вычеркнута, и получить противоречие.
И доказательство легко проводится по индукции по размерности (количеству участников) N. А именно — выделяем одну из координат (например, первую), и смотрим на наборы из конфигурации, где она принимает наименьшее возможное значение a_0.
С одной стороны, по оставшимся (N-1) координате эти наборы обладают таким же свойством — поэтому уже там мы видим как минимум (N-1)+1=N различных сумм (к которым добавляется одно и то же a_0).
С другой — посмотрим на наибольшую из этих сумм и на соответствующий набор (a_0,b,c,...). По предположению на всю конфигурацию наборов, мы можем заменить первую координату в наборе и опять получить набор (a', b,c,...) из конфигурации. С другой стороны, a_0 было наименьшим возможным значением первой координаты, так что a'>a_0 и поэтому мы нашли ещё одну — ещё большую — сумму. И вот у нас и нашлись N+1 разная сумма, и доказательство завершено.
С другой — посмотрим на наибольшую из этих сумм и на соответствующий набор (a_0,b,c,...). По предположению на всю конфигурацию наборов, мы можем заменить первую координату в наборе и опять получить набор (a', b,c,...) из конфигурации. С другой стороны, a_0 было наименьшим возможным значением первой координаты, так что a'>a_0 и поэтому мы нашли ещё одну — ещё большую — сумму. И вот у нас и нашлись N+1 разная сумма, и доказательство завершено.
И — возвращаясь к самой статье. У неё три автора: Конвей, Патерсон и... Москва (СССР) (!) —
https://www.tandfonline.com/doi/full/10.1080/00029890.2020.1712168
https://www.tandfonline.com/doi/full/10.1080/00029890.2020.1712168
Taylor & Francis
A Headache-Causing Problem
After disproving the celebrated Conway–Paterson–Moscow theorem [1], we prove that theorem and make an application to a well-known number-theoretic problem.
Более того, если кажется, что это опечатка, и что-нибудь не туда вписали — так всё правильно: