Proof that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission C_k = 0 for all k trades.

Let U₁, U₂, ..., U_n be a collection of currencies. We can represent all possible sequences from U₁ to U_n as a directed graph where each node is a currency and is connected to each other node in the graph. Each directed edge represents a currency conversion value.  

This problem is somewhat similar to the Unweighted Shortest Path problem only in this case, rather than hitting the fewest nodes from the start to end points, we wish to maximize the resulting value when exchanging from U₁ along the sequence (path) to U_n

For simplicity, assume nodes are only visited once and that U₁ ≠ U_n

Any path P from U₁ -->_P U_n can be broken into sub-paths U₁ -->_P1 w -->_P2 U_n (where node w can equal U_1, U_n, or some other currency in the collection). The number of edges in P equals the sum of edges in P1 and P2.

We claim that if P is the optimal path from U₁ to U_n (that is, the sequence will offer the highest return of currency exchange) then P1 must be the optimal path from U₁ to w and P2 must be the optimal path from w to U_n

By the cut and paste argument, if there was a more optimal path P1’ from U₁ to w, then we could cut out P1 and past in P1’ to give U₁ -->_P1’ w -->_P2 U_n as a more optimal path than P. However, this contradicts P’s optimality. Likewise, if there was a more optimal path P2’ from w to U_n , then we could cut out P2 and past in P2’ to give U₁ -->_P1 w -->_P2’ U_n as a more optimal path than P. However, this contradicts P’s optimality.

This proves that finding the best sequence of exchanges for currencies exhibits optimal substructure when commission C_k = 0 for all k trades. 

When C_k are arbitrary values for all k trades, finding the best sequence of exchanges no longer has optimal substructure. This is because the sub-problem of finding the best return along the path is not independent from the problem of minimizing commissions based on the number of trades. What was once an optimal path when C_k = 0 could no longer be optimal when C_k is some other value.