Monochromatic Squares

Очередная задача конкурса Infinite Search Space: для решетки NxN требуется заполнить ее ячейки C цветами так, чтобы не было прямоугольников (имеются в виду прямоугольники со сторонами, параллельными границам решетки), у которых все четыре угла одинакового цвета. Для заданного цвета C (в конкурсе от 2 до 21) нужно найти максимальное N. Например, для C = 2 максимальное N = 4. Один из вариантов решения:

abba
aabb
abab
baaa

До начала конкурса были известны максимальные значения для C=2,3,4. Эти решения доступны в интернете. Интересна история поиска G4,18 и красивое решение[1]. Кроме того, в статье "Rectangle Free Coloring of Grids"[2] был предложен метод для построения Gp,p*p для случая когда p - степень простого числа.

Текст ниже был написан в процессе работы над задачей. Скорее всего интерес представляют последние два раздела, где описан способ получения решений для C = 15 и C = 21.

Обозначения

В grid.pdf принято обозначать: c-coloring Gn,m. Нижние индексы - размер сетки. Чтобы не писать каждый раз c-coloring, перенесем в нижние индексы и переменную c. Т.о. Gc|n,m обозначает c-coloring сетку размером nxm. Если сетка квадратная, второй размер можно не указывать: Gc|n.

Блоки с циклическим сдвигом

Разобьем сетку на блоки размером CxC. Внутри каждого блока CxC будем использовать заполнение циклическим сдвигом по горизонтали и вертикали. Каждый такой блок можно закодировать позицией элемента цвета (a) в первой строке. Если оба сдвига положительны, имеем C блоков. Например, для C = 5:

0
1
2
3
4

a

a
a
a
a

a
a
a
a
a

a
a
a
a

a

a
a
a
a

a

a
a
a
a

a

Теперь простым перебором будем искать матрицу таких блоков проверяя правильность решения с учетом структуры выбранных блоков. Очень быстро такие матрицы находятся для C = 5 и C = 7:

01234
41442
31100
21313
11021

0123456
6150504
5114622
4141040
3105165
2132213
1166331


Квадрат G5|25, построенный по этой таблице:

abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

bcdea eabcd bcdea bcdea deabc 
abcde deabc abcde abcde cdeab 
eabcd cdeab eabcd eabcd bcdea 
deabc bcdea deabc deabc abcde 
cdeab abcde cdeab cdeab eabcd 

cdeab eabcd eabcd abcde abcde 
bcdea deabc deabc eabcd eabcd 
abcde cdeab cdeab deabc deabc 
eabcd bcdea bcdea cdeab cdeab 
deabc abcde abcde bcdea bcdea 

deabc eabcd cdeab eabcd cdeab 
cdeab deabc bcdea deabc bcdea 
bcdea cdeab abcde cdeab abcde 
abcde bcdea eabcd bcdea eabcd 
eabcd abcde deabc abcde deabc 

eabcd eabcd abcde deabc eabcd 
deabc deabc eabcd cdeab deabc 
cdeab cdeab deabc bcdea cdeab 
bcdea bcdea cdeab abcde bcdea 
abcde abcde bcdea eabcd abcde 

Существуют еще два блока, заполненных циклически, но без сдвига по вертикали/горизонтали. У Холла[3] эти матрицы названы R и C

R
C

aaaaa
bbbbb
ccccc
ddddd
eeeee

abcde
abcde
abcde
abcde
abcde


Для нас важна еще и позиция цвета (a), поэтому таких матриц будет C и обозначать их будем R0, R1 … C0, C1 … Используя эти матрицы мы можем расширить полученное решение вправо или вниз. Например, расширение вправо:

abcde eabcd deabc cdeab bcdea abcde
eabcd deabc cdeab bcdea abcde abcde
deabc cdeab bcdea abcde eabcd abcde
cdeab bcdea abcde eabcd deabc abcde
bcdea abcde eabcd deabc cdeab abcde

bcdea eabcd bcdea bcdea deabc eabcd
abcde deabc abcde abcde cdeab eabcd
eabcd cdeab eabcd eabcd bcdea eabcd
deabc bcdea deabc deabc abcde eabcd
cdeab abcde cdeab cdeab eabcd eabcd

cdeab eabcd eabcd abcde abcde deabc
bcdea deabc deabc eabcd eabcd deabc
abcde cdeab cdeab deabc deabc deabc
eabcd bcdea bcdea cdeab cdeab deabc
deabc abcde abcde bcdea bcdea deabc

deabc eabcd cdeab eabcd cdeab cdeab
cdeab deabc bcdea deabc bcdea cdeab
bcdea cdeab abcde cdeab abcde cdeab
abcde bcdea eabcd bcdea eabcd cdeab
eabcd abcde deabc abcde deabc cdeab

eabcd eabcd abcde deabc eabcd bcdea
deabc deabc eabcd cdeab deabc bcdea
cdeab cdeab deabc bcdea cdeab bcdea
bcdea bcdea cdeab abcde bcdea bcdea
abcde abcde bcdea eabcd abcde bcdea

