Соединение ячеек перестановками строк и столбцов в конечной сетке

10

Я хотел бы знать, изучалась ли ранее простая проблема и известно ли какое-либо решение.

Пусть G - конечная (MxN) сетка, S - подмножество клеток G («крошки»). Говорят, что две крошки (локально) связаны, если их координаты отличаются не более чем на один (т. Е. Если они нарисованы в виде квадратов, они имеют хотя бы одну угловую точку).

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

Вопрос: всегда ли есть решение?

Я не совсем знаю, как на него напасть. Из-за отсутствия лучшей идеи я написал сырую программу, которая ищет решения методом грубой силы (она генерирует случайные перестановки и проверяет, связаны ли крошки в результирующей сетке). До сих пор программа всегда находила решения для маленьких (10x10 или 7x14) сеток, а более крупные сетки явно недосягаемы для своей упрощенной стратегии (слишком бы случайно наткнуться на решение).

Вот пример сетки, решаемой программой:

Начальная сетка (крошки обозначены X, пустые ячейки точками):

   0 1 2 3 4 5 6 7 8 9 
 0 X . X X . X . X X .
 1 X . . . . X . . . .
 2 . . X . . . . X . X
 3 . X . . X . X . . X
 4 . . . X . . . . . .
 5 X X . . . X X . X .
 6 . . . X . . . . X .
 7 X . X . . X . . . .
 8 X . . . X . . X X .

Решение:

   6 1 4 7 8 2 9 3 5 0
 1 . . . . . . . . X X
 4 . . . . . . . X . .
 5 X X . . X . . . X X
 8 . . X X X . . . . X
 7 . . . . . X . . X X
 0 . . . X X X . X X X
 3 X X X . . . X . . .
 6 . . . . X . . X . .
 2 . . . X . X X . . .

Естественно, проблему можно легко обобщить на любое измерение d> 2. Полагаю, можно было бы рассмотреть и другие обобщения.

Заранее спасибо,

Ян Дэвид

Ян Дэвид
источник
2
интересная проблема. есть какое-то приложение?
Суреш Венкат
@Tsuyoshi: вы правы, у фигуры, которую я разместил, есть решение (которое вы предоставили). Я удалил это.
Марцио Де Биаси
2
Одновременный кросспост не рекомендуется. math.stackexchange.com/questions/83231/…
Tsuyoshi Ito

Ответы:

7

Давайте попробуем аналогично аргументу подсчета с более ранней версией моего ответа.

n225qn25qn225q(n!)2

c(nc)ncexp(cnlognO(n))q=cnexp(2nlogn+O(cn))c>2

Дэвид Эппштейн
источник
Установив и пренебрегая членами, я прогнал ваше неравенство, чтобы найти точку безубыточности, получив . Последнее значение замечательно близко к 26608.c=3o(n)n>6215/e2
Hardmath
Это любопытное численное совпадение. Я спрашивал об этом на mathoverflow.net/questions/81368/…
Дэвид Эппштейн
1
Это действительно элегантное и убедительное доказательство. (Мне потребовалось немного времени, чтобы детализировать приближения для моей собственной выгоды.) Еще неизвестно, удастся ли кому-нибудь придумать конкретный контрпример. Приведенный выше комментарий @ hardmath говорит о том, что это может быть сложно (СЕ будет уродливым зверем); теперь не нужно иметь одинаковое количество крошек во всех рядах CE.
Янн Дэвид