Задача
В лесном пункте обмена можно обменять • апельсин — на две груши, • яблоко и грушу — на апельсин, • апельсин и грушу — на яблоко. По случаю праздника в пункте устроили акцию: за каждый обмен в подарок выдают коллекционный фантик. У лисы есть 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 фантиков.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь