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

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

Условие

  В некотором государстве ценятся золотой и платиновый песок. Золото можно менять на платину, а платину на золото по курсу, который определяется натуральными числами g и p так: x граммов золотого песка равноценны y граммам платинового, если  xp = yg  (числа x и y могут быть нецелыми). Сейчас у банкира есть по килограмму золотого и платинового песка, а  g = p = 1001.  Государство обещает каждый день уменьшать одно из чисел g и p на единицу, так что через 2000 дней они оба станут единицами; но последовательность уменьшений неизвестна. Может ли банкир каждый день менять песок так, чтобы в конце гарантированно получить хотя бы по 2 кг каждого песка?


Решение

  Докажем, что если вначале у банкира по 1 кг каждого песка, и  g = p = k,  то в конце хотя бы одного песка будет не больше  2 – 1/k кг.  Для этого достаточно доказать, что если вначале у банкира по     кг песка, то в конце он не может получить каждого песка больше чем по килограмму.
  Назовём состоянием банкира число  S = Gp + Pg,  если у него G кг золота и P кг платины. Заметим, что в результате обмена песка по курсу состояние не меняется. Покажем индукцией по числу дней, что наибольшее гарантированное состояние банкира в день, когда курсы равны g и p, не превосходит     В начальный день это так.
  Пусть в некоторый день это так. Ясно, что при этом либо     либо     (Оба неравенство выполнены одновременно только в случае, когда оба превращаются в равенства.)
  Пусть выполнено первое неравенство, то есть     Тогда государство уменьшит p на 1 (случай  g > p = 1  будет разобран ниже). При этом из состояния вычтется G, то есть оно станет равно

 
что и требовалось.
  Случай, когда выполнено второе неравенство, в частности, случай  g > p = 1,  разбирается "симметрично".
  В итоге, в последний день  (g = p = 1)  состояние будет не больше 2, а значит, количество какого-то песка будет не больше килограмма.


Ответ

Не может.

Замечания

1. Полученная оценка точна. Если банкир каждый день будет делать так, чтобы массы золотого и платинового песков относились как  g(g – 1) : p(p – 1)  (что возможно), то его состояние каждый день будет равняться     В частности в последний день у него будет ровно 2 кг песка, и он сможет его обменять так, что каждого сорта будет по одному килограмму.

2. 10 баллов.

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

олимпиада
Название Турнир городов
Турнир
Номер 36
Дата 2014/15
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 7

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

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