19-я Международная Жаутыковская олимпиада по математике, 2023 год

У Пети есть $1001$ карточка, на которых написаны синей ручкой числа $1,2,\dots,1001$; на каждой карточке написано ровно одно число. Петя выложил карточки по кругу синими числами вниз. Затем для каждой карточки $C$ Петя рассмотрел $500$ карточек, следующих за $C$ по часовой стрелке, и нашёл количество $f(C)$ тех из них, на которых синие числа больше, чем синее число на $C$. Число $f(C)$ Петя написал на верхней стороне карточки $C$ красной ручкой. Докажите, что Вася, видя только все красные числа, может восстановить, какое синее число на какой карточке написано. ( И. Богданов )

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

Примечание: Если у первой карточки по часовой стрелке в следующих $500$ карт встретится вторая, назовем ее бьющей вторую.

$Факт$ $#1$:

Если выбрать любые две карты, одна будет бить другую и никогда две карты бить друг друга не будут (доказать легко).

$Факт$ $#2$:

Карта с синей отметкой $a$ ($a \geq 501$) могла лежать лишь на картах с красной отметкой: $0,1,…,1001-a$.

$Процесс$ $нахождения:$

Мы будем искать сперва $1001$, потом зная нахождение $1001$, найдем $1000$, а после зная места $1001,1000$ найдем $999$ и так далее…

Поиск $1001$ очень легок, рассмотрим под кандидатуру лишь карты с $0$ (#2), и в этом случае можно понять что если первая карта с $0$ бьет вторую, то эта карта больше чем вторая, значит найдем самую большую карту с надписью $0$ (все карты бьют друг друга, #1), там и будет лежать $1001$. Теперь вместо $0$ на этой карте напишем синей ручкой $1001$ (для удобства).

Найдем карту $a$ если нам известны карты $1001,1000, …, a+1$. Для начала рассмотрим только карты с $0,1,…,1001-a$ (#2). Допустим мы рассматриваем лучшего кандидата с карточек с красной надписью $b$ из этих чисел. Заметим, кандидатами из таких карточек нужно учитывать только тех у кого в следующие $500$ чисел по часовой уже лежит ровно $b$ уже определенных чисел. Если будет меньше, то почему то наша карта $a$ будет меньше какой-то неопределенной карты (что невозможно, ибо мы определили все карты больше $a$). А больше быть очевидно не может быть ибо на карте $b$ не могло бы быть написано. Пусть это будет называться первым фильтром.

После первого фильтра, сделаем второй, он выглядит таким образом:

Теперь рассмотрим опять же карточки с красной надписью $b$ которые уже прошли первый фильтр. По #1, каждая карта бьет другую, а значит больше, ибо мы же знаем все числа которые больше $a$, значит любое неопределенное число в поле $500$ чисел по часовой у карты с $b$ всегда ее меньше, значит бьющая больше принимающей удар. Это фильтр $2$. Так, по #1 мы выведем лишь одного кандидата с $b$, и так сделаем с каждым (если остались карты) $b$ $\in[0,1,…,1001-a]$ и выдвинем всех кандидатов. По #1, опять же каждая бьет другую, а значит больше по такому же принципу как в фильтре $2$. Так, мы получим лишь одного кандидата, там будет лежать наш заветный $a$. Напишем на этой карте синим $a$ что бы запомнить.

Таким образом, мы сделаем с каждой картой от $1001$ до $501$, а после, можно вообще забыть про эти карты и все красные карты с $a$ переписать в $1001-a$ и найти сперва $0$, потом зная $0$, $1$ и так далее до $500$, что и требовалось доказать.

Мотивация: Впринципе кажись сразу было понятно что это верно даже если будет $2k+1$ карт и мы будем рассматривать $k$ карт по часовой. Вот и я нарисовал $11$ чисел по кругу и пробовал восстановить. Было довольно просто понять что легче всего начать с самых крайних чисел ($11$ или $0$), ибо у них сокращено количество кандидатов, потом я искал $10$ так будто мне было ясно где лежит $11$ но как бы не совсем точно, и мне нужно было найти алгоритм что бы спускаться, и я его нашел :D

Мы называем карту видимой, если знаем значение синего цвета на ней. Мы попробуем найти невидимую карту максимума (карта является максимальной, если синее значение на ней самое большое) одну за другой. Допустим, некоторые карты видимы и не учитываются (как большее число) при написании красных чисел на других картах, а также предположим, что только невидимые карты имеют красные значения. Итак, наша задача — найти максимальную невидимую карту. Рассмотрим следующий алгоритм: пусть $S$ — набор карточек с красным номером $0$. Очевидно, что максимальная карта находится в $S$. Если $|S| = 1$ мы уже нашли максимальную карту, так что все готово. В противном случае выберем любую карту $A\in S$. Если для всех $B\in S$ $dist(A,B)\leq 501$ (Расстоянием от карты $A$ до карты $B$ мы называем количество карт, которые мы увидим, двигаясь по часовой стрелке от $ От A$ до $B$, $dist(A, B)$ — это просто расстояние от этих карт). Можно сказать, что $A$ — максимальная карта, поскольку значение синего цвета на ней больше, чем значение любой карты в наборе. Теперь рассмотрим карту $C$, для которой $dist(A,C) > 501$ и $dist(A,C)$ минимально возможно. Обратите внимание, что $A$ и любая другая карта $B$ со свойством $dist(A,B) > 501$ входят в карты $500$, следующие за $C$ по часовой стрелке. С другой стороны, любая карта $D$ со свойством $dist(A,D) \leq 501$ имеет меньшее значение синего цвета, чем карта A, которая имеет меньшее значение, чем $C$. Следовательно, $C$ — это карта максимального достоинства. На каждом шаге мы можем найти максимальную невидимую карту и уменьшить стоимость карты стоимостью $500$ против часовой стрелки на 1 (поскольку мы знаем, что эта карта считалась большей картой). Итак, в конце мы найдем каждую карту.