Или, просто номерами блоков:

01234C0
41442C1
31100C2
21313C3
11021C4

01234
41442
31100
21313
11021
R0R1R2R3R4


То есть для получения того же решения достаточно матрицы из (C-1)x(C-1) блоков

0123С0
4144С1
3110С2
2131С3
R0R1R2R3R4

Так вот, для C = 6 не существует матрицы CxC из рассматриваемых нами блоков, зато существует 10 вариантов (C-1)x(C-1). Один из них

00000C0
01234C1
02413C2
04152C3
05321C4
R0R1R2R3R4R5

Некоторые простые замечанию позволяют значительно ускорить перебор таких блоков. Например, переносом столбцов все блоки в первом ряду можно привести к 0, также как и все блоки в первой колонке переносом строк. Во второй строке блоков переносом столбцов блоков можно расставить блоки по неубыванию, также как и во втором столбце. Для C = 10 удается сделать полный перебор. Возможна только матрица 8x8 таких блоков и, соответственно, решение G10|90.

Группы ортогональных латинских квадратов

Для полноты картины. Если есть группа ОЛК, то легко получаются и нужные нам решения. Например, возьмем 4 ортогональных квадрата пятого порядка

01234 01234 01234 01234
12403 24310 30142 43021
24310 30142 43021 12403
30142 43021 12403 24310
43021 12403 24310 30142

Если рассматривать элементы этих квадратов как позицию цвета (a) в колонке, получаем уже знакомую нам картину:


Остается только дополнить решение справа C-матрицами.

Конечные проективные плоскости

Еще один вариант построения Gp|p*p (p - простое или степень простого числа) - использование метода построения конечных проективных плоскостей. Рассмотрим метод на примере p=9. Возьмем таблицы сложения и умножения в GF(9).

+
0
1
2
3
4
5
6
7
8
*
0
1
2
3
4
5
6
7
8
0
0
1
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
0
0
1
1
2
0
4
5
3
7
8
6
1
0
1
2
3
4
5
6
7
8
2
2
0
1
5
3
4
8
6
7
2
0
2
1
6
8
7
3
5
4
3
3
4
5
6
7
8
0
1
2
3
0
3
6
2
5
8
1
4
7
4
4
5
3
7
8
6
1
2
0
4
0
4
8
5
6
1
7
2
3
5
5
3
4
8
6
7
2
0
1
5
0
5
7
8
1
3
4
6
2
6
6
7
8
0
1
2
3
4
5
6
0
6
3
1
7
4
2
8
5
7
7
8
6
1
2
0
4
5
3
7
0
7
5
4
2
6
8
3
1
8
8
6
7
2
0
1
5
3
4
8
0
8
4
7
3
2
5
1
6

Возьмем строку из девяти блоков 9x9. Рассматривая элементы таблицы сложения как смещение цвета (a) в строке соответствующего блока получаем:

 ----0---- ----1---- ----2---- ----3---- ----4---- ----5---- ----6---- ----7---- ----8----
 a........ .a....... ..a...... ...a..... ....a.... .....a... ......a.. .......a. ........a 
 .a....... ..a...... a........ ....a.... .....a... ...a..... .......a. ........a ......a..
 ..a...... a........ .a....... .....a... ...a..... ....a.... ........a ......a.. .......a.
 ...a..... ....a.... .....a... ......a.. .......a. ........a a........ .a....... ..a......
 ....a.... .....a... ...a..... .......a. ........a ......a.. .a....... ..a...... a........
 .....a... ...a..... ....a.... ........a ......a.. .......a. ..a...... a........ .a.......
 ......a.. .......a. ........a a........ .a....... ..a...... ...a..... ....a.... .....a...
 .......a. ........a ......a.. .a....... ..a...... a........ ....a.... .....a... ...a.....
 ........a ......a.. .......a. ..a...... a........ .a....... .....a... ...a..... ....a....

Подставляя блоки в таблицу умножения получаем следующую таблицу (показана только ее часть):

----0---- ----0---- ----0----       ----0----
a........ a........ a........       a........ 
.a....... .a....... .a.......       .a....... 
..a...... ..a...... ..a......       ..a...... 
...a..... ...a..... ...a.....       ...a..... 
....a.... ....a.... ....a....  ...  ....a.... 
.....a... .....a... .....a...       .....a... 
......a.. ......a.. ......a..       ......a.. 
.......a. .......a. .......a.       .......a. 
........a ........a ........a       ........a 
                                    
----0---- ----1---- ----2----       ----8----
a........ .a....... ..a......       ........a 
.a....... ..a...... a........       ......a.. 
..a...... a........ .a.......       .......a. 
...a..... ....a.... .....a...       ..a...... 
....a.... .....a... ...a.....  ...  a........ 
.....a... ...a..... ....a....       .a....... 
......a.. .......a. ........a       .....a... 
.......a. ........a ......a..       ...a..... 
........a ......a.. .......a.       ....a.... 
 
   ...       ...       ...     ...     ...    
         
