В какое max число цветов нужно окрасить все клетки квадрата

[melnikoff]

В какое максимальное число цветов нужно окрасить все клетки квадрата 4 на 4 так, чтобы для каждой пары различных цветов нашлись две клетки этих цветов, находящиеся
либо в одной строке, либо в одном столбце квадрата?

Попытка:
Каждая строка и каждый столбец может представлять основное свойство для не более чем 6 разных цветов. Поэтому разных пар цветов не может быть более $6\cdot 8 = 48$. Поэтому в 11 цветов квадрат точно нельзя раскрасить, так различных пар цветов будет равно $C_{11}^2 = 55 > 48$.
При этом, квадрат легко раскрашивается в 7 цветов. Итого, возможное максимальное кол-во цветов сократили до 8, 9 или 10.
Как дальше? Чувствую, что вообще не в ту сторону думаю.

[PETIKANTROP]

Может быть, исходить из того, что максимальное попарное разнообразие цветов ограничено количеством различных цветов (N) на пересекающемся столбике и строке, что в свою очередь ограничено параметрами квадрата : $(n+n)-1=N$?

[mihaild]

Пусть цветов хотя бы 8. Может ли какой-то цвет встречаться в квадрате только один раз? Какое из этого следует ограничение на количество цветов (и на раскраску с этим количеством)?

[melnikoff]

mihaild в сообщении #1548128 писал(а):

Пусть цветов хотя бы 8. Может ли какой-то цвет встречаться в квадрате только один раз? Какое из этого следует ограничение на количество цветов (и на раскраску с этим количеством)?

Пусть цветов хотя бы 8. Если какой-то из цветов встречается в квадрате 1 раз, то как минимум 1 цвет не влезает ни на строку, ни в столбец с данным цветом. Следовательно, каждый из цветов встречается как минимум 2 раза. А это значит, что кол-во разных цветов не более 8 ($8\cdot2=16$).
Вот только такой квадрат с 8 цветами никак не строится...

[gris]

Просто надо вместо цветов использовать цифры от 1 до 8. Прекрасно 8 пар из одинаковых цифр (но все пары разные) строятся в каре и каждая пара из разных цифр (каждая цифра встречается с каждой другой цифрой) встречается хотя бы в одном столбце или в одной строке.
Или я как обычно ничего не понял
Построение проведено подбором в таблице эксель. При этом никакая пара из одинаковых цифр не стоит ни в одном столбце, ни в одной строке. Лайфхак для проверки: надо начинать с 1 и далее по порядку до 8 и каждую цифру проверять в паре только с большими цифрами. При сравнении цифра считается числом.

[mihaild]

Я не придумал, как систематически проверять, но вручную нашел довольно быстро (и одинаковые цифры в одной строке встречаются).

[gris]

Вот! С цифрами же легче. Осталось только найти количество таких каре (опасаюсь употреблять слово квадраты), причём не переходящих в друг друга при поворотах, отражениях и с помощью перестановки массива цифр.

[waxtep]

Пример, так же методом случайного блуждания в экселе, без повторов цифр в строке/столбце:

$$\begin{tabular}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 4&3&5&6\\ \hline 7&8&1&2\\ \hline 8&7&6&5\\ \hline \end{tabular}$$

[melnikoff]

waxtep, а вот мой вариант:

$$\begin{tabular}{|c|c|c|c|} \hline 1&2&3&4\\ \hline 2&5&6&7\\ \hline 3&8&7&8\\ \hline 4&6&5&1\\ \hline \end{tabular}$$

-- 12.02.2022, 15:03 --

gris в сообщении #1548577 писал(а):

Осталось только найти количество таких каре, причём не переходящих в друг друга при поворотах, отражениях и с помощью перестановки массива цифр.

И как же подступиться к этой задаче?

[gris]

Уважаемый melnikoff
Мне кажется, что 1)свойство квадрата сохраняется при перестановке столбцов и/или строк;
2) только одна цифра может находиться дважды в одной строке или столбце.
Приведу по макету waxtep приведённый к начальной форме квадрат (возможно именно тот, что указан by mihaild).

$$\begin{tabular}{|c|c|c|c|} \hline 1&1&2&3\\ \hline 4&5&6&7\\ \hline 6&7&8&5\\ \hline 8&2&3&4\\ \hline \end{tabular}$$

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

[mihaild]

Нет, у меня другой квадрат был, нарушающий свойство 2.

$$\begin{tabular}{|c|c|c|c|} \hline 1 & 1 & 2 & 2 \\ \hline 3 & 4 & 3 & 4 \\ \hline 5 & 6 & 7 & 8 \\ \hline 8 & 7 & 6 & 5 \\ \hline \end{tabular}$$