Задача про 12 шашек

ЗАДАЧА ПРО 12 ШАШЕК

РАЗМЕСТИТЬ 12 ШАШЕК НА ПЛОСКОСТИ В
19 РЯДОВ ПО 3 ШАШКИ В КАЖДОМ РЯДУ.

Эта задача исключительно проста и доступна по формулировке,
но необъятна по глубине. В этом смысле ее можно поставить в один ряд
с классическими проблемами и головоломками, над которыми билось не
одно поколение ученых и энтузиастов.
В более строгой математической постановке задача выглядит
следующим образом. Определить на плоскости 12 точек и 19 отрезков
так, чтобы каждый отрезок содержал ровно 3 точки из этих двенадцати
и чтобы пересечение любых двух отрезков было одноточечно или пусто.
Удобно считать, что концы отрезков лежат в тех же 12 точках.
Задачу про 12 шашек, в общем, можно считать решенной, но
осталась масса сопутствующих вопросов, на большинство из которых
до сих пор нет ответа.
Сразу возникает вопрос: почему именно 12 шашек, а не больше
и не меньше?
Действительно, вариации задачи для 9, 10, 11 рядов тоже
интересны. И может быть, именно с простых случаев надо начать, чтобы
подступиться к более сложному. Но все известные решения упрощенных
задач получаются из решений основной задачи выкидыванием лишних
шашек. Ни логика, ни компьютерный перебор не помогли найти в
упрощенных задачах ничего оригинального, что не было бы частью
общего решения.
С другой стороны, добавление шашек тоже не дает ничего
нового, кроме того, что шашки норовят разместиться где в 4, где в 5
рядов и т.д. С новой шашкой можно образовать две новые линии, но нет
ничего удивительного в том, что две прямых пересеклись. Удивительно,
когда три прямых, появившихся из разных источников, пересекаются все
в одной точке. В то же время не удалось строго доказать, что для
большего набора шашек не существует никаких оригинальных содержательных
конструкций.
По-видимому, именно 12 шашек и 19 рядов характеризуют некое
фундаментальное свойство плоскости (отражающее максимальную жесткость
плоских решетчатых конструкций). Трехмерное пространство имеет свои
показатели. (К этому вопросу мы еще вернемся.)

Впервые задачу про размещение шашек на плоскости в ряды по 3
штуки в каждом опубликовал Г.Винокуров в 1986 г. Однако он предложил
ее для 11 шашек, причем полагал, что максимально из них можно
образовать только 13 рядов. Очень скоро ищущий народ обнаружил
расположения в 14 и 15 рядов, а позже выяснилось, что можно собрать
даже 16 рядов. Хотя Г.Винокуров не заметил сразу всю глубину посетившей
его идеи, тем не менее он по праву может считаться ее автором,
поскольку все остальное развитие идет по накатанным логическим схемам,
а рождение идеи ничем не объяснимо.

Если найдено одно расположение шашек, то с помощью линейных
преобразований из него легко получить бесконечно много схожих
вариантов, как говорят, топологически эквивалентных, которые вряд
ли надо считать новым достижением. Есть различные признаки, которые
помогают быстро различать решения. Например, если при одном
расположении есть шашка, участвующая ровно в 3 рядах, а при другом
нет, то вы имеете дело с разными решениями.
Всего найдено 5 расположений, не сводящихся друг к другу
никакими преобразованиями. Вот они:

То же самое можно посмотреть в программе S12.COM.
Однако, кроме растяжений, существуют другие преобразования,
отличные от топологических, но не меняющие принципиальных показателей
расположения шашек. Любую крайнюю шашку рисунка можно "завести" в
бесконечность; там разорвать эту шашку, превратив ее ряды в
параллельные линии; а затем собрать эти линии с противоположного конца
в новую шашку. Такой прием от первого рисунка дает дополнительно 7
решений, от 2-го - 15, 3 - 23, 4 - 23, 5 - 25. Таким образом, всего
получается 98 решений. Часть из них показана в D12.COM, E12.COM, F12.COM
в процессе разрывов и в движении.
Произведен большой перебор, который вроде бы
закрывает все пути к иным решениям. Но не удалось сделать единую
программу, которая за ограниченное время произвела бы полный перебор.
Все 8 решений из первой серии (а именно: координаты шашек)
могут быть получены из единых формул (дробно-линейных функций от
двух переменных). Для остальных решений изредка попадаются формулы,
но общих, хотя бы для одной серии, не найдено.
Для контроля приводим координаты шашек на 1-м рисунке:
(0,2), (-1,0), (1,0), (0,0), (0,2/3), (-1/2,1), (-1/4,1), (-1/10,1),
(-2/9,10/9), (-1/7,8/7), (-2/11,10/11), (-1/9,8/9).
В общем, подсчет численных координат не слишком сложен.

Элементарно доказывается, что 12 шашек нельзя расположить
в 21 ряд. Допустим противное, тогда у каждой шашки поставим столько
птичек, во скольких рядах она участвует. Коль каждому ряду отвечают
3 птички, то всего их 63. Значит, хотя бы одна шашка дала 6 (или
более) птичек и входит по крайней мере в 6 рядов. Нарисуем эти 6
рядов и обнаружим на них... 13 шашек.
Однако не удалось доказать, что шашки нельзя расположить в
20 рядов. Здесь также произведен большой перебор, но нет достаточной
уверенности, что он закрыл все дыры.

Для трехмерного случая можно сформулировать задачу так.
Расположите в трехмерном пространстве 11 точек так, чтобы существовало
по возможности наибольшее количество плоскостей, в каждой из которых
содержалось бы ровно 4 указанных точки, не лежащих на одной прямой.
Найден вариант, когда таких плоскостей 34. Но не ясно,
является ли это пределом.
Может быть, вы найдете содержательные обобщения для
n-мерного пространства?

Невесенко Н.В.
12 ноября 2002 г.