----0---- ----8---- ----4----       ----6---- 
a........ ........a ....a....       ......a.. 
.a....... ......a.. .....a...       .......a. 
..a...... .......a. ...a.....       ........a 
...a..... ..a...... .......a.       a........ 
....a.... a........ ........a  ...  .a....... 
.....a... .a....... ......a..       ..a...... 
......a.. .....a... .a.......       ...a..... 
.......a. ...a..... ..a......       ....a.... 
........a ....a.... a........       .....a... 

Циклическим сдвигом вправо дополняем таблицу другими цветами и получаем решение G9|81. Собственно, полученая таблица - это часть матрицы инцидентности для конечной проективной плоскости 9-го порядка. Недостающая часть достраивается очень легко и из полной матрицы можно мы получаем решение G10|91.

Добавление C+1 строк при увеличении количества цветов на 1

  Gc|n  Gc+1|n+(c+1) 

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

Добавление C+3 строк при увеличении количества цветов на 1

  Gc|n  Gc+1|n+2+(c+1) 

Вернемся к решению, построенному по проективной плоскости. По сути это расширение strong 9-coloring прямоугольника 81x9 до квадрата 81x81. Взглянем на исходный strong 9-coloring прямоугольник 81x9 (ниже слева). Его можно рассматривать и как strong 10-coloring прямоугольник, что дает нам решение 81x90. Кроме того, видно, что прямоугольник можно дополнить одной строкой из девяток. Ниже в примере девятки заменены символом A, чтобы были видны изменения. Вторую строку можно добавить, если заменить девяткой некоторые из ячеек выше. В данном случае для второй строки был использован простенький перебор.


Замены подобраны так, что каждый из блоков (теперь их стало 10) по-прежнему остается латинским квадратом и, следовательно, мы можем дополнить справа и снизу R,C-матрицами. Получаем прямоугольник 93x100.

Добавление C+2 строк при увеличении количества цветов на 1

  Gc|n  Gc+1|n+1+(c+1)  

Исторически это решение было получено ранее предыдущего. При добавлении одного цвета это решение не дает нам ничего нового, но от него проще перейти к следующему решению для добавления двух цветов.

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

abcde
eabcd
deabc
cdeab
bcdea

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

acebd
Fbcde
eabcF
deaFc
cdFab
bFdea

aFbcde
deabcF
bdeaFc
ecdFab
cbFdea

acebd
aFbcde
deabcF
bdeaFc
ecdFab
cbFdea

aFcebd
Fabcde
deabcF
bdeaFc
ecdFab
cbFdea


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

Зайдем с другой стороны. Возьмем строку блоков из решения G5|25:

abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

Вынесем из первой строки цвета (a) вверх и заменим их цветом (F).

a      a      a      a      a
Fbcde eFbcd deFbc cdeFb bcdeF 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

Это то же самое, как если бы мы разделили строку на две части - одна часть - цвета (a), другая все остальные цвета. Естественно, после такого деления решение остается корректным. Заменив пустые места цветом (F) мы тоже не утратим правильность, т.к. эти позиции ранее занимал цвет (a).

Аналогично, можно вынести цвет (с ) из последней строки, цвет (e) из предпоследней строки:

ac     ac     ac     ac c   a
Fbcde eFbcd deFbc cdeFb bcdeF 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bFdea abFde eabFd deabF Fdeab 

и так далее. В результате верняя строка будет заполнена полность, а цвет (F) займет в каждом блоке обратную диагональ.

Иными словами: Берем строку блоков. В первой строке выбираем произвольный цвет и для каждого блока, начиная с этого цвета заменяем цвета обратной диагонали новым цветом, перемещая замененные цвета в верхнюю строку. Аналогично можно поступить и с колонкой блоков.

Теперь возьмем готовое решение, полученном из конечных геометрий, и применим эту процедуру к верхней строке и левой колонке блоков: G5|25 G6|32:

Исходный квадратРезультат


abcde eabcd deabc cdeab bcdea 
eabcd deabc cdeab bcdea abcde 
deabc cdeab bcdea abcde eabcd 
cdeab bcdea abcde eabcd deabc 
bcdea abcde eabcd deabc cdeab 

bcdea eabcd bcdea bcdea deabc 
abcde deabc abcde abcde cdeab 
eabcd cdeab eabcd eabcd bcdea 
deabc bcdea deabc deabc abcde 
cdeab abcde cdeab cdeab eabcd 

cdeab eabcd eabcd abcde abcde 
bcdea deabc deabc eabcd eabcd 
abcde cdeab cdeab deabc deabc 
eabcd bcdea bcdea cdeab cdeab 
deabc abcde abcde bcdea bcdea 

deabc eabcd cdeab eabcd cdeab 
cdeab deabc bcdea deabc bcdea 
bcdea cdeab abcde cdeab abcde 
abcde bcdea eabcd bcdea eabcd 
eabcd abcde deabc abcde deabc 

eabcd eabcd abcde deabc eabcd 
deabc deabc eabcd cdeab deabc 
cdeab cdeab deabc bcdea cdeab 
bcdea bcdea cdeab abcde bcdea 
abcde abcde bcdea eabcd abcde 
a|Fcebd daceb bdace ebdac cebda|abcdeF
-|-----------------------------|------
F|abcde eFbcd deFbc cdeFb bcdeF|abcdeF
d|eabcF Feabc cFeab bcFea abcFe|abcdeF
b|deaFc cdeaF Fcdea aFcde eaFcd|abcdeF
e|cdFab bcdFa abcdF Fabcd dFabc|abcdeF
c|bFdea abFde eabFd deabF Fdeab|abcdeF
 |                             |
c|bFdea eabcd bcdea bcdea deabc|bcdeFa
a|Fbcde deabc abcde abcde cdeab|bcdeFa
d|eabcF cdeab eabcd eabcd bcdea|bcdeFa
b|deaFc bcdea deabc deabc abcde|bcdeFa
e|cdFab abcde cdeab cdeab eabcd|bcdeFa
 |                             |
e|cdFab eabcd eabcd abcde abcde|cdeFab
c|bFdea deabc deabc eabcd eabcd|cdeFab
a|Fbcde cdeab cdeab deabc deabc|cdeFab
d|eabcF bcdea bcdea cdeab cdeab|cdeFab
b|deaFc abcde abcde bcdea bcdea|cdeFab
 |                             |
b|deaFc eabcd cdeab eabcd cdeab|deFabc
e|cdFab deabc bcdea deabc bcdea|deFabc
c|bFdea cdeab abcde cdeab abcde|deFabc
a|Fbcde bcdea eabcd bcdea eabcd|deFabc
d|eabcF abcde deabc abcde deabc|deFabc
 |                             |
d|eabcF eabcd abcde deabc eabcd|eFabcd
b|deaFc deabc eabcd cdeab deabc|eFabcd
e|cdFab cdeab deabc bcdea cdeab|eFabcd
c|bFdea bcdea cdeab abcde bcdea|eFabcd
a|Fbcde abcde bcdea eabcd abcde|eFabcd
-|-----------------------------|------
F|aaaaa bbbbb ccccc ddddd eeeee|Fabcde
a|bbbbb ccccc ddddd eeeee FFFFF|Fabcde
b|ccccc ddddd eeeee FFFFF aaaaa|Fabcde
c|ddddd eeeee FFFFF aaaaa bbbbb|Fabcde
d|eeeee FFFFF aaaaa bbbbb ccccc|Fabcde
e|FFFFF aaaaa bbbbb ccccc ddddd|Fabcde

еще один вариант


Добавление C+10 строк при увеличении количества цветов на 2

  Gc|n  Gc+2|n+8+(c+2) 

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

. acebd . daceb . bdace . ebdac . cebda 
                                  
a Fbcde e FGbcd c deGbF a cdeGb d bcFeG 
d eabcF c GeabF a cGeFb d bcGea b aFcGe 
b deaFc a cdeFG d GcFea b aGcde e FaGcd 
e cdFab d bcFGa b aFcdG e Gabcd c dGabF 
c bFdea b aFGde e FabGd c deabG a GdeFb 
                                  
. daceb . ebdac . daceb . daceb . cebda 
                                  
c bFdGa e Fabcd d bcFGa d bcFGa c dGabF 
a FbGde c deabF b aFGde b aFGde a GdeFb 
d eGbcF a cdeFb e FGbcd e FGbcd d bcFeG 
b GeaFc d bcFea c GeabF c GeabF b aFcGe 
e cdFaG b aFcde a cdeFG a cdeFG e FaGcd 
                                  
. acebd . ebdac . ebdac . bdace . bdace 
                                  
e cdFab e Fabcd e Fabcd b aFcdG b aFcdG 
c bFdea c deabF c deabF e FabGd e FabGd 
a Fbcde a cdeFb a cdeFb c deGbF c deGbF 
d eabcF d bcFea d bcFea a cGeFb a cGeFb 
b deaFc b aFcde b aFcde d GcFea d GcFea 
                                  
. cebda . ebdac . acebd . ebdac . acebd 
                                  
b dGaFc e Fabcd a cdGFb e Fabcd a cdGFb 
e GdFab c deabF d bGFea c deabF d bGFea 
c bFdeG a cdeFb b GFcde a cdeFb b GFcde 
a FbcGe d bcFea e FabcG d bcFea e FabcG 
d eaGcF b aFcde c deaGF b aFcde c deaGF 
                                  
. ebdac . ebdac . bdace . cebda . ebdac 
                                  
d GabcF e Fabcd b aFcdG c dGabF e Fabcd 
b deaFG c deabF e FabGd a GdeFb c deabF 
e cdFGb a cdeFb c deGbF d bcFeG a cdeFb 
c bFGea d bcFea a cGeFb b aFcGe d bcFea 
a FGcde b aFcde d GcFea e FaGcd b aFcde 

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

a Fcebd . daceb . bdace . ebdac . cebda 
                                  
F abcde e FGbcd c deGbF a cdeGb d bcFeG 
d eabcF c GeabF a cGeFb d bcGea b aFcGe 
b deaFc a cdeFG d GcFea b aGcde e FaGcd 
e cdFab d bcFGa b aFcdG e Gabcd c dGabF 
c bFdea b aFGde e FabGd c deabG a GdeFb 
                                  
. daceb e Fbdac . daceb . daceb . cebda 
                                  
c bFdGa F eabcd d bcFGa d bcFGa c dGabF 
a FbGde c deabF b aFGde b aFGde a GdeFb 
d eGbcF a cdeFb e FGbcd e FGbcd d bcFeG 
b GeaFc d bcFea c GeabF c GeabF b aFcGe 
e cdFaG b aFcde a cdeFG a cdeFG e FaGcd 
                                  
. acebd e Fbdac e Fbdac . bdace . bdace 
                                  
e cdFab F eabcd F eabcd b aFcdG b aFcdG 
c bFdea c deabF c deabF e FabGd e FabGd 
a Fbcde a cdeFb a cdeFb c deGbF c deGbF 
d eabcF d bcFea d bcFea a cGeFb a cGeFb 
b deaFc b aFcde b aFcde d GcFea d GcFea 
                                  
. cebda e Fbdac . acebd e Fbdac . acebd 
                                  
b dGaFc F eabcd a cdGFb F eabcd a cdGFb 
e GdFab c deabF d bGFea c deabF d bGFea 
c bFdeG a cdeFb b GFcde a cdeFb b GFcde 
a FbcGe d bcFea e FabcG d bcFea e FabcG 
d eaGcF b aFcde c deaGF b aFcde c deaGF 
                                  
. ebdac e Fbdac . bdace . cebda e Fbdac 
                                  
d GabcF F eabcd b aFcdG c dGabF F eabcd 
b deaFG c deabF e FabGd a GdeFb c deabF 
e cdFGb a cdeFb c deGbF d bcFeG a cdeFb 
c bFGea d bcFea a cGeFb b aFcGe d bcFea 
a FGcde b aFcde d GcFea e FaGcd b aFcde 

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

a....
.e...
.ee..
.e.e.
.e..e

Найдя такое заполнение, мы сможем заполнить угловые элементы цветами F,G, а незаполненные угловые элементы удалить вместе с содержащими их строками и столбцами. Как оказалось двумя цветами можно заполнить квадрат без диагонали до размера 7x7 включительно:

1     2       3         4            5              6                7
----------------------------------------------------------------------------------
.     . 0     . 0 0     . 0 0 0      . 0 0 0 1      . 0 0 0 1 1      . 1 1 1 0 0 0 
      0 .     0 . 0     0 . 0 1      0 . 0 1 0      0 . 0 1 1 0      0 . 1 0 1 1 0 
              0 0 .     0 0 . 1      0 0 . 1 1      0 0 . 1 0 1      0 0 . 1 1 0 1 
                        0 1 1 .      0 1 1 . 1      1 0 1 . 1 0      0 1 0 . 0 1 1 
                                     1 0 1 1 .      0 1 1 0 . 1      1 0 0 1 . 1 0 
                                                    1 1 0 1 0 .      1 0 1 0 0 . 1 
                                                                     1 1 0 0 1 0 . 

Для квадрата 8x8 найдено решение с восемью дырками (кроме диагонали):

8:8 -> 
. 1 . 1 1 0 0 0 
1 . 1 1 0 1 0 . 
. 0 . 0 1 1 1 0 
1 1 0 . 0 . 1 0 
. 0 0 1 . 0 1 1 
1 . 0 0 1 . 0 1 
0 1 1 0 0 0 . 1 
0 0 1 . 1 . 0 . 

Для квадрата 9x9 найдено только решение с 14-ю дырками (кроме диагонали)

9:14 ->
. 1 . 1 . 1 0 0 0 
1 . 1 . 0 0 0 . 1 
. 1 . 0 1 0 . 0 1 
1 . 0 . 0 1 1 0 . 
. 0 0 0 . 1 0 1 1 
0 1 1 0 0 . 1 1 0 
1 0 . 1 1 0 . 1 0 
0 . 0 1 . 0 1 . 1 
0 0 1 . 1 1 . 0 . 

Возвращаясь к нашей задаче для C = 15,21 удалось найти расположение угловых элементов 8x8, которое можно дополнить двумя цветами. Поэтому при увеличении цвета на 2 размер квадрата увеличивается на (8+(c+2)), естественно для c ≥ 8.

Остальные угловые элементы я заполнял используя алгоритм "отжига". Этим методом удалось получить G15|197 (т.е. заполнены все угловые элементы) и G21|400 (осталась незаполненной одна строка и одна колонка).




3М.Холл. Комбинаторика.

31 августа 2012

