Имеется турнир по маджонгу. Есть несколько раундов R, играют несколько человек P. Имеется также P/4 столов (по 4 игрока на стол). Порядок чисел, представляющих номера игроков, внутри стола значения не имеет. Пример двух раундов:

  • [ [ 1, 0, 3, 2 ], [ 5, 6, 4, 7 ] ]
  • [ [ 1, 7, 4, 3 ], [ 6, 2, 5, 0 ] ]

Необходимо получить такую рассадку участников по столам, чтобы они пересекались все между собой за все раунды одинаковое количество раз. То есть чтобы все игроки сыграли со всеми остальными игроками ровно K раз.

Это возможно в случаях, когда K = 3 * R / (P - 1) принимает целые значения. При этом квадратная матрица пересечений (x, y - номера игроков) выглядит примерно так, самопересечения не учитываются:

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

В данном случае это для четырёх игроков и одного раунда, количество столбцов и строк, а также игр могут быть другими, но вид останется тем же. Это - критерий того, что турнирная таблица решена правильно. Хотя, возможно, есть и иные критерии.

Пример решений:

Для маленького числа участников решение достаточно легко получить направленным перебором, 16х10 поддаётся решению кое-как (хотя и может быть составлено как сумма двух решений 16х5), а 20х19 или 28х9 уже слишком велики, чтобы найти их точные решения таким образом. В примерных решениях в таблице пересечений местами есть искажения (+-1 от среднего).

Какая область математики ответственна за решение таких задач? Есть ли алгоритмы точного решения или хотя бы численного решения (составления) таких таблиц? Таблицы для нецелого К находятся случайными перестановками весьма уверенно и достаточно быстро.

Глядя на такую красоту, я верю, что алгоритм должен существовать.

задан 13 Янв '14 12:15

изменен 13 Янв '14 14:50

В одном из вопросов однажды обсуждались т.н. "комбинаторные дизайны". Это и есть та область математики, которая занимается подобными вещами. Здесь имеется в том числе и ссылка на соответствующие монографии.

(13 Янв '14 20:47) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×110
×86

задан
13 Янв '14 12:15

показан
694 раза

обновлен
13 Янв '14 20:47

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru