hw04.pdf - Google Drive

C = {c1, c2, . . . , cn}: e.g., dollars, Euros, bitcoins, dogecoins, etc. For any pair of currencies ci , cj , there is an exchange rate ri,j : you can buy ri,j units of currency cj at the price of one unit of currency ci . Assume that ri,i = 1 and ri,j ≥ 0 for all i, j. The Foreign Exchange Market Organization (FEMO) has hired Oski, a CS170 alumnus, to make sure that it is not possible to generate a profit through a cycle of exchanges; that is, for any currency i ∈ C, it is not possible to start with one unit of currency i, perform a series of exchanges, and end with more than one unit of currency i. (That is called arbitrage.) More precisely, arbitrage is possible when there is a sequence of currencies ci1 , . . . , cik such that ri1,i2 · ri2,i3 ·· · ·· rik−1,ik · rik,i1 > 1. This means that by starting with one unit of currency ci1 and then successively converting it to currencies ci2 , ci3 , . . . , cik and finally back to ci1 , you would end up with more than one unit of currency

saved by

• Jameson Crate