Обмены валют
В стране Лимпопо есть четыре национальные валюты: бананы (Б), кокосы (К), еноты ($\epsilon$) и доллары (\$). Ниже приведены курсы обмена этих валют (одинаковые во всех обменных пунктах страны). Число на стрелке показывает, сколько единиц, указанных в конце стрелки, можно получить за единицу, указанную в начале стрелки. Например одного енота можно обменять на 6 бананов или на 11 кокосов, один доллар на 10 кокосов а один кокос - на 1/15 доллара. (При решении задачи любую валюту можно дробить на сколь угодно мелкие части: например обменять 101/43 енота на 606/43 банана). Обмены \$ в $\epsilon$ и обратно, \$ в Б и обратно в Лимпопо запрещены. Перевозить деньги через границу Лимпопо можно только в долларах. Дядя Вася приехал в Лимпопо, имея при себе 100 долларов. Он может выполнять указанные выше операции обмена валют неограниченное количество раз, но не имеет никаких других источников дохода. Может ли он разбогатеть и увезти из Лимпопо 200 долларов? Если да — объясните, как. Если нет, докажите.
Решение
Отметим, что в условии задачи не сказано явно, требуется ли получить не менее 200\$, или ровно 200\$. Ответ положительный для обеих трактовок условия. Хотя понятно, что решение для случая "ровно 200\$" решает так же и второй случай, мы приведем разные решения для обоих случаев. а) Нужно получить не менее 200\$. Рассмотрим цикл $K$ —> $\epsilon$ —> $Б$ —> $K$. Если обменивать деньги по такому циклу, то количество денег увеличивается. Действительно, если изначально было $x$ кокосов, то они обмениваются на $\frac{x}{11}$ енотов, которые в свою очередь обмениваются на $\frac{6x}{11}$ бананов, которые обмениваются на $\frac{12x}{11}$ кокосов. Таким образом, из $x$ кокосов получается $\frac{12x}{11}$ кокосов. Стратегия дяди Васи такова: вначале обменять 100 долларов на 1000 кокосов. Затем обменивать их по указанному выше циклу, пока не получится более 3000 кокосов. Для этого цикл придется пройти $n$ раз, где $n$ таково, что $(\frac{12}{11})^n$>3. Поскольку $\frac{12}{11}>1$, это неравенство равносильно неравенству $n>\log_{\frac{12}{11}}{3}$. Очевидно, натуральное $n$, удовлетворяющее этим условиям, существует. Получившиеся в результате кокосы следует обменять на доллары, которых получится не менее $\frac{3000}{15}=200$. б) Нужно получить ровно 200\$. Рассмотрим тот же цикл, что в пункте а), но будем каждый раз запускать по обменному циклу ровно 11 кокосов, т. е. прибыльный 12-й кокос будем каждый раз откладывать. Тогда, сделав $n$ циклов, мы можем заработать ровно $n$ кокосов. Теперь стратегия, например, такова: обмениваем 100\$ на 1000 кокосов, берем 11 из этой 1000 и производим $n$ раз цикл, в результате чего получаем $1000+n$ кокосов. Если $n=2000$, то в результате получим 3000 кокосов, которые обменяем обратно на 200\$ Ответ: Может. Примечание: Критерии (-/+) Найден цикл, который увеличивает капитал, и более не сделано никаких значимых продвижений. (+/-) Приведён алгоритм, дающий экспоненциальный рост капитала, однако не приведено доказательство того, что этот алгоритм когда-либо достигнет нужной суммы, или приведено неверное доказательство, например, неограниченность капитала "выведена" из его возрастания. (+) Задача полностью решена. В случае приведения алгоритма с линейным приростом капитала обоснования того, что нужная сумма будет достигнута, не требуется.