Районная олимпиада, 2020-2021 учебный год, 11 класс

Компьютер заражён вирусами. На этот компьютер установили Антивирус. Этот Антивирус борется с каждым вирусом по следующей схеме:
   1) сначала он находит вирус,
   2) затем помещает найденный вирус в карантин,
   3) и, в конце концов, уничтожает вирус.
   Над каждым вирусом Антивирус выполняет операции 1-3 строго в указанном порядке, но не обязательно сразу одну за другой. Выполнив одну операцию над каким-то вирусом, он может либо приступить к следующей для этого вируса операции, либо перейти к другому вирусу, выполняя над ним соответствующую операцию.
   Известно, что Антивирус вылечил компьютер, уничтожив все 2020 вирусов, которыми был заражён компьютер. Сколькими различными способами Антивирус мог это сделать?

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.    
Ответ. $\frac{{6060!}}{{{{(3!)}^{2020}}}}.$
Решение. Пронумеруем все вирусы числами от 1 до 2020. Выполнение операций Антивирусом по уничтожению вирусов закодируем в виде последовательности чисел 1 до 2020, записывая номер вируса каждый раз, как только Антивирус при-ступил к выполнению операции к какому-либо вирусу. Таким образом получится последовательность, состоящая из $3 \cdot 2020 = 6060$ чисел (так как вирусов 2020, и над каждым вирусом выполняется по 3 операции). В этой последовательности в каком-то порядке будут записаны ровно три 1, ровно три 2, ровно три 3,..., ровно три 2020.
   Обратно, если мы выберем произвольную последовательность, состоящую из 6060 чисел, в которой присутствуют ровно три 1, ровно три 2, ровно три 3,..., ровно три 2020, то мы можем восстановить последовательность выполнения Антивирусом операций над вирусами так: как только первый раз встретилось число $x$ в последовательности, это означает, что нужно выполнить операцию 1 над вирусом $x$, второе появление числа $x$ в этой последовательности означает, что пора выполнять операцию 2 над вирусом $x$, и, наконец, третье появление $x$ в последовательности на говорит о том, что необходимо приступить к выполнению операции 3 над вирусом $x$. Например, последовательность $$2018, 4, 4, 7,3, 2018,3, 2018, 4,...$$ показывает нам, что Антивирус сначала находит вирус с номером 2018, затем находит вирус 4, после этого помещает вирус 4 в карантин, затем находит вирус 7, после чего находит вирус 3, затем помещает вирус 2018 в карантин, после этого помещает вирус 3 в карантин, теперь уничтожает вирус 2018, после чего уничтожает вирус 4, ... Таким образом, количество таких последовательностей равно количеству различных способов, которыми Антивирус может уничтожить вирусы на компьютере. Поскольку рассматриваемая нами последовательность состоит из 6060 чисел от 1 до 2020, и каждое число входит в эту последовательность ровно три раза, то количество различных способов составить эту последовательность равно $\frac{{6060!}}{{{{(3!)}^{2020}}}}.$