QuantMax

Games, decision theory and puzzles

7 lessons · 8 equations. Each lesson below gives its formulas and key rules; open the lesson for the full explanation.

Pricing a game: EV, re-rolls and when to stop

The Bellman equation

V(s)=max⁡(stop(s), E[V(s′)]−c)V(s) = \max\Big(\text{stop}(s),\ \mathbb{E}\big[V(s')\big] - c\Big)

Every stopping game is this one line: at each state, take the better of stopping now and paying to continue into the next state. Finite horizons are solved backwards from the last decision; infinite ones by guessing the stopping region and checking it.

Remember

  • Value =max⁡(hold, continue)=\max(\text{hold},\ \text{continue}), evaluated by backward induction.

Poker for traders: pot odds, ranges and bluffing frequency

Pot odds

equity needed=callpot after the bet+call\text{equity needed} = \frac{\text{call}}{\text{pot after the bet} + \text{call}}

The break-even win probability for calling. Above it, calling is profitable; below, folding is.

Minimum defence frequency

MDF=PP+b\text{MDF} = \frac{P}{P + b}

Facing a bet of bb into a pot of PP, you must continue at least this often or the bettor profits by betting any two cards. It is the mirror image of the bluffer’s break-even fold frequency, b/(P+b)b/(P + b).

Remember

  • Equity needed =call/(pot after the bet+call)= \text{call} / (\text{pot after the bet} + \text{call}).

Logic puzzles: information bounds and common knowledge

Key rules

  • Count information first: nn three-way weighings distinguish at most 3n3^n outcomes.
  • A minimum-number answer needs a bound *and* a construction.
  • Common knowledge is stronger than everyone knowing, and the difference drives the islander puzzle.

Measuring and timing puzzles

Bezout’s identity

{ax+by:x,y∈Z}={kgcd⁡(a,b):k∈Z}\{ax + by : x, y \in \mathbb{Z}\} = \{k\gcd(a, b) : k \in \mathbb{Z}\}

The amounts two jugs can produce, the times two timers can measure and the positions two step sizes can reach are all multiples of the greatest common divisor. It decides whether a puzzle has a solution before you search for one.

Remember

  • Lighting both ends halves a burn time whatever the rate, because only the total matters.

Weighing, searching and strategy puzzles

How many coins can three weighings handle?

Nmax⁡=3n−32 (no reference),3n−12 (with one known good coin)N_{\max} = \frac{3^n - 3}{2}\ \text{(no reference)}, \qquad \frac{3^n - 1}{2}\ \text{(with one known good coin)}

For one counterfeit that may be heavy or light, nn weighings can both find it and say which way it is off for up to (3n−3)/2(3^n - 3)/2 coins — twelve for three weighings. A spare coin known to be genuine lets the first weighing be unbalanced in numbers, raising the limit to thirteen.

More eggs

max floors with e eggs and d drops=∑i=1e(di)\text{max floors with } e \text{ eggs and } d \text{ drops} = \sum_{i=1}^{e}\binom{d}{i}

Each drop either breaks an egg or does not, so the floors you can resolve satisfy f(d,e)=f(d−1,e−1)+f(d−1,e)+1f(d, e) = f(d-1, e-1) + f(d-1, e) + 1, which sums to this binomial expression. With two eggs it is d+(d2)=d(d+1)/2d + \binom d2 = d(d+1)/2.

Remember

  • A balance gives three outcomes, so nn weighings separate 3n3^n cases — twelve coins need three.

Nim, symmetry strategies and who wins

Nim

losing position  ⟺  a1⊕a2⊕⋯⊕an=0\text{losing position} \iff a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0

Several piles; a move removes any positive number from one pile; the player taking the last object wins. The XOR — the "Nim-sum" — of the pile sizes decides everything.

Sprague–Grundy numbers

g(x)=mex⁡{g(y):y a move from x},g(G1+G2)=g(G1)⊕g(G2)g(x) = \operatorname{mex}\{g(y) : y \text{ a move from } x\}, \qquad g(G_1 + G_2) = g(G_1) \oplus g(G_2)

Every impartial game position behaves like a single Nim pile of size g(x)g(x), where mex is the smallest non-negative integer not in the set. A sum of independent games is won by XOR-ing the Grundy numbers, exactly as in Nim; the position is losing when the XOR is zero.

Remember

  • A losing position is one where every move leads to a winning position.

Detailed formula cards