Математические байки – Telegram
Математические байки
4.3K subscribers
1.44K photos
15 videos
27 files
914 links
Рассказы про разную математику.

Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
Download Telegram
Так вот, её таблица на самом деле хранит в себе всю информацию, собранную в результате предыдущих ответов — так что очередной отвечающий (допустим, Бертран) может просто посмотреть на неё, найти в ней наборы, совпадающие с видимыми числами им остальных участников, и понять, однозначно ли это определяет его число. Если такой набор один, он говорит "да", иначе "нет".
Соответственно, Zoe при очередном ответе "нет" одного из участников вычёркивает из таблицы те наборы, для которых в таблице нет других наборов, отличающихся от данного только на число этого участника:
И вот как выглядит таблица для набора сумм (6,7,8) —
(Картинка из той же статьи, и про саму статью я ещё скажу — ибо с ней тоже всё интересно.)

На этом рисунке подписаны, правда, только тройки на границе — но понятно, как оно продолжается внутрь. А числа, которыми подписаны вершины этой таблицы, это номер вопроса, на котором этот набор будет вычеркнут. Скажем, все варианты вида (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 разная сумма, и доказательство завершено.
Более того, если кажется, что это опечатка, и что-нибудь не туда вписали — так всё правильно:
На самом деле — эта статья исходно была написана в 1977 году, и появилась в сборнике, изданном "частным образом" в подарок Ленстре:
А пару лет назад Дирк Шляйхер уговорил Конвея её издать и "для широкой публики" — так что она вышла в American Math. Monthly.

Вот тут — https://blog.tanyakhovanova.com/2008/08/a-math-paper-by-moscow-ussr/ — запись 2008 года в блоге Татьяны Ховановой, посвящённая этой статье; там можно увидеть фотографию Конвея, ищущего свой оттиск этой статьи, и собственно скан того оттиска:
http://www.tanyakhovanova.com/BlogStuff/Conway/Headache.pdf
Ну и — благодарности смотрятся отдельно прекрасным образом:
Вчера было сто лет со дня смерти Рамануджана —