ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109833
Темы:    [ Перестановки и подстановки (прочее) ]
[ Индукция (прочее) ]
[ Процессы и операции ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Гарбер М.

На столе лежат 365 карточек, на обратной стороне которых написаны различные числа. За один рубль Вася может выбрать три карточки и попросить Петю положить их слева направо так, чтобы числа на карточках располагались в порядке возрастания. Может ли Вася, потратив 2000 рублей, с гарантией выложить все 365 карточек на стол слева направо так, чтобы числа на них располагались в порядке возрастания?


Решение

  Лемма. Пусть за x рублей Вася смог выложить в нужном порядке на стол некоторые  N – 1  карточку, где  N ≤ 3k.  Тогда он сможет добавить к выложенным карточкам еще одну, потратив при этом еще не более k рублей.
  Доказательство проведём индукцией по k. База  (k = 1)  очевидна.
  Шаг индукции. Пусть  N = 3mr ≤ 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  рублей.


Ответ

Может.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2005
Этап
Вариант 5
Класс
Класс 9
задача
Номер 05.5.9.4

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .