Клетки квадрата 4x4 нужно раскрасить тремя цветами так, чтобы в каждой строке и в каждом столбце не все клетки были одного цвета. Сколько существует способов это сделать?
от

1 Ответ

Дано: квадрат 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).
от