14 ноября 2005 года
Разделим окружность на пять частей. Задача эквивалентна вписыванию в окружность правильного пятиугольника. Если у нас есть циркуль и линейка, то решение не очень сложное.
Опишем построение циркулем и линейкой:
- Проводим окружность с центром в точке O.
- Проводим диаметр AB.
- Восстанавливаем перпендикуляр CD к прямой AB в точке O. Для этого достаточно провести окружности с центрами в точках A и B с одинаковыми радиусами и провести прямую через точки пересечения этих окружностей.
- Аналогичным построением разделим отрезок AO точкой E пополам.
- Проведем окружность из точки E радиусом CE и найдем точку F пересечения с отрезком AB.
- CF — искомый отрезок, являющийся стороной вписанного пятиугольника.
Откладывая окружности с радиусом CF, мы разделим окружность на пять частей. Если провести построения аккуратно, хорошим циркулем, то деление получится точное. Доказательство этого факта оставим в качестве небольшого упражнения. Замечу, что для него нужно несколько раз применить теорему Пифагора, а также найти, чему равен sin 36°.
Те же самые построения можно выполнить, не используя линейки. По этой теме могу порекомендовать брошюру Геометрические построения одним циркулем из серии «Популярные лекции по математике».
Пробую зайти с другой стороны.
Пусть куски пронумерованы по возрастанию: 
.
На первом этапе выпишем всевозможные системы уравнений для разбиения на равные части. Для 
это будут разбиения на на 8, 7, 6 и 5 равных частей, дающих 4 группы из 7+6+5+4 = 22 уравнений.
Например, для решения из 16 кусков для первые 7 уравнений будут такими:
Вторые 6 уравнений:
(дальше не буду выписывать, надеюсь, понятно).
На этом этапе нашей задачей будет перебрать всевозможные такие системы уравнений, стараясь отсечь как можно больше бесперспективных вариантов. Например, если в системе попались уравнения 
, то её можно смело выкинуть, так как куски идут по возрастанию (даже если 
, ничто нам не мешает записать то же уравнение как 
). Далее, для разбиений на частей любая -я часть будет состоять минимум из двух кусков (уравнения вида исключаются).
Здесь мы ещё уравнения не решаем, поэтому выгодно записывать их более компактно, как собственно разбиения:
1234567887654321 — для первой группы уравнений (разбиение на 8 частей), назовём его 8-разбиением.
1123245672765143 — для второй группы уравнений (разбиение на 7 частей), назовём его 7-разбиением, и т.д..
и перебирать символьные строки по определённым правилам.
Я пока дошёл только до этого этапа, и то для разбиений не более чем на 7 частей из не более чем 13 кусков. Я сконцентрировался на 7 частях и 13 кусках, дальше будет только про этот вариант.
После указанных оптимизаций у меня получилось 740 возможных 7-разбиений тринадцати кусков, 6-разбиений — 87, 5-разбиений — 11972 и 4-разбиений — 54473. Пока что слишком много, чтобы перебирать их всевозможные сочетания, поэтому нужен дополнительный этап оптимизации.
На втором этапе планируется группировать найденные -разбиения друг с другом, сначала по парам, жадно ища противоречия. Например, 5-разбиение 1234441221553 несовместимо с 6-разбиением 1123455514326, так как выделенный набор 444 весит меньше, чем выделенный набор 555 (в силу того, что куски идут по возрастанию), хотя первый составляет пятую часть торта, а второй — шестую. Затем группируем по тройкам, и т.д, пока не получим полные наборы разбиений, кажущиеся непротиворечивыми. Совершенно непонятно, сколько можно будет выгадать на такой оптимизации. Если не слишком много, то придётся начинать решать системы уравнений совместно друг с другом, не сгенерировав предварительно всё множество систем.
На третьем этапе вспомним, что разбиения задают системы уравнений и проверяем, какие системы имеют решение. Для этого последнее уравнение, определяющее, что сумма кусков равна единице, мы не привлекаем, а просто ищем те системы из 22-уравнений с 13-ю неизвестными, у которых ранг меньше максимального (то есть 12). Здесь тоже возможна оптимизация, мы ведь можем сначала проверить систему из первых 6+5+4=15 уравнений (не более миллиарда случаев), и если у неё ранг уже 13, то дальше искать нет смысла.
Преимущество такого подхода в том, что он действительно перебирает всевозможные варианты разбиений и позволяет строго доказать, что решения нет (ну, если мы в погоне за оптимизацией перебора не отсекли лишнего), или, если оно есть, находит его.
