Как расставить 14 чисел в наборах из троек и четверок

[AlexSam]

Как расставить (если возможно) 14 чисел в наборы из 2-х троек и 2-х четверок, так чтобы числа в одном наборе в тройках и четверках не повторялись и каждое число встречалось с другим числом не более одного раза? Если такая расстановка существует, то должно быть 5 наборов чисел. Другая задача расстановки от 1 до 16 решается просто, а с 14 проблемы (и с 13 тоже). ИИ с задачей не справляется.

(1, 2, 3, 4)
(5, 6, 7, 8)
(9, 10, 11, 12)
(13, 14, 15, 16)

(1, 5, 9, 13)
(2, 6, 10, 14)
(3, 7, 11, 15)
(4, 8, 12, 16)

(1, 7, 12, 14)
(2, 8, 11, 13)
(3, 5, 10, 16)
(4, 6, 9, 15)

(1, 6, 11, 16)
(2, 5, 12, 15)
(3, 8, 9, 14)
(4, 7, 10, 13)

(1, 8, 10, 15)
(2, 7, 9, 16)
(3, 6, 12, 13)
(4, 5, 11, 14)

Это 5 наборов для 16 чисел. Но получить из этих наборов тройки и четверки не смог.

[Combat Zone]

Хоть как. Расставьте по порядку.
Скорее всего, вы неправильно понимаете условие задачи, потому что 3+3+ 4+ 4 это и есть 14.
И вангую, в задаче просили не предъявить способ расстановки (это слишком легко). А найти число таких способов, которые описаны в условии. Да?

Комбинаторная задача, решается долго, ответ около 9 миллионов способов расстановки, чуть больше.

[Yadryara]

Весьма похоже на задачу Киркмана, но для другого расклада.

-- 07.02.2026, 07:38 --

AlexSam в сообщении #1717535 писал(а):

Это 5 наборов для 16 чисел.

А сколько нужно найти наборов? В задаче Киркмана нужно найти 7 наборов для 15 чисел.

[AlexSam]

Combat Zone в сообщении #1717540 писал(а):

Хоть как. Расставьте по порядку.
Скорее всего, вы неправильно понимаете условие задачи, потому что 3+3+ 4+ 4 это и есть 14.
И вангую, в задаче просили не предъявить способ расстановки (это слишком легко). А найти число таких способов, которые описаны в условии. Да?

Комбинаторная задача, решается долго, ответ около 9 миллионов способов расстановки, чуть больше.

Скорее всего я плохо объяснил. 3+3+4+4 это набор чисел. Таких наборов 5. В любом наборе присутствуют все числа, а в других наборах комбинации чисел не повторяются.
Посмотрите образец для 16. Но если это легко, напишите все наборы для 13, 14 и 17.

Yadryara в сообщении #1717543 писал(а):

Весьма похоже на задачу Киркмана, но для другого расклада.

-- 07.02.2026, 07:38 --

AlexSam в сообщении #1717535 писал(а):

Это 5 наборов для 16 чисел.

А сколько нужно найти наборов? В задаче Киркмана нужно найти 7 наборов для 15 чисел.

Наборов должно быть 5 (для 14).

[TOTAL]

AlexSam в сообщении #1717563 писал(а):

Скорее всего я плохо объяснил. 3+3+4+4 это набор чисел.

В этом наборе сколько чисел?
Какие числа в этом наборе?

[Combat Zone]

TOTAL

Цитата:

Event organizers for bowling, golf, bridge, or tennis frequently tackle problems of this sort, unaware of the problem complexity. In general, it is an unsolved problem. A table of known results is maintained by Harvey.

-- 07.02.2026, 15:19 --

Я переведу на русский постановку задачи, хотя это дело ТС.

Есть 14 участников турнира. Для того, чтобы сыграть раунд турнира они разбиваются на 4 группы: две тройки и две четверки.
По правилам турнира, два разных участника могут играть друг с другом вместе в одной группе не более одного раза.

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

Задача восходит к Social golfer problem. Цитата, приведенная выше, позаимствована с Wolfram Mathworld.

[tolstopuz]

Combat Zone в сообщении #1717591 писал(а):

Есть 14 участников турнира. Для того, чтобы сыграть раунд турнира они разбиваются на 4 группы: две тройки и две четверки.

Скажем проще - турнир по преферансу :)

[tolstopuz]

