In this note, I try to solve two problems with brute force.

1. Discrete linear programming

---

A collegue once posed the following interesting problem.

\[\min_{\xi_k\in \{-1, 1\}}|\boldsymbol{\xi}^T\boldsymbol{\alpha}|\]

where \(\alpha_k = \sqrt{k}\).

The code implements “random trying”. Could also use particle swarm if one wants to.

2. Dynamic programming involving dice

---

Suppose we are playing a dice game where you get paid the amount the die shows. We fix the maximum number of rolls at \(n\), and let \(P(n)\) denote our optimal payoff. At each roll \(1\le i\le n\), you can either take your winnings, or give it up and roll again. We would like to compute \(E(n) := \mathbb{E}[P(n)]\). We then have the recurrence relation:

\[E(n+1) = \frac{1}{6}\sum_{i=1}^6\max(i, E(n))\]

which means the optimal situation in \(n\) rounds happens if we would choose to re-roll whenever the current roll is less than our expectation (of winnings) out of a \((n-1)\) roll game. It is intuitively clear if we let \(n\rightarrow \infty\), our winning is going to be closer to the maximum possible.