Imagine that you wish to exchange one currency for another. You realize that ins
ID: 3765022 • Letter: I
Question
Imagine that you wish to exchange one currency for another. You realize that instead of directly exchanging one currency for another, you might be better off making a series of trades through other currencies, winding up with the currency you want. Suppose that you can trade n different currencies, numbered 1.2, , n, where you start with currency 1 and wish to wind up with currency n. You are given, for each pair of currencies i and j, an exchange rate r_ij, meaning that if you start with d units of currency i, you can trade for dr_ij units of currency j. A sequence of trades may entail a commission, which depends on the number of trades you make. Let c_k be the commission that you are charged when you make k trades. Show that, if c_k = 0 for all k = 1, 2, ... , n, then the problem of finding the best sequence of exchanges from currency 1 to currency n exhibits optimal substructure. Then show that if commissions c_k are arbitrary values, then the problem of finding the best sequence of exchanges from currency 1 to currency n does not necessarily exhibit optimal substructure.Explanation / Answer
Currency conversion problem definition:
Consider that there are n currencies numbered.
In the trade of currency exchange one can trade n currencies numbered where he can start from 1 and ends up with currency.
If for each currency pair i and j the exchange rate is , then with d units of the currency i can be converted intounits of currency j.
is the commission that is charged on making k trades in a sequence.
Since the sequence of trades may entail a commission, a best sequence of trades that produces more commission can be obtained.
Case 1(if =0) :
Consider=0 for all k =1, 2, 3.., n. That is, there is no need to pay commission for making any number of trades. Then the finding best sequence of trade problem exhibits optimal sub structure.
Consider the rates between any two currencies:
1
2
.
.
.
n
1
0
r12
.
.
.
r1n
2
r21
0
r2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
n
rn1
rn2
.
.
.
0
And ck = 0 for making any number of trades.
Consider the starting currency 1 and ending currency n. now for the sequence of exchange from currency 1 to currency n may contain one currency k such that d.r1k.rkn > d.r1n. There are n-2 choices for k. the trading sequence is 1-k-n .
Now, the problem is sub-divided into two problems
Trading from currency 1 to currency k: there may a currency i such that d.r1i.rik > d.r1k. There are n-3 choices for i. The trading sequence is 1-i-n.
Trading from currency k to currency n:again there may a currency j such that d.rkj.rjn > d.rkn. There are n-3 choices for j. The trading sequence is k-j-n.
Again the above problems produce sub problems.
The solution to the sub problems is optimal and the solution to the main problem is obtained by combining the solution to the sub problems. The solution to the main problem is also optimal.
Therefore the given problem exhibits optimal sub structure and can be solved recursively by dynamic programming.
Case 2(if is arbitrary):
If the commission rate (ck) is an arbitrary random value, then the problem of finding the best sequence of trading does not exhibit an optimal sub-structure. The ck is an arbitrary random value means the commission is not same for all conversions.
Since the commission rate ck is arbitrary, even though there exists a currency k such that d.r1k.rkn > d.r1n, the solution may not the optimal.
There is no guarantee that the sub problems may give optimal solutions, because the commission rates are arbitrary values.
Hence, if the commission rate is arbitrary, then the finding a best sequence of trades problem do not exhibit optimal substructure property.
1
2
.
.
.
n
1
0
r12
.
.
.
r1n
2
r21
0
r2n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
n
rn1
rn2
.
.
.
0