Вот это вот авторское.
Показать скрытый текст
Лемма. Пусть за x рублей Вася смог выложить в нужном порядке на стол некоторые N – 1 карточку, где N ≤ 3k. Тогда он сможет добавить к выложенным карточкам еще одну, потратив при этом еще не более k рублей.
Доказательство проведем индукцией по k. База (k = 1) очевидна.
Шаг индукции. Пусть N = 3m – r ≤ 3k (r = 0, 1, 2). Первый рубль Вася потратит на то, чтобы правильно выложить на стол N-ю карточку и карточки A и B , уже лежащие на местах m и 2m. Тогда N-я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки A и B разбивают лежащую на столе последовательность из N – 1 карточки на куски размером не более чем по m – 1 ≤ 3k–1 – 1 карточек, а значит, Васе осталось определить место карточки с номером N среди не более чем 3k–1 – 1 карточек, потратив не более чем k – 1 рубль, а это можно сделать по предположению индукции.
Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит 1 рубль. На добавление к ним карточек с номерами от 4 до 9 (всего 6 карточек) Вася потратит не более 2 рублей на каждую. На карточки с 10-й по 27-ю – не более 3 рублей на каждую, с 28-й по 81-ю – не более 4 рублей, с 82-й по 243-ю – не более 5 рублей и, наконец, на карточки с номерами от 244 до 365 – не более 6 рублей на каждую.
Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем 1 + 6·2 + 18·3 + 54·4 + 162·5 + 122·6 = 1845 рублей.
