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.