|
|
 |
Условие
В лесном пункте обмена можно обменять• апельсин — на две груши,
• яблоко и грушу — на апельсин,
• апельсин и грушу — на яблоко.
По случаю праздника в пункте устроили акцию: за каждый обмен в подарок выдают коллекционный фантик. У лисы есть 30 яблок, 30 груш и 30 апельсинов. Какое максимальное количество фантиков она может получить?
Решение
Попробуем приписать фруктам цену в фантиках так, чтобы обмены были равноценными. В двух обменах груша + фрукт меняется на фантик + фрукт, поэтому пусть груша стоит 1 фантик, а апельсин и яблоко попробуем считать равноценными. Поскольку апельсин меняется на две груши и фантик, припишем апельсину и яблоку цену по 3 фантика. С такими ценами при обменах стоимость вещей у лисы в фантиках не меняется. При последнем обмене лиса получит фруктов стоимостью хотя бы два фантика, так что больше чем $30 + 30 \cdot 3 + 30 \cdot 3 − 2 = 208$ фантиков ей никак не получить.Осталось объяснить, как лисе получить 208 фантиков. Один из возможных алгоритмов состоит из двух стадий.
1 стадия (превращаем всё в апельсины). Лиса обменивает все яблоки и груши на апельсины и получает 30 фантиков. Теперь у лисы 60 апельсинов.
2 стадия (избавляемся от апельсинов). Последовательностью обменов 2А → А + 2Г → Я + Г → А можно уменьшить количество апельсинов на один, получив 3 фантика.
Лиса делает так 59 раз, и у неё останется один апельсин (и еще $59 \cdot 3 = 177$ фантиков). Осталось обменять этот последний апельсин на две груши и получить ещё фантик.
В итоге лиса получает $30 + 177 + 1 = 208$ фантиков, как и было обещано.
Ответ
208 фантиков.Замечания
1. Доказать, что больше 208 фантиков получить нельзя, можно и по-другому. Заметим, что каждый обмен не увеличивает количество не-груш, а обмен А → 2Г уменьшает его на 1. Поэтому обменов А→2Г может быть не больше 60. При всех остальных обменах количество груш уменьшается на 1. Если в конце ничего, кроме груш, не осталось, то последним ходом лиса обменяла апельсин на две груши. В этом случае в конце остаётся не меньше двух груш, следовательно, число обменов А + Г →Я и Я + Г →A не превышает $30 + 60 \cdot 2 − 2$. Если же в конце остается какой-то фрукт, отличный от груши, то обменов А → 2Г не больше 59, а остальных не больше $30 + 2 \cdot 59$. В обоих случаях суммарное количество обменов не превосходит 208.2. Нарисуем график: если у лисы в какой-то момент $x$ не-груш и $y$ груш, отметим на координатной плоскости точку $(x,y)$. Можно заметить, что если провести через каждую точку с целыми координатами прямую «с наклоном $(1, −3)$» (прямые с уравнениями $y=-3x+c$), то с каждым обменом лиса переходит с прямой на прямую на 1 ниже (на рисунке показаны точки, в которые можно попасть, сделав не более 3 обменов). Подумайте, как это связано с рассуждением в начале решения.
