Linear programming has been used many times before to detect arbitrage in FX trading. However, to use in live trading these solutions require solving a linear program after each price update. So I ask a different question: for each pair, what is the minimum exchange rate such that an arbitrage exists? This way, if the exchange rate updates for a pair, all we have to do is compare the new exchange rate to the minimum exchange rate for an arbitrage to exist.
Problem A2 of the 2018 Putnam Competition states:
Let \(S_1, S_2, \dots, S_{2^n-1}\) be the nonempty subsets of \(\{1,2,\dots,n\}\) in some order, and let \(M\) be the \((2^n-1) \times (2^n-1)\) matrix whose \((i,j)\) entry is \[ m_{ij} = \begin{cases} 0 & \mbox{if }S_i \cap S_j = \emptyset; \\ 1 & \mbox{otherwise.} \end{cases} \] Calculate the determinant of \(M\).
First thing to note is that we can generate all nonempty subsets of \(\{1, 2, \ldots, n\}\) by converting each integer from \(1\) to \(2^{n} - 1\) to binary.
Problem A1 of the 2019 Putnam Competition states:
Determine all possible values of the expression \(A^3 + B^3 + C^3 − 3ABC\) where \(A\), \(B\), and \(C\) are nonnegative integers.
In the real test, you can’t use a computer. Nevertheless, let’s generate some examples in Python. We’ll generate all \(A\), \(B\), \(C\) with \(10 \geq A \geq B \geq C \geq 0\) and look at all unique values of the expression less than 30.