Name: Anonymous 2011-06-13 16:03
The risk-fice currency exchange problem offers a risk-free way to make money. Suppose we have currencies c1...cn (For example. c1 might be dollars, c2 might be yen. etc.) P011511) for two currencies ci and cj, there is anexchannetrter such that you can exchange one unit of m for ut, units of u). Note that if > I. then you can make money simply by trading units of currency i into units of currency j and back aga1n. This almost never happens. but occasionally (because the updates for exchange rates do not happen quickly enough) for very short periods of time exchange traders can find a sequence of trades that can make risk-free money. That is. if there is a sequence of currencies c c, such that ojj), ut,),05.> 1. then trading one unit of m into c, and trading that into c, and so on will yield a profit. Design an efficient algorithm to detect if a risk-five currency exchange exists. (You need not actually find it.)