Гробы на экзаменах в ШАД24.12.2024 12:00

Рассмотрим ориентированный граф с вершинами — трёхзначными числами (которые могут начинаться с нуля) и рёбрами вида (abc,bcd) (= четырёхзначное число abcd ).
Из каждой вершины выходит 10 рёбер и в каждую входит 10 рёбер, поэтому в графе есть эйлеров цикл. Запишем по кругу число из 10000 цифр, соответствующее этому циклу. Разрежем его и выпишем в строку так, чтобы фрагмент 0000 стоял в конце. Сотрём последний нуль и получим 9999 -значное число, в котором встречаются по разу все 4-значные числа (которые могут начинаться с нуля), кроме 0000 .

Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными. Рёбра графа, отвечающие числам, не начинающимся с нуля, назовём синими, остальные — красными.
Пусть теперь дано кратчайшее -значное число $X=a_1a_2\ldots a_n$ , в котором встречаются все 9000 4-значных чисел, не начинающихся с нуля (хотя бы раз). Тогда $n\geq 9000+$ число нулей в A: при сдвиге на одну цифру вправо в мы получим, возможно, новое число, если только эта цифра не нуль. Рассмотрим множества чисел

$A=\{c000\mid c\ne 0\},\;B=\{bc00\mid a\ne 0\},\;C=\{abc0\mid a\ne 0\}, \;\;|A|=9,\,|B|=90,\;|C|=900.$

Оценим снизу число нулей в .
Все тройные нули из чисел в не пересекаются и содержатся в — уже $3\cdot 9$ нулей.
Пары нулей из не пересекаются и максимум 9 из этих 90 пар могли ,, утонуть`` в тройках нулей из . Итого, $\geq 2\cdot (90-9)$ новых нулей. Наконец максимум из 900 одинарных нулей из уже могли быть учтены в и , итого $\geq 900-90$ новых нулей. Итого, число содержит как минимум

$3\cdot 9+2\cdot(90-9)+900-90=999 \text{ нулей.}$

Ссылка на задачу