Математикадан аудандық олимпиада, 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}}}}.$