Дано: квадрат 4x4, 3 цвета для раскраски клеток. Условие: в каждой строке и в каждом столбце не должно быть всех клеток одного цвета.
Найти: количество способов раскраски квадрата, удовлетворяющих заданным условиям.
Решение:
1. Обозначим цвета как A, B, C. Квадрат имеет 4 строки и 4 столбца.
2. Для начала, определим общее количество способов раскраски клеток без учета условий. Поскольку у нас 3 цвета и 16 клеток, общее количество раскрасок равно 3^16.
3. Теперь нам нужно вычесть случаи, когда хотя бы одна строка или один столбец содержит клетки одного цвета.
4. Применим принцип включения-исключения:
- Обозначим N — общее количество раскрасок.
- Обозначим A_i — множество раскрасок, где i-ая строка или столбец содержит клетки одного цвета.
- |A_i| — количество раскрасок, где i-ая строка или столбец содержит клетки одного цвета. Это будет равно 3 * 3^12 (поскольку одна строка может быть окрашена в один цвет, а остальные 12 клеток можно раскрасить любыми цветами).
5. Учитывая, что в квадрате 4 строк и 4 столбца, мы можем рассмотреть количество случаев, когда одна строка или столбец окрашен в один цвет:
|A| = |A_1 ∪ A_2 ∪ A_3 ∪ A_4 ∪ B_1 ∪ B_2 ∪ B_3 ∪ B_4|.
6. Применим формулу включения-исключения:
|A| = Σ |A_i| - Σ |A_i ∩ A_j| + Σ |A_i ∩ A_j ∩ A_k| - ...
Учитываем, что |A_i ∩ A_j| (две строки или два столбца окрашены в один цвет) будет равно 3 * 3^8 (т.к. 2 строки/столбца уже окрашены, остаются 8 клеток).
7. Рассчитываем количество перестановок:
- Количество способов выбрать одну строку или столбец, который будет одного цвета = 4 (строки) + 4 (столбцы) = 8.
- Количество способов выбрать две строки или столбца, которые будут одного цвета = C(4, 2) = 6 для строк и 6 для столбцов.
8. Сложив все эти случаи, получаем:
|A| = 8 * 3 * 3^12 - 12 * 3 * 3^8 + 0.
9. Подставив значения, вычисляем:
|A| = 8 * 3^13 - 12 * 3^9.
10. Теперь найдем общее количество раскрасок:
N = 3^16 - |A|.
Ответ: количество способов раскрасить квадрат 4x4 так, чтобы в каждой строке и столбце не было всех клеток одного цвета, равно 3^16 - (8 * 3^13 - 12 * 3^9).