Post @vvvphoenix — Entertaining tasks

Jul 30 at 07:345.1K

Винтик, Шпунтик, включения и исключения.

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

у нас есть грань размера 3x3 и нам надо покрасить 9 ячеек в три цвета. 3 - в красный, 3 - в желтый, и 3 - в зеленый. Сколько существует раскрасок при которых ни одна строка и ни один столбец не закрашены одним цветом?

Картинка ниже дает примеры возможных и невозможных раскрасок

Задачку эту я решил, но решение мне не нравилось, потому что по сути оно является "ручным перебором" возможных раскрасок. И вот недавно, читая статью Артема, я сообразил, что все это можно описать в терминах "формулы включений - исключений". Для этого из полного числа раскрасок в три цвета нам надо исключить все "невозможные". Для это нужно просто аккуратно считать число раскрасок и чередовать знаки. Через к в дальнейшем обозначается номер шага, через n - размерность пространства. через В нашем случае она равна 3.

Шаг 0. Знак +. Полное число раскрасок 9 ячеек в три цвета.
$C_0 =+C(9,3,3,3) = +\frac{9!}{3!3!3!}=+1680$
Шаг 1. Знак -. Число раскрасок, при которых одна строка или один столбец закрашен одним цветом. Строки и столбы у нас "равноправны". Таким образом, мы получаем множитель 2, исходя из геометрии (а точнее просто размерности) задачи. Теперь, допустим, мы закрашиваем одну строчку(столбец) каким то одним цветом (допустим красным). Выбор цвета(1 из 3) дает нам С(3,1)=3 варианта. Выбор позиции дает еще 3 варианта. Запишем это как n!/(n-k)! Теперь нам нужно покрасить еще 6 (n(n-1)) ячеек в два цвета (желтый и зеленый). Что дает В итоге,
$C_1 =-2*C(3,1)*3!/(3-1)!* C(6,3) = -2*3*3*\frac{6!}{3!3!}=-360$
Шаг 3. Знак +. Когда у нас одновременно есть две строки или два столбца закрашенные одним цветом. Аналогично, 2- множитель размерности. Теперь нам надо выбрать 2 из 3 трех цветов. Получим, С(3,2) =3. Геометрическое размещение дает множитель 3!/(3-2)!. Ну и далее нам останется закрасить оставшиеся три ячейки оставшимся цветом. Что дает нам ровно С(3,3) = 1 вариант. Получаем,
Шаг 4. Знак -. Все три столбца или строки закрашены одним цветом. 2 - геометрический множитель. С(3,3) = 1 - выбор цветов. 3!/(3-3)! = 6 количество размещений. Итак,
А теперь соберем все вместе и получим.
$C = \frac{(n^2)!}{(n!)^n} +2*\sum_{k=1}^n(-1)^kC(n,k)\frac{n!}{(n-k)!}\frac{(n(n-k))!}{(n!)^{n-k}} (*)$

Или для нашего случая n = 3

И это правильный ответ. При домножении на дает 10752 - решение задачи Винтика и Шпунтика в тернарном случае.

Формулу (*) наверняка можно как то упрощать, но я не буду сейчас этим заниматься. Скажу лишь, что она работает для любых n. В частности, если нам нужно посчитать раскраски квадрата 4x4 в 4 цвета формула* дает.

В кватернарном случае Винтика и Шпунтика дело обстоит сложнее. Появляется дополнительная размерность и исключений становится больше. Однако, достоинством формулы (*) является относительное малое количество слагаемых (пусть и более сложного вида) по сравнению с тем, что предложил Артем.

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

+16