Обмены валют
В стране Лимпопо есть четыре национальные валюты: бананы , кокосы , еноты и доллары . Ниже приведены курсы обмена этих валют (одинаковые во всех обменных пунктах страны).
Число на стрелке показывает, сколько единиц, указанных в конце стрелки, можно получить за единицу, указанную в начале стрелки. Например одного енота можно обменять на бананов или на кокосов, один доллар на кокосов а один кокос - на доллара.
(При решении задачи любую валюту можно
дробить на сколь угодно мелкие части: например обменять енота на банана). Обмены в и обратно, в и обратно в Лимпопо запрещены.
Перевозить деньги через границу Лимпопо можно только в долларах. Дядя Вася приехал в Лимпопо, имея при себе долларов. Он может выполнять указанные выше операции обмена валют неограниченное количество раз, но не имеет никаких других источников дохода. Может ли он разбогатеть и увезти из Лимпопо долларов? Если да — объясните, как. Если нет, докажите.
Отметим, что в условии задачи не сказано явно, требуется ли получить не менее , или ровно . Ответ положительный для обеих трактовок условия. Хотя понятно, что решение для случая "ровно " решает так же и второй случай, мы приведем разные решения для обоих случаев.
а) Нужно получить не менее . Рассмотрим цикл Если обменивать деньги по такому циклу, то количество денег увеличивается. Действительно, если изначально было кокосов, то они обмениваются на енотов, которые в свою очередь обмениваются на бананов, которые обмениваются на кокосов. Таким образом, из кокосов получается кокосов.
Стратегия дяди Васи такова: вначале обменять долларов на кокосов. Затем обменивать их по указанному выше циклу, пока не получится более кокосов. Для этого цикл придется пройти раз, где таково, что . Поскольку , это неравенство равносильно неравенству Очевидно, натуральное nn, удовлетворяющее этим условиям, существует. Получившиеся в результате кокосы следует обменять на доллары, которых получится не менее .
б) Нужно получить ровно . Рассмотрим тот же цикл, что в пункте а), но будем каждый раз запускать по обменному циклу ровно кокосов, т. е. прибыльный -й кокос будем каждый раз откладывать. Тогда, сделав циклов, мы можем заработать ровно кокосов. Теперь стратегия, например, такова: обмениваем на кокосов, берем из этой и производим раз цикл, в результате чего получаем кокосов. Если , то в результате получим кокосов, которые обменяем обратно на .
Ответ:
Может.
**Примечание: **
Критерии
(-/+) Найден цикл, который увеличивает капитал, и более не сделано никаких значимых продвижений.
(+/-) Приведён алгоритм, дающий экспоненциальный рост капитала, однако не приведено доказательство того, что этот алгоритм когда-либо достигнет нужной суммы, или приведено неверное доказательство, например, неограниченность капитала "выведена" из его возрастания.
(+) Задача полностью решена. В случае приведения алгоритма с линейным приростом капитала обоснования того, что нужная сумма будет достигнута, не требуется.