Разделы 
Дополнительно
Задача по математике - 2032
2019-01-23 
На столе лежат 365 карточек, на обратной стороне которых написаны различные числа. За один рубль Вася может выбрать три карточки и попросить Петю положить их слева направо так, чтобы числа на карточках располагались в порядке возрастания. Может ли Вася, потратив 2000 рублей, с гарантией выложить все 365 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?
Решение:
Лемма. Пусть за $x$ рублей Вася смог выложить в нужном порядке на стол некоторые $N - 1$ карточку, где $N \leq 3k$. Тогда он сможет добавить к выложенным карточкам еще одну, потратив при этом еще не более $k$ рублей, т. е. затратив всего не более $x + k$ рублей.
Доказательство. * леммы проведем индукцией по числу $k$. База $k = 1$ очевидна. Пусть для всех $N \leq 3^{k-1}$ лемма доказана. Первый рубль Вася потратит на то, чтобы правильно выложить на стол $N$-ю карточку и карточки $A$ и $B$, уже лежащие на местах $\left [ \frac{N}{3} \right ]$ и $\left [ \frac{2N}{3} \right ]$. Тогда $N$-я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки $A$ и $B$ разбивают лежащую на столе последовательность из $N - 1$ карточки на куски размером не более чем по $3^{k-1} - 1$ карточек, а значит Васе осталось определить место карточки с номером $N$ среди не более чем $3^{k-1} - 1$ карточек, потратив не более чем $k - 1$ рубль, а это можно сделать по предположению индукции. Таким образом, лемма доказана.
Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит 1 рубль. На добавление к ним карточек с номерами от 4 до 9 (всего 6 карточек) Вася потратит не более 2 рублей на каждую карточку. На карточки с 10 по 27 не более 3 рублей на каждую, с 28 по 81 не более 4 рублей, с 82 по 243 не более 5 рублей и наконец на карточки с номерами от 244 до 365 не более 6 рублей на каждую. Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем $1 + 6 \cdot 2 + 18 \cdot 3 + 54 \cdot 4 + 162 \cdot 5 + 122 \cdot 6 = 1845 < 2000$ рублей. Таким образом, Вася сможет потратить не более 2000 рублей.
Ответ. Может.
На столе лежат 365 карточек, на обратной стороне которых написаны различные числа. За один рубль Вася может выбрать три карточки и попросить Петю положить их слева направо так, чтобы числа на карточках располагались в порядке возрастания. Может ли Вася, потратив 2000 рублей, с гарантией выложить все 365 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?
Решение:
Лемма. Пусть за $x$ рублей Вася смог выложить в нужном порядке на стол некоторые $N - 1$ карточку, где $N \leq 3k$. Тогда он сможет добавить к выложенным карточкам еще одну, потратив при этом еще не более $k$ рублей, т. е. затратив всего не более $x + k$ рублей.
Доказательство. * леммы проведем индукцией по числу $k$. База $k = 1$ очевидна. Пусть для всех $N \leq 3^{k-1}$ лемма доказана. Первый рубль Вася потратит на то, чтобы правильно выложить на стол $N$-ю карточку и карточки $A$ и $B$, уже лежащие на местах $\left [ \frac{N}{3} \right ]$ и $\left [ \frac{2N}{3} \right ]$. Тогда $N$-я карточка попадет в одну из трех частей, на которые другие две карточки разбивают уже выложенную на стол последовательность. Но карточки $A$ и $B$ разбивают лежащую на столе последовательность из $N - 1$ карточки на куски размером не более чем по $3^{k-1} - 1$ карточек, а значит Васе осталось определить место карточки с номером $N$ среди не более чем $3^{k-1} - 1$ карточек, потратив не более чем $k - 1$ рубль, а это можно сделать по предположению индукции. Таким образом, лемма доказана.
Теперь, используя лемму, подсчитаем Васины затраты на выкладывание всех 365 карточек. На выкладывание первых трех карточек Вася потратит 1 рубль. На добавление к ним карточек с номерами от 4 до 9 (всего 6 карточек) Вася потратит не более 2 рублей на каждую карточку. На карточки с 10 по 27 не более 3 рублей на каждую, с 28 по 81 не более 4 рублей, с 82 по 243 не более 5 рублей и наконец на карточки с номерами от 244 до 365 не более 6 рублей на каждую. Итого, Вася сможет выложить все карточки на стол в нужном порядке, потратив не более чем $1 + 6 \cdot 2 + 18 \cdot 3 + 54 \cdot 4 + 162 \cdot 5 + 122 \cdot 6 = 1845 < 2000$ рублей. Таким образом, Вася сможет потратить не более 2000 рублей.
Ответ. Может.