Навайбкодил перебор, получается, что решений нет. Для проверки сделал этим же кодом $5$ наборов от $1$ до $16$, находит исправно.

Используется синтаксис Python

# Полное решение задачи выложу с разрешения модератора

Краткое содержание.

1. Генерирую все возможные разбиения с небольшим учетом симметрии - блоки одинакового размера должны идти по возрастанию минимального элемента. Так как возможных пар $91$, а используется только $90$, произвольно фиксирую одну отсутствующую пару $(13, 14)$ и выкидываю разбиения, где эти элементы попадают в один блок.
2. Для каждого разбиения считаю, какие пары оно затрагивает.
3. Превращаю множество пар в битовую маску.
4. Делаю перебор, накапливая битовую маску. Первое разбиение можно зафиксировать, далее для избежания лишней работы они идут по возрастанию номеров в исходном списке. На каждом уровне фильтрую оставшиеся разбиения и передаю их на следующий уровень, потому что условия становятся только жестче.

Всего разбиений с таким условием $843150$, для второго разбиения остается $8064$ варианта, для третьего - иногда $28$, иногда $32$.

-- Вс фев 08, 2026 15:17:05 --

Для $13$ тоже нет. Для $15$ нашлось.

$(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 11, 12), (13, 14, 15)$
$(1, 5, 9, 13), (2, 6, 10, 14), (3, 7, 11, 15), (4, 8, 12)$
$(1, 6, 12, 15), (3, 8, 10, 13), (4, 7, 9, 14), (2, 5, 11)$
$(1, 8, 11, 14), (2, 7, 12, 13), (4, 5, 10, 15), (3, 6, 9)$
$(2, 8, 9, 15), (3, 5, 12, 14), (4, 6, 11, 13), (1, 7, 10)$

[AlexSam]

Спасибо. А если ввести небольшие "поблажки" только для четверок? Из (1, 2, 3, 4) мы исключаем не все сочетания, а только "соседние": 1 исключить из любых сочетаний с 2 и 4 (2 и 4 при этом сочетаться могут еще один раз, но только как "соседи"), 2 исключить из 1 и 3 (1 и 3 при этом сочетаться могут еще один раз, но только как "соседи"), 3 исключить из (2 и 4), 4 исключить из (1 и 3)? Для 14 такое сработать может - там две четверки.

[tolstopuz]

А после $(1,2,3,4)$ можно $(1,5,3,6)$?

[AlexSam]

tolstopuz в сообщении #1717781 писал(а):

А после $(1,2,3,4)$ можно $(1,5,3,6)$?

а еще будет (1, 3, 8, 10) и три раза одно сочетание - перебор. Но если невозможно два раза сочетать, то тогда пусть будет три.
т.е. (1,5,3,6) и (1, 3, 8, 10) - это нормально (больше сочетаний 1 и 3 нет). (1,2,3,4) и (1,5,3,6) - не хорошо (больше сочетаний 1 и 3 нет), а (1,2,3,4) и (1,5,3,6) и (1, 3, 8, 10) - это плохо.

[tolstopuz]

Тогда схема с битовыми масками не пройдет, придется думать, как не просадить эффективность. Может, пока расскажете, откуда взялась такая задача?

[AlexSam]

tolstopuz в сообщении #1717798 писал(а):

Тогда схема с битовыми масками не пройдет, придется думать, как не просадить эффективность. Может, пока расскажете, откуда взялась такая задача?

Это жеребьевка на бильярдный "колхоз". Сайт делаю.

[tolstopuz]

Для $14$ с одним дублем решений нет, с двумя довольно много, например:

$(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, 13), (11, 12, 14)$
$(1, 5, 9, 11), (2, 6, 10, 12), (3, 7, 13), (4, 8, 14)$
$(1, 7, 10, 14), (2, 8, 9, 13), (3, 5, 12), (4, 6, 11)$
$(3, 6, 9, 14), (4, 5, 10, 13), (1, 8, 12), (2, 7, 11)$
$(3, 8, 10, 11), (4, 7, 9, 12), (1, 6, 13), (2, 5, 14)$

Здесь дубли $(9,13)$ и $(10,13)$, в четверках их можно расставить подальше друг от друга.

Все решения устроены одинаково - один неудачник ($13$) повторно играет в одной тройке сразу с двоими ($9$, $10$) и вообще не играет с троими ($11$, $12$, $14$).

[AlexSam]

Спасибо. Буду думать как с этим правильно разобраться.