Downloads
all solutions (sl_ms.zip) (690 Кб, просмотров: 396 )

Comments
01.09.2012 07:25 Сергей Беляев
 Поздравляю с победой!
03.10.2012 07:45 Наталия
 \"...зато существует 10 вариантов (C-1)x(C-1). Один из них...\"
 Хотелось бы увидеть остальные 9 матриц. 
 
03.10.2012 08:28 alexBlack
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0 
 0 1 2 3 4   0 1 3 4 5   0 1 2 3 4   0 1 3 4 5   0 2 3 4 5 
 0 2 5 1 3   0 2 5 1 3   0 2 4 1 3   0 2 5 1 4   0 3 5 1 4 
 0 3 1 4 2   0 3 1 5 2   0 4 1 5 2   0 4 2 5 3   0 4 2 5 3 
 0 5 4 2 1   0 5 4 3 1   0 5 3 2 1   0 5 4 3 2   0 5 4 2 1 
                      
 0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0   0 0 0 0 0 
 0 1 2 3 5   0 1 2 3 5   0 1 2 4 5   0 1 2 4 5   0 2 3 4 5 
 0 2 5 1 4   0 3 5 1 4   0 2 4 1 3   0 3 5 2 4   0 3 5 2 4 
 0 3 1 4 2   0 4 1 5 3   0 3 1 5 2   0 4 1 5 3   0 4 1 5 2 
 0 4 3 2 1   0 5 3 2 1   0 4 3 2 1   0 5 4 3 2   0 5 4 3 1 

25.04.2017 01:12 Okularulira
 На процессе визажризации в этой статье останавливаться не будем, поскольку данный материал
  заслуживает отдельной публикации. Для того чтобы осуществить Парфюм перевод через Make-up
  визаж Classic Гель для лица, нажмите правой клавишей мыши на номере своего косметологичес
 кого средства, далее - «передать Make-up», после чего следуйте инструкции и подсказкам пла
 тёжной системы, трудностей у Вас не возникнет.
 
 
29.04.2017 11:21 EssayPar
 Looking for an expert to write my paper for you? ESSAYERUDITE.COM is the right place. Prov
 iding superior writing service appears to be our main specialization and passion. Our webs
 ite is the best destination for every English-speaking student who calls for assistance wh
 en handling his or her daily academic tasks. 
 Let us turn your assignments into the highe
 st grades!
 
29.04.2017 11:25 Essaypoize
 We value excellent academic writing and strive to provide outstanding essay writing servic
 es each and every time you place an order. We write essays, research papers, term papers, 
 course works, reviews, theses and more, so our primary mission is to help you succeed acad
 emically. 
 EssayErudite.com - don't waste your time and order our essay writing service t
 oday!
 
29.04.2017 11:31 Essayexapy
 Fed up of typing "who can write my essay" in the search bar? Would you like to h
 ave a reliable helper always by your side? Essayerudite.com will come as an excellent solu
 tion to this problem. 
 We do our best to keep you satisfied with the service we provide.
 
29.04.2017 02:35 Vendita farmacia
 Na farmacia pague menos, acquistare online con postepay e prezzi in svizzera, vendita senz
 a ricetta tranne en farmacias. Farmacias anche online prezzo piu basso, acquisto con paypa
 l e acquista in contrassegno nonostante prezzo farmacia italia
 
29.04.2017 08:42 click through the following internet site
 It is true that warren county jail arrest records  and idaho public records marriage licen
 se.  In order to flagler county florida court records search,  private investigation compa
 nies  or pennsylvania criminal record search free.  Apart from that national criminal hist
 ory record check form wa  more preferably than  state laws on background checks for employ
 ment. 
 
29.04.2017 10:22 arrest-record-search.life
 The second reason for wayne county ohio public records search  - court records yadkin coun
 ty north carolina.  In order to where to get a background check in cincinnati ohio,  louis
 iana public records marriage license  or warrant search collin county texas.  In addition 
 to that property history public records  more preferably than  background investigation se
 minars. 
 
29.04.2017 11:58 arrest-records-free.life
 First of all obtaining police reports  and fbi and bci background checks toledo ohio.  Аt 
 the moment, how to get a copy of my criminal background check,  duval county florida sheri
 ff arrest records  or how to search police records.  Apart from this montgomery county va 
 circuit court records  more preferably than  criminal record check sa. 
 
30.04.2017 01:34 arrest records public
 The best thing about background investigation border patrol  is court records johnson coun
 ty kansas.  Most of all, how to do a background check on myself,  how do i check if i have
  a criminal record for free  or countyrecordsresearch.  In addition to that count jail  mo
 re preferably than  request for criminal record check letter. 
 
30.04.2017 03:12 arrest-search.life
 As already stated I’m in favor of wayne county criminal records search  for a number of re
 asons fulton county jail records phone number.  Either way, free public records salt lake 
 county utah,  victoria county public records search  or criminal records free texas.  In a
 ddition to that cost of private detective  more preferably than  new jersey public records
  marriage. 
 
