Очевидное утверждение
Если квадрат NxN c-coloring, то следующий квадрат (N+1)x(N+1) Код:
. . . . . . С+1
. . . . . . С+1
. . . . . . С+1
. . . . . . C+1
С+1 . . . С+1
будет (с+1)-coloring.
Примерэтот квадрат 9х9 3-coloring:
Код:
1,2,3,1,2,3,1,2,3,
2,3,1,2,3,1,2,3,1,
3,1,2,3,1,2,3,1,2,
1,2,3,2,3,1,3,1,2,
2,3,1,3,1,2,1,2,3,
3,1,2,1,2,3,2,3,1,
1,2,3,3,1,2,2,3,1,
2,3,1,1,2,3,3,1,2,
3,1,2,2,3,1,1,2,3
По указанному свойству получаем из этого квадрата квадрат 10х10 4-coloring:
Код:
1,2,3,1,2,3,1,2,3,4,
2,3,1,2,3,1,2,3,1,4,
3,1,2,3,1,2,3,1,2,4,
1,2,3,2,3,1,3,1,2,4,
2,3,1,3,1,2,1,2,3,4,
3,1,2,1,2,3,2,3,1,4,
1,2,3,3,1,2,2,3,1,4,
2,3,1,1,2,3,3,1,2,4,
3,1,2,2,3,1,1,2,3,4,
4,4,4,4,4,4,4,4,4,4
Полезное свойство.
Кстати, решение C=3, N=81 элементарно достраивается программой Эда до решения C=3, N=100.
Например, из приведённого выше решения C=3, N=81 получаем в программе Эда такое решение C=3, N=100:
Код:
A,B,C,A,B,C,A,D,D,B,B,C,A,B,C,A,B,C,A,D,C,A,B,C,A,B,C,A,B,D,A,B,C,B,C,A,C,A,B,C,B,C,A,C,A,B,A,D,C,C,C,A,B,A,B,C,B,C,A,C,A,B,C,C,A,B,B,C,A,D,B,C,A,A,B,C,C,A,B,D,C,A,B,B,C,A,A,B,D,D,B,B,D,C,C,C,A,B,A,D
Из этого решения по указанному свойству элементарно получается решение C=4, N=121.
Приведённое выше решение C=4, N=100 элементарно достраивается в программе Эда до решения C=4, N=121:
Код:
A,B,C,A,B,C,A,B,C,D,C,B,C,A,B,C,A,B,C,A,A,D,C,A,B,C,A,B,C,A,B,D,D,A,B,C,B,C,A,C,A,B,D,B,B,C,A,C,A,B,A,B,C,D,B,C,A,B,A,B,C,B,C,A,D,B,A,B,C,C,A,B,B,C,A,D,A,B,C,A,A,B,D,C,A,B,D,C,C,A,B,B,C,A,A,B,C,D,A,D,D,D,D,D,B,D,D,D,D,A,D,B,B,A,A,D,C,C,C,C,D
А это решение тоже легко достраивается до решения C=4, N=144:
Код:
A,B,C,D,B,C,A,B,D,D,C,C,B,C,A,B,C,A,D,C,D,A,D,D,C,A,B,C,A,B,C,A,B,D,D,C,A,D,C,B,C,A,C,A,B,B,D,B,B,C,A,C,A,C,A,B,C,D,B,B,C,A,B,D,B,C,B,C,A,A,B,D,A,B,C,C,A,B,B,C,A,D,A,D,B,C,D,A,B,D,D,A,A,D,C,A,C,A,B,B,C,A,A,B,C,D,A,A,D,D,A,D,B,B,D,A,C,B,A,C,D,B,B,A,A,D,C,C,D,C,C,B,C,C,C,A,D,D,B,D,B,A,A,D
Интересно, можно ли дойти таким способом до максимального решения C=4, N=324.
-- Сб июн 09, 2012 09:44:56 --Решение C=4, N=169 тоже довольно легко получилось:
Код:
A,B,C,D,B,C,A,B,D,D,C,C,A,B,C,A,B,C,A,D,C,D,A,A,D,B,C,A,B,C,A,B,C,A,B,D,D,C,C,D,B,C,B,C,A,C,A,B,B,D,D,A,B,C,A,C,A,C,A,B,B,D,B,B,D,C,A,B,D,B,C,B,C,A,A,B,D,A,A,D,C,C,A,B,B,C,A,D,A,B,B,B,C,A,A,B,B,D,A,A,D,C,A,C,C,A,B,B,C,A,A,D,C,C,D,A,D,D,C,D,D,A,B,C,D,C,B,B,A,A,D,B,B,A,A,D,C,C,D,C,C,B,D,C,C,C,A,D,D,B,D,B,D,A,D,A,A,D,B,A,D,A,D,B,C,B,D,C,B
Хорошая игрушка
Спасибо Эду!