Потерянная задача из Кванта: перестановка натуральных чисел

[maxal]

Эта задача основывается на одной задаче, предположительно опубликованной в журнале "Квант" в 1996 году или чуть раньше, за авторством А.Шаповалова. Известная мне библиографическая ссылка отсылает к журналу Quantum: Sept/October 1996. Надо заметить, что журнал Quantum наряду со множеством статей и задач переведенных на английский язык из русскоязычного "Кванта" содержал также оригинальные материалы, не публиковавшиеся на русском языке. К сожалению, добраться до указанного номера журнала Quantum довольно проблематично, а найти эту задачу в отечественном "Кванте" мне тоже сходу не удалось. Поэтому судить о корнях задачи я могу лишь косвенно. Буду рад, если кто-нибудь сумеет найти исходную публикацию этой задачи.

Задача. Бесконечная последовательность положительных целых чисел $a_1, a_2, \dots$ определяется по правилу: $a_n$ - это наименьшее положительное целое число, отличное от $a_1, a_2, \dots, a_{n-1}$, такое, что сумма $a_1+a_2+\dots+a_n$ делится на $n$.
Докажите, что:

1) Последовательность $a_1, a_2, \dots$ является перестановкой членов натурального ряда, то есть каждое натуральное число рано или поздно появляется в этой последовательности.

2) Получающаяся перестановка является само-обратной (инволюцией), то есть для каждого целого $n\geq 1$ имеет место тождество $a_{a_n}=n$.

[Руст]

Задача интересная.
1. Определим две последовательности: $b_0=0, \ a_n=b_{n-1}, \ b_n=b_{n-1}$ если $b_{n-1}>0$ и не встречался до этого в последовательности, иначе $a_n=b_{n-1}+n, \ b_n=b_{n-1}+1$.
Ясно, что последовательность $n/2 \le b_n\le n$ не убывающая а потому в последовательности $a_n$ встречаются все числа натурального ряда ровно один раз.
2. Доказывается подсчётом тех i, для которых $a_i<i\le n$.
Вроде тут можно вывести более явную формулу: $a_n=[c_1n+1]$ или $a_n=[c_2n+1]$, где $с_{1,2}=\frac{\pm1+\sqrt 5}{2}$ - корни золотого сечения,

[Erken1]

Ну мне кажется не настолько она и потерянная.Во-первых хотелось бы упомянуть первый источник, где я увидел эту задачку.Так вот им был широко известный сборник задач Санкт-Петербургских олимпиад,если не ошибаюсь 2004 года,а именно задача второго тура для десятых классов.
Автором же является человек по фамилии Ижболдин,к сожалению имени и даже инициалов не припомню.
Также задачу я видел на сайте mathlinks,а именно вот здесь,для незнающих ангийский могу даже пояснить,что автор темы,говорит о том,что он якобы сам догадался о существование этой задачи.Вот ссылка: http://www.mathlinks.ro/viewtopic.php?t=158438
Лично я склонен считать, что автором все же является выше упомянутый
,Ижболдин.

[maxal]

Erken1, о какой части задачи вы говорите?
Как я уже писал выше, первая часть задачи (или ее очень похожий вариант) появилась не позже 1996 года и ее автором был Шаповалов. Вторая часть задачи (без указания решения) по сути указана Howard A. Landman как свойство последовательности A019444, что датировано 2001 годом.
Поэтому в 2004 году она никак не могла быть новой.

А "потерянной" я ее назвал лишь потому, что не могу найти ссылку в русскоязычной литературе, хотя есть ссылка в переводной.

[Erken1]

Я говорил о второй задаче.
Насчет первой задачи возможно вы и правы, а насчет второй позволю себе не согласиться, поскольку если верить данному сборнику, то О.Т Ижболдин остваил нас в 2000 году,так как же он
мог придумать эту задачу позже чем A.Landman? И в ней четко сказано, что О.Т.Ижболдин является автором этой задачи,и лично я доверяю этому источнику.

[нг]

Erken1 писал(а):

Автором же является человек по фамилии Ижболдин,к сожалению имени и даже инициалов не припомню.

Олег Томович Ижболдин

[Brukvalub]

Наиболее похожие, но не идентичные задачи авторства А.Шаповалова см.
Квант: №1 за 2003, Стр. 21 , Квант: №5 за 1995, Стр. 21

[maxal]

Brukvalub, ага за 1995 год - это она (идентична английской версии). Ура!

[Erken1]

To maxal:
И какое же отношение она имеет к задаче предложенной вами в начале темы?
В кванте вопрос стоит о существование последовательности, у вас же требуется доказать совсем другое,так что даже похожими эти задачи считать нельзя.
УРА!

[maxal]

Erken1, первая задача в этой теме дает конкретный ответ на задачу из Кванта. Другими словами, из решения задачи 1 (а уж тем более 2) автоматически следует решение задачи из Кванта.