Задача 2.4. Мешки Царя Гороха

Что делает Царь Горох

Пусть Царь выбрал мешок с номером $k$. Мешков с большими номерами — от $k+1$ до $2007$ — ровно $2007-k$. Например, после мешка $2000$ стоят мешки $2001, 2002, \ldots, 2007$, их $7=2007-2000$. В каждый такой мешок Царь кладёт по одной монете. Поэтому:

• мешок $k$ теряет $2007-k$ монет;
• каждый мешок с номером больше $k$ получает $1$ монету;
• мешки с номерами меньше $k$ не меняются.

Монет всегда хватает: больше всего отдаёт мешок $1$ — $2006$ монет, а в нём $2022$. Если Царь выбрал последний, $2007$-й мешок, перекладывать некуда, и ничего не меняется. Этот случай Ивану тоже нужно уметь узнать.

На рисунке то же правило на $7$ мешках. Заметь: монеты только переходят из мешка в мешок, поэтому во всех мешках вместе их по-прежнему $2007\cdot2022$. Значит, называть все мешки бесполезно: при любом выборе Царь скажет одно и то же число.

Что на самом деле узнаёт Иван

Иван называет мешки один раз и слышит одно число. Сколько монет было в его мешках до перекладывания, он знает: по $2022$ в каждом. Поэтому вся новая информация — на сколько изменилась сумма. По шагу 1 это изменение складывается так:

• $+1$ за каждый названный мешок с номером больше $k$;
• $-(2007-k)$, если назван и сам мешок $k$.

Выбора у Царя $2007$. Иван наверняка узнает номер, только если все $2007$ выборов дают разные изменения. Простые наборы для этого не годятся. Все мешки — изменение всегда $0$. Один мешок, например $1000$-й: изменение равно $+1$, если $k$ меньше $1000$; равно $-1007$, если $k=1000$; равно $0$, если $k$ больше $1000$. Всего три разных ответа на $2007$ выборов. Нужен набор похитрее.

Сравним соседние выборы

Чтобы понять, какой набор нужен, вспомним пример с одним мешком из шага 2. Там одинаковые ответы давали как раз соседние выборы: при $k=1, 2, \ldots, 999$ Иван каждый раз слышал $+1$. Соседние выборы Царя меньше всего отличаются друг от друга — значит, их ответы проще всего спутать. Поэтому сравним два соседних выбора: мешок $k$ и мешок $k+1$. Сначала посмотрим на $7$ мешках, $k=4$ (рисунок ниже).

• Выбор $4$: мешок $4$ теряет $3$ монеты, мешки $5$, $6$, $7$ получают по одной.
• Выбор $5$: мешок $5$ теряет $2$ монеты, мешки $6$ и $7$ получают по одной.

Мешки $6$ и $7$ в обоих случаях получают одинаково, мешки $1$–$3$ не меняются. Разница только в мешках $4$ и $5$: при выборе $4$ в мешке $4$ на $3$ монеты меньше, а в мешке $5$ на $1+2=3$ монеты больше, чем при выборе $5$. Будто из мешка $4$ в мешок $5$ переложили $3$ монеты.

В кладовой из $2007$ мешков так же. Мешки до $k$ в обоих случаях не меняются, мешки после $k+1$ в обоих случаях получают по монете. Мешок $k$ при выборе $k$ теряет $2007-k$ монет, а при выборе $k+1$ не меняется. Мешок $k+1$ при выборе $k$ получает $1$ монету, а при выборе $k+1$ сам отдаёт $2006-k$; разница $1+(2006-k)=2007-k$. Значит, выбор $k$ отличается от выбора $k+1$ только тем, что из мешка $k$ в мешок $k+1$ будто переложили $2007-k$ монет.

Отсюда главный вывод. Если Иван назвал оба мешка $k$ и $k+1$, переложенные монеты остаются внутри его мешков, и сумма та же. Если он не назвал ни одного из них, монеты проходят мимо его мешков — сумма тоже та же. В обоих случаях при выборах $k$ и $k+1$ Царь скажет одно и то же число, и Иван их не различит.

Значит, в подходящем наборе любые два соседних мешка «разные»: один назван, другой нет. Названные и неназванные мешки чередуются, и вариантов всего два — смотря по тому, назван ли мешок $1$: все нечётные мешки или все чётные. Проверим, что все чётные мешки подходят; для нечётных рассуждение такое же.

Считаем изменения для чётных мешков

Пусть Иван назвал все чётные мешки: $2, 4, \ldots, 2006$ — это $1003$ мешка. Царь выбрал мешок $k$; обозначим через $m$ число мешков после него: $m=2007-k$, это мешки с номерами от $k+1$ до $2007$. Последний из них, $2007$-й, нечётный, а чётные и нечётные номера чередуются.

$k$ нечётный. Тогда $m$ чётное. Мешок $k$ не назван, а мешки после него начинаются с чётного $k+1$ и кончаются нечётным $2007$. Их можно разбить на пары «чётный, нечётный», поэтому чётных ровно половина: $m:2$. Каждый из них получил монету, и сумма Ивана выросла на $m:2$. Например, при $k=1999$ после него $8$ мешков, чётные среди них — $2000, 2002, 2004, 2006$: рост на $4$.

$k$ чётный. Тогда $m$ нечётное. Мешок $k$ назван и теряет $m$ монет. Мешки после него начинаются с нечётного $k+1$ и кончаются нечётным $2007$. Без последнего, $2007$-го, они разбиваются на пары «нечётный, чётный», поэтому чётных среди них $(m-1):2$. Они получают по монете. Всего изменение

то есть сумма уменьшилась на $(m+1):2$. Например, при $k=2000$ получаем $m=7$: мешок $2000$ отдал $7$ монет, а чётные $2002, 2004, 2006$ получили по одной, $3-7=-4$.

Переберём все выборы. Для нечётных $k$ число $m$ принимает значения $0, 2, 4, \ldots, 2006$, и сумма растёт на $0, 1, 2, \ldots, 1003$ — все эти числа разные. Для чётных $k$ число $m$ принимает значения $1, 3, \ldots, 2005$, и сумма уменьшается на $1, 2, \ldots, 1003$ — тоже все разные. А рост (или $0$) никогда не совпадает с уменьшением. Значит, все $2007$ выборов Царя дают разные суммы.

Как Иван находит номер

Теперь способ Ивана. Он называет все чётные мешки. До перекладывания в них

монет. Услышав ответ Царя, Иван сравнивает его с этим числом.

• Сумма выросла на $g$ (или не изменилась, $g=0$). По шагу 4 Царь выбрал нечётный мешок, после которого $m=2g$ мешков, то есть мешок номер $2007-2g$.
• Сумма уменьшилась на $d$. Тогда мешок чётный и $(m+1):2=d$, значит, $m=2d-1$, и номер мешка $2007-(2d-1)=2008-2d$.

Например, Царь сказал $2\,028\,071$ — это на $5$ больше. Иван отвечает: мешок $2007-2\cdot5=1997$. Проверим: после мешка $1997$ чётные мешки — $1998, 2000, 2002, 2004, 2006$, их ровно $5$. Если же Царь сказал $2\,028\,060$ — на $6$ меньше, — то это мешок $2008-2\cdot6=1996$: он отдал $11$ монет, а пять чётных мешков после него получили по одной, $5-11=-6$.