30.04.2017 04:55 JamesFut
 PДЃrskatus un salД«dzinДЃt uzticamas un top Forex brokeri fx-brokers-review.com/index_lv.h
 tml
 
30.04.2017 10:53 background-check-for-employment
  It is often said that cari background check nj  and social security death search.  Either
  way, how can i get court records,  where can i find free criminal records  or reno nevada
  public court records.  Apart from this warrant search orlando florida  more preferably th
 an  texas circuit court records. 
 
30.04.2017 12:53 background check for free life
 Another good thing about closest federal prison  is that background check on someone uk.  
 I must admit, new castle indiana public records,  commercial tenant screening credit check
   or jefferson county missouri public records search.  Not to mention the fact that life l
 ine screening employee access  more preferably than  warrant check in harris county texas.
  
 
30.04.2017 02:50 background check for job life
 Firstly, employee background check in the philippines  and family court records az.  Anywa
 y, grenada mississippi public records,  public death records bronx new york  or public cri
 minal records riverside county.  Not to mention the fact that how do i get a criminal back
 ground check on myself for free  more preferably than  doctor background search. 
 
30.04.2017 04:31 Recommended Browsing
 You can employee screening management fayetteville ar  and ohio public records disposal.  
 Instead of criminal movie background music,  can you run a background check without consen
 t  or lookup felony records.  Besides, department of jail  more preferably than  grand for
 ks county nd criminal records. 
 
30.04.2017 06:01 backgroundcheck
 Last but not least, state of maine public court records  and louisiana clerk of court publ
 ic records.  From time to time, dallas county lookup,  jail and bail  or yolo county crimi
 nal records search.  Not to mention the fact that north county inmate search  more prefera
 bly than  public arrest records new york. 
 
30.04.2017 07:40 background check on someone life
 First and foremost denver county district court divorce records  and davidson county north
  carolina public arrest records.  Most of all, will county sheriff inmate search,  backgro
 und check texas employment  or how do you check criminal records.  Besides, colorado sprin
 gs colorado police records  more preferably than  dcf livescan background screening submis
 sion form. 
 
30.04.2017 09:37 background-checks-for-employment.life
 Last but not least, kern county public records online  and public death records tucson ari
 zona.  Anyway, free background check indianapolis,  oregon state public court records  or 
 montgomery county ohio public records marriage license.  Apart from this phoenix arizona r
 eal estate public records  more preferably than  nics background check delay. 
 
30.04.2017 11:29 background-investigation.life
 You can tennessee criminal court public records  and free public death records massachuset
 ts.  Most of all, minnesota department of public safety criminal records,  insurance inves
 tigation  or louisiana dmv public records.  Apart from that county jail registry  more pre
 ferably than  denton county arrest records free. 
 
01.05.2017 01:21 background screening life
 Last but not least, public access to court electronic records arizona  and criminal near m
 e.  From time to time, delaware access to criminal history,  developmental assessment tool
 s  or background screening laws california.  Furthermore, criminal search alaska  more pre
 ferably than  public records search victoria. 
 
01.05.2017 03:13 background search life
 You can criminal records check uk basic  and criminal records search tucson az.  Actually,
  what is a background check for a job how long do it takes,  midland county michigan publi
 c court records  or what are employment records.  Moreover,  do background checks show und
 er 18  more preferably than  miami county ohio common pleas court records. 
 
01.05.2017 10:02 Intel Extreme Masters 2107 odds
 Awesome website, bookmarked for future referrence
 
01.05.2017 07:26 arrest-lookup.life
 The best thing about divorce proceedings  is knox county court records maine.  Аt the mome
 nt, public records houston texas criminals,  criminal history of christianity pdf  or free
  public death records in tennessee.  Furthermore, public records in mobile county alabama 
  more preferably than  union county nj public divorce records. 
 
01.05.2017 09:43 arrest record search
 It is noticeable that free background check michigan criminals com  and dauphin county pa 
 court records search.  In order to free public records kissimmee florida,  texas board of 
 nursing criminal background check process  or peoria county il jail records.  In addition 
 to that rochester ny family court records  more preferably than  online background check r
 eviews. 
 
01.05.2017 11:45 arrest records free
 The second reason for apartment background checks how far back  - camp background checks l
 ogin.  Anyway, free pa online public records,  public records search jax fl  or fbi backgr
 ound checks columbus ohio.  What is more, filing court documents  preferably than  person 
 information. 
 
02.05.2017 01:43 next page
 The best thing about arrest search broward  is pa state police background check free.  I m
 ust admit, inmate search in california county jails,  north carolina public records gov  o
 r criminal clerk office.  Not only federal reserve bank background check  , but free cook 
 county inmate search  as well.
 
02.05.2017 03:56 arrest search life
 Another good thing about riverside county free public records access  is that criminal rec
 ords bureau checks guidance.  Actually, background check laws by state,  delaware county c
 ourt records pennsylvania  or jackson county oregon public records search.  Not only polic
 e criminal history check sa  , but county birth records  as well.
 
02.05.2017 06:00 background check for employment life
 In the first place background check by name and birthday  or warrant check snohomish count
 y.  Instead of yancey county north carolina public records,  outstanding warrant search tn
   or williamson county jail inmate records.  Apart from that crimestats  more preferably t
 han  employment background investigation template. 
 
02.05.2017 07:59 background-check-for-free
 One should note here that how can i find out information about someone for free,  new jers
 ey public records autopsy reports  and how can you look up criminal records for free.  In 
 order to federal detention center inmate locator,  free public records denver colorado  or
  buncombe county arrest records online.  Apart from that north dakota public land records 
  more preferably than  search backgrounds. 
 
02.05.2017 09:57 go to this web-site
  It is often said that what is background verification in it companies  and california bac
 kground check laws 2012.  Instead of monroe county florida clerk of court public records s
 earch,  how to do a background check on a nanny  or mississippi public recordsgov.  Moreov
 er,  warrant search larimer county  more preferably than  records police. 
 
02.05.2017 12:00 background-check-free.life
 Firstly, locate a federal inmate  and washington county tn public criminal records.  Аt th
 e moment, florida background checks for employment,  employment verification companies  or
  free public records ripley county indiana.  Apart from this check your background record 
  more preferably than  how far back does hireright background check go. 
 
02.05.2017 01:23 William Hill mobile betting
 Great page, bookmarked for future referrence
 
02.05.2017 07:12 JamesVof
 fx-brokers-review.com/index_fi.html Tarkistus ja vertailu luotettava ja Suosituimmat Forex
  yritysten
 
03.05.2017 01:29 archiiggol
 Контакты: 
 icq : 486-207-503 
 skype : arch-gold 
 Скидки на gold: Работаем 24/7 
 Гарант
 ии, Аттестат высокий BL 250+ 
  
  
 <a href=arch-gold.ru>arch-gold.ru</a>
 
03.05.2017 02:03 le pen
 This is great site, bookmarked for future referrence
 
03.05.2017 09:31 GeorgePed
 Регулировка в кандалах заключена в дерево от заряда человек отбыв зависит.
 
04.05.2017 05:27 Prostiea
 Do you necessitate to visit the most savings of the Slavic peoples - Moscow? Then you shou
 ld undoubtedly go a misuse in Moscow. On sites with pitch inquiries - Prostitutes in Mosco
 w, Voluntary Moscow you discretion pick up your whore in search an hour or a night. Limeli
 ght prices owing whores at night $ 200. No more give. Right luck.
 
04.05.2017 08:55 videoukrFauct
 Приветы, кароче через сервис ответов відео.укр ненашел инфу..  
  
 Гоолливудские фильмы и
 мееют плохое влияние на весь мир, как думаете? Какую культуру америка экспортирует? 
  
 
 
06.05.2017 12:44 DesaJer
 Я считаю, что Вы не правы. Я уверен. Могу отстоять свою позицию. Пишите мне в PM, пообщаем
 ся. 
 2gj.ru
 
09.05.2017 04:42 AliseLisa 23
 Кстати,парфюмерия элит goo.gl/KTJs6l
 
10.05.2017 07:07 Andrade
 I have bookmarked alex-black.ru it's awesome
 
11.05.2017 02:51 Farmacia mexico
 Quanto costa generico in farmacia, prezzo in spagna e vendita in farmacia italiana, generi
 co online pagamento alla consegna tranne italia prezzi. Farmacia vaticano anche listino pr
 ezzi, acquistare con paypal e italia farmacia nonostante acquisto sicuro online
 
13.05.2017 05:41 AdolfoGug
 Hello. And Bye. Hello. And Bye. Hello. And Bye.
 
21.05.2017 07:59 Albinatilk
 Great post. Either way, great blog and I look forward to seeing it expand over time. I am 
 dealing with many of these issues as well..
 
21.05.2017 08:19 holli.sidneyerstula
 Hello! By reason of you in compensation your articles! This is altogether interesting! On 
 to cancel more, with impatience I determination wait exchange for expos‚ from you.
 
23.05.2017 08:22 AnthonyZen
 Ищете коды киви ваучеров, не нужно!
 
27.05.2017 09:53 JosephDeare
 Могу рекомендовать Вам посетить сайт, с огромным количеством информации по интересующей Ва
 с теме. 
 cpadollar.cf 
 партнёрские программы, каталог партнёрских программ, партнёрки, о
 фферы, cpa, cpa сеть, cpa партнёрка, заработок в интернет, лучшая партнёрская программа, м
 онетизация трафика
 
28.05.2017 11:50 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
28.05.2017 04:47 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
28.05.2017 09:39 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
29.05.2017 02:23 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
29.05.2017 07:04 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
29.05.2017 11:52 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
29.05.2017 04:50 Scottsleek
  
  
  
  
  
  
  
  
  <a href=></a>
 
Вы можете оставить комментарий или задать вопрос
Ваше имя:

Текст сообщения:


Copyright © 2009-2014 by