Основные термины, понятия и обозначения

Среди свойств разбиений чисел на части можно указать одно, не называемое другими авторами, которое в ряде случаев оказывается весьма полезным. Речь идет о свойстве разбиений числа, закрепляющем за конкретными слагаемыми подмножества позиций (точек) дискретной плоскости, в котором эти слагаемые могут перемещаться, не выходя за его пределы.

Например, рассмотрим такую задачу. Имеется 2 спицы длиной 12 ед и 7 шаровых бусин с диаметрами 2,2,2,3,3,4,4 ед и с двумя просверленными под углом сквозными отверстиями, проходящими через центры бусин. Как распределить и нанизать бусины на спицы, чтобы все позиции спиц были заполнены, а спицы образовали Х или V подобную симметричную фигуру?

Очевидно, все 8 позиций закреплены на спицах. Для решения задачи можно воспользоваться разбиениями числа 12 либо 11 на 4 части. По два таких разбиения с учетом диаметров бусин имеют вид: а = 2,2,4,4; b = 2,3,3,4. или а = 2,2,3,4; b = 2,2,3, 4. Поскольку бусин всего 7, то одна бусина должна быть общей для этой пары разбиений. Это может либо 2, либо 4. Тогда получаем решения b = 3,3,4,2, а для разбиения (а) переставляем слагаемые (меняем позиции бусин, сохраняя исходную сумму) а = 2,4,4,2. Пересечение спиц возможно в 4-й предпоследней бусине или в последней 2.

Нам потребуются несколько определений:

Определение 1. Разбиением целого положительного числа n называется представление n в виде суммы целых положительных чисел: n = х1+ х2 + х3 +…+ хk, хi > 0, i =1(1)k.      

Определение 2. Неупорядоченное разбиение n на k частей – представление n суммой, где слагаемые выписаны в убывающем порядке n = х1 + х2 + х3 +…+ хk, х1 ≥ х2 ≥ х3 ≥…≥ хk ≥ 1. 

Определение 3. Количество разбиений –это число решений р_k(n) в целых положительных хi уравнения р_k(n) = р_k(n – k) + р_k-1(n – k)+ р_k-2(n – k) +…+ р_k=1(n – k), р_k(n) = 0, для n< k,  р_k(k) = 1.

Задача о шестиугольнике (гексагоне) и её характеристика

Наряду с магическими квадратами разных порядков можно рассматривать не квадраты, а, например, магические шестиугольники (гексагоны). Постановка задачи остается в принципе такой же, но линии называются иначе (не вертикали, горизонтали или диагонали). Число ячеек шестиугольника (гексагона) порядка n вычисляется по формуле n = 3 и может содержать числа от 1 до 3n² – 3n + 1. Шестиугольник 3-го порядка имеет в центре одну соту, внутреннее кольцо из 6 сот и внешнее кольцо из 12 сот, всего 19 сот. Сота шестиугольная ячейка. Сумма всех чисел в гексагоне

S = (3n² – 3n + 1)( 3n² – 3n +2)/2

другой стороны, есть 2n –1 рядов (например, вертикальных), которые включают в себя все числа в шестиугольнике. Так как сумма чисел в каждом ряду равна M то общая их сумма во всём шестиугольнике будет S = M (2n – 1). Приравняв суммы, получим, что   32M = 72n³ – 108n² + 90n – 27 + 5/(2n – 1)

Слева от равенства стоит целое число. Значит, справа должно тоже быть целое число.     

Значит, дробь 5/(2n –1) — это целое число, что возможно только при n = 1 и n = 3.            В этом и заключается доказательство единственности решения задачи о гексагоне с n = 3.

Полученная фигура n = 3 имеет три направления, связывающие противоположные вершины шестиугольника. Каждое направление содержит по 5 сот, размещенных вдоль прямой линии, проходящей через центральную соту фигуры. Параллельно рядам из пяти сот к ним примыкают с обеих сторон ряды из четырех сот (2 ряда) и затем из трех сот (2 ряда). Всего 15 рядов, образованных 19 сотами. Эти ряды заполняются натуральными числами от 1 до 19.

Задача состоит в заполнении всех 19 сот шестиугольной фигуры этими числами, но так, чтобы сумма чисел в сотах вдоль каждого из 15 рядов (линий) была постоянной, равной М = 2·19 = 38. Решение существует и, как оказалось, оно единственное.  

Обобщение задачи видится в повышении порядка n, т.е. в добавлении внешних колец из таких же шестиугольных сот. Неизвестно, существуют ли канонические фигуры большего порядка. Много ограничивающих условий, которые должны выполняться. Математики поднапряглись и кое-что им удалось отыскать. К сожалению, найденные фигуры названы аномальными, так как их заполнение числами начинается не с 1.

Примеры некоторых аномальных фигур приводятся ниже, они также вызывают интерес.

Наибольший из известных на данный момент гексагон поpярка n = 8, начинающийся с −84 и кончающийся +84 был создан Louis K. Hoelbling 5 февраля 2006 года. Этот Луис проявил настойчивость и через полтора года выдал новый гексагон:

История поиска решения

Житель Флориды Клиффорд Адамс с 1910 по 1957 годы занимался решением этой задачи для n = 3, которую вычитал в газете, (ЭВМ тогда просто не было) в свободное время на протяжении 47 лет и решил ее.

Решение представляет нетривиальный процесс. Его поиск сложнее нежели для магического квадрата, формул и правил для заполнения сот шестиугольника я не встречал, но было бы интересно ознакомиться если кто-то знает о них. Чтобы привлечь компьютер, нужна программа и алгоритм. О них авторы не пишут. В сети много чего написано об этом шестиугольнике, приводится готовое решение, но никто не рассказал. как же его получить, как можно правильно заполнить соты фигуры в соответствии с требованиями задачи. Клиффорд построил заполнение фигуры, перебирая варианты, и ему здорово повезло, всего через 47 лет встретился окончательный вариант. Вопрос о правилах расстановки чисел в сотах, удовлетворяющих требованиям задачи, на мой взгляд самый интересный и самый трудный. Попробуйте самостоятельно заполнить гексагон. Адамс Клиффорд не был глупым человеком и потратил около 50 лет на поиск решения, нашел его. Я сознательно не привожу окончательное решение. Хочу, чтобы Вы самостоятельно сумели заполнить все соты-ячейки 19 цифрами и удовлетворить требованиям к такому заполнению. Думаю, что изложенное здесь поможет вам в этом.

Успехов Вам.

Предлагаемый вариант решения

Перед собой я поставил задачу, рассказать как раз о правилах заполнения сот гексагона числами от 1 до 19.

Эти правила я не вычитал где-то, а выработал (придумал) самостоятельно. Возможно, они не лучшие, но они мои. Они позволяют самостоятельно заполнить фигуру за один вечер. Louis K. Hoelbling опубликовал вторую фигуру через полтора года, а сколько времени ушло на первую мы не знаем. При этом компьютеры уже имелись практически в каждом доме.

Так как гексагона второго порядка не существует, начнем с незаполненного шестиугольника 3-го порядка. Две пары чисел n = 2 с одинаковой суммой в кольце должны быть смежными и одно число (вершина) общее в паре. Но, как известно, таких пар не существует.

Заполнение числами внешнего кольца гексагона. Для решения задачи заполнения числами гексагона будем рассуждать и действовать так.

Соты внешнего кольца образуют контур шестью тройками чисел, сумма которых должна быть равна 38. Для этих троек требуются всего 12 чисел из 19, 6 из них располагаются в вершинах фигуры, т.е. эти числа принадлежат парам смежных троек. Они входят в две суммы. Еще 6 чисел являются средними числами в тройках внешнего кольца. Эти числа также используются в двух суммах: для троек и четверок. Можем ли мы отыскать нужные тройки? Как это сделать? Замечание: всех разбиений числа 38 существует р_k(n = 38) = 26015.

Оказывается, это вполне возможно, зная некоторые математические результаты из комбинаторного анализа. Надо число 38 разбить на 3 части способами (вариантами), не содержащими одинаковых чисел в пределах одной тройки. (Кто-то из авторов Хабра писал об алгоритме и программе разбиения чисел. Здесь он и другие читатели могут применить плоды трудов своих.) Требование однократности использования чисел при заполнении сот фигуры задается в условиях задачи. Среди полученных троек чисел отобрать такие, которые в крайних сотах (смежных пар троек) будут иметь совпадающие значения.

Первая вершина внешнего кольца. Допустим, что в одной из вершин фигуры помещается число (цифра) 1 (малые числа буду иногда называть цифрами). Она (возможно) должна быть в соте внешнего кольца и в двух тройках крайним числом, общим для двух смежных троек. В таблице ниже приведен фрагмент списка разбиений числа 38 на три части, из которого видим, что 1 содержит лишь одна допустимая тройка (в ней разные числа, меньшие 20 с суммой 38), а также и число 2 содержится лишь в одной допустимой тройке. Это тройки: 1,18,19; 2,17,19. Этим тройкам предшествуют тройки с числом 20, что недопустимо. За тройкой 2,17,19 следует 2,18,18 с суммой 38, но в ней тоже нарушается требование (два раза 18) задачи, и ее отвергаем.

Этому разбиению 1,18,19 предшествует тройка 1,17,20; а за ним следует 2,2,34, обе недопустимые. Для тройки, содержащей 2,17,19 цифру 2, тройки до нее и после недопустимы. Следовательно, внешнее кольцо не может содержать в сотах ни 1, ни 2. А тройку?

С тройкой как раз, все хорошо. В таблице имеется пара допустимых троек 3, 16, 19; 3,17,18, содержащих цифру три, которую можно поместить в вершину фигуры, общую для этих двух троек. Для этой пары троек имеем 4 возможных конфигурации размещения 5 чисел: а=19,16,3,17,18; b =19,16,3,18,17; c = 16,19,3 17,18; d =16,19,3,18,17. Вычеркивание объясняется позже. Какая конфигурация из 4-х будет реализована пока неизвестно. Другими вершинами внешнего кольца могут быть, вообще говоря, 4 числа 16,17,18, 19. Таким образом, ни 1, ни 2 не могут попасть в соты внешнего кольца фигуры, а цифра 3 допустима. Вообще желательно подбирать ряды-разбиения из чисел такими, чтобы возможности замен позициями были как можно более широкими.

Закрепление еще двух вершин. Теперь рассмотрим разбиения числа 38 на 5 частей. Фигура содержит три линии, вдоль каждой по прямой располагаются по 5 сотовых позиций. Сумма чисел в каждой 5-ке сот должна быть равна также числу 38. Поскольку эти три пятерки пересекаются в центральной соте фигуры, число, вписываемое в центральную соту, должно присутствовать во всех трех этих разбиениях на 5 частей. В одной из пятерок должна включаться цифра 3. Всего в трех пятерках разбиений 15 чисел, одно из них (для центра) встречается три раза. Какое это число пока неизвестно. Следовательно, остальные 12 чисел могут включаться в пятерки только однократно и быть различными, не превышая числа 19. Желательно выбор сделать таким, чтобы числа, вошедшие в пару уже выбранных троек, не включались в две пятерки, но при этом присутствовали в пятерках, не содержащих цифру три. Исключение можно сделать для чисел потенциальных вершин из 3,16,17,18,19, которые будут совпадать с числами троек. В пятерках разбиений они могут присутствовать однократно. Понятно, цифры 1 и 2 должны быть включены в 5-ки. С них и начнем. Фрагмент списка разбиений числа 38 на 5 частей приведен в таблице 2.

Заметим, что направления рядов пятерок связывают пары противоположных вершин фигуры. Следовательно, выбор пятерок уточнит числа, помещаемые еще в две вершины фигуры выбранной парой смежных троек. Вершина, содержащая тройку, считается закрепленной. Итак, создаем пятерки чисел по трем направлениям. Поскольку цифры 1 и 2 не используются во внешнем кольце, они будут присутствовать во внутреннем кольце сот.
Начнем с 1. Сформируем по аналогии (как для троек) фрагмент таблицы разбиений

Подходящие допустимые пятерки: 1,4,5,9,19; g = 1,4,5,10,18; оставляем пока обе 5-ки. Продолжим список 5-ок, но с включением в их состав цифры 2. Такие допустимые подходящие 5-ки получают вид: 2,5,6,8,17; h = 2,5,6,9,16. Вторая из 2-х пятерок (с 2) конфликтует (содержит число 9) с первой 5-ой, содержащей 1 и 9. Эту 5-ку удаляем (вычеркиваем), оставляем вторую (с 1) они в таблице выделены заливкой. После такого выбора однозначно выбираются вершины в паре троек (подходящей из 4-х а=19,16,3,17,18; b =19,16,3,18,17; c = 16,19,3 17,18; d =16,19,3,18,17) конфигурацией пары троек оказалась «с» = 16,19,3,17,18): слева закрепляем вершину 16, а справа –18. Однозначно определяются и средние числа в паре троек – это 19 слева и 17 справа. Пока все идет достаточно гладко. Осталось определить 5-ку с вершиной 3. В таблице 2 видим допустимая пятерка следует за 5-ой с двумя семерками (выделена заливкой) цифры 7 и 8 ранее не встречались, что влияет на выбор 5-ки. Состав этой 5-ки: k = 3,5,7,8,15, ее компоненты не пересекаются с 5-ми, выбранными ранее, кроме цифры 5 для центральной соты. Две позиции этой 5-ки (k) определены однозначно. Это 3 и 5. В двух других 5-ах аналогично. Их составы пересекаются с тройками в сотах вершин 16 и 18, которые мы уже определили. Итак, установлены 3 вершины из 6 и центральная позиция (5), а также центральные позиции пары троек. Остальные числа выбранных рядов распределены по рядам, но не по позициям в сотах.

Вернемся к генератору троек. Будем отыскивать пару новых троек внешнего кольца (смежные в вершинах (16) и (18)) с предыдущими тройками. Этот факт упрощает определение допустимой пары троек. В таблице разбиения числа 38 на три части пара этих троек внесена в конце таблицы: s = 9, 11, 18; t =10, 12, 16. Кроме фиксированных вершин 16 и 18   новые тройки обязаны иметь общие числа с пятерками g и h, содержащими в составах еще две вершины. Такими числами могут быть 4, 6, 9, 10. Цифры 1 и 2 вершинами быть не могут.   Общий элемент (18) тройки s и g 5-ки должен быть вершиной фигуры, также как и элемент (16) тройки (t) и пятерки (h). Аналогично общие числа новых троек и пятерок g и h должны стать вершинами (9) и (10) (используются эти уже выбранные ряды). В новых тройках s и t определяются и средние элементы: слева (12) и справа (11). Таким образом, определены 5 вершин фигуры из 6-ти, 4 тройки из 6 определены полностью.

Последняя вершина гексагона. Замкнем внешнее кольцо выбором последней пары троек. Эти тройки должны содержать 5 чисел: 9 и 10, и пока нигде не проявившиеся 13,14,15. Одно число из последних трех должно стать последней вершиной фигуры и войти в состав обеих последних троек: 9,14,15; 10,13,15 (они в табл.1 в конце без заливки). Теперь ясно, что последняя вершина 15 фигуры вписывается в соту. Число 13 слева, а 14 справа – средние числа в тройках. Поскольку вершины инцидентны всегда двум тройкам (смежным) для вершины 10 вторая тройка – 10,13,15; а для вершины 9 вторая тройке – 9,14,15. Эти тройки пересекаются в элементе 15, следовательно, это 6-я вершина фигуры. Действительно число 15 входит в состав 5-ки k = 3,5,7,8,15 и в ней однозначно теперь определены три элемента из 5. Средние элементы последней пары новых троек: слева (13) и справа (14).

Заполнение внутреннего кольца. Внешнее кольцо замкнулось. Осталось разобраться со средним кольцом. Состав чисел этого кольца определен полностью как разность множества всех 19 чисел и чисел внешнего кольца с учетом (5) в центре. Состав представлен тремя парами 1,4; 2,6; и 7,8, определяемыми тремя пересекающимися рядами пятерок. За парами чисел закреплены пары сот в пятерках. Числа в паре можно переставлять (суммы в 5-ах при этом не изменятся). Для того, чтобы в рядах четверок также выполнялось условие постоянство сумм, числа перечисленных пар возможно потребуется поменять местами. На этом все, гексагон заполнен.                                                       

Трудности процесса решения. Остановлюсь на трудностях поиска решения. Генераторы разбиений числа удобно строить с лексикографическим порядком слов-разбиений. Генераторы могут быть двух типов: первые разбивают число на все возможные части, что перемешивает слова разбиений с разным числом частей; вторые – разбивают число на заданное количество частей (все слова имеют одну длину). Списки результатов получаются огромными и просматривать их, не понимая до конца, что нужно отыскивать проблематично. Например, разбиения 38 на 5 частей имеют лексикографические номера: № 22243 (код 16 9 6 5 2); №23820 (код 18 10 5 4 1); №21071 (код 15 8 7 5 3). А число 38 на 3 части имеют следующие лексикографические номера:

Заключение

На Хабре мне встречались работы по разбиениям числа, это были попытки алгоритмизации и программирования. Могу дать совет начинающим, ознакомьтесь до начала своей работы с тем [3,4, 18,33,28], что сделано до вас, разберитесь и, если чувствуете в себе потребность приложить усилия, то я рекомендовал бы это делать в области разбиений множеств, так как для чисел уже очень многое сделано и вы в лучшем случае повторите уже готовое. Но то, что готовое делали профессионалы. Своей цели я достиг - изложил, что было задумано. Насколько хорошо судить вам.