Identify rules and preconditions first, then choose your technique: find P-positions in combinatorial games, seek equilibria in strategic games, define explicit sample spaces in probability, and apply enumeration, recurrence, or search for numerical puzzles. All stone-taking games below follow the normal play convention (the player taking the last stone wins).
Algorithm Complexity Cheat Sheet · Python 3 Cheat Sheet · Chess Moves & Rules Cheat Sheet
Impartial Combinatorial Games
Both players have identical legal moves from any given state. A "losing position" (P-position) means the player whose turn it is will lose under optimal play by the opponent.
Nim Game
Nim XOR Sum
Rules: On each turn, a player removes any positive number of objects from exactly one heap, up to the entire heap.
Strategy: An XOR sum (nim-sum) of 0 is a losing state (P-position). When non-zero ($s \ne 0$), reduce a heap of size $x$ to $x \oplus s$ such that the new XOR sum becomes 0.
Example: $3 \oplus 4 \oplus 5 = 2$. First player takes 2 from the heap of 3, leaving $1 \oplus 4 \oplus 5 = 0$.
Misère play (last player to move loses) requires a separate end-game adjustment.
Principle Explained
From an XOR sum of 0, any legal move necessarily transitions to a non-zero state. From any non-zero state, there is always at least one legal move that transitions to an XOR sum of 0. Always returning 0 to the opponent guarantees victory. Here $s$ represents the XOR sum of all current heap sizes.
Bash Game
Bash Game Modular Arithmetic
Rules: A single pile of $n$ items. Each player removes between $1$ and $m$ items per turn.
Strategy: Multiples of $m+1$ are losing states. If $n$ is not a multiple, take $n \bmod (m+1)$ on the first move; thereafter, if the opponent takes $k$, you take $m+1-k$.
Example: When taking $1\text{--}4$ items, $n=30$ is a losing state for the first player; from $n=32$, take 2 on the first move.
Permitted removals must be consecutive integers $1\text{--}m$; arbitrary discrete subtraction sets require Sprague-Grundy analysis.
Principle Explained
If the opponent takes $k$ items, taking $m+1-k$ ensures that each round of two turns removes exactly $m+1$ items. Starting from a multiple of $m+1$, any move leaves that set; starting outside it, a single move returns to it.
Wythoff's Game
Wythoff's Game Golden Ratio Pairs
Rules: Two piles of objects. On a turn, remove any number from one pile, or remove the same positive number from both piles simultaneously.
Classification: Order the piles as $a \le b$ and let $k = b - a$. The position is a losing state if and only if $a = \lfloor k\varphi \rfloor$, where $\varphi = (1+\sqrt{5})/2 \approx 1.618$.
Example: $(1,2)$, $(3,5)$, $(4,7)$, $(6,10)$, $(8,13)$ are all losing pairs (P-positions).
Includes terminal state $(0,0)$. The positions are determined strictly by the floor function, not every point along the line.
Principle Explained
By Beatty's theorem, the sequences $\lfloor k\varphi \rfloor$ and $\lfloor k\varphi^2 \rfloor$ partition the positive integers, and $b_k - a_k = k$. No single move can transition between two losing pairs, whereas any other position can reach some losing pair in one move. For instance, from $(2,3)$, reduce the second heap to 1 to reach sorted pair $(1,2)$.
Fibonacci Nim
Fibonacci Nim Zeckendorf's Theorem
Rules: First player cannot take all stones. Thereafter, each player may take at most twice the number taken by the previous player on their immediately preceding turn.
Strategy: Decompose $n$ into a sum of non-consecutive Fibonacci numbers; let $z(n)$ be the smallest term. If the current upper limit $r \ge z(n)$, taking $z(n)$ wins; otherwise, the state is a losing position.
Example: $20 = 13 + 5 + 2$; first player takes 2. If the initial $n$ is itself a Fibonacci number, the first player has no winning move.
Evaluate both remaining stones $n$ and the current removal ceiling $r$.
Principle Explained
Every positive integer can be uniquely represented as a sum of non-consecutive Fibonacci numbers (Zeckendorf's theorem). A greedy algorithm repeatedly subtracting the largest Fibonacci number $\le$ the remainder yields the minimal term $z(n)$. The initial ceiling is $n-1$; if $n$ is a Fibonacci number, $z(n) = n > n-1$, making the first move unable to reach the winning term.
Sprague–Grundy Theorem
SG Theorem mex & XOR Equivalence
Calculation: The Grundy value of a game state is the mex (minimum excluded non-negative integer) of the Grundy values of all reachable next states; terminal states have value 0.
Strategy: The SG value of composite independent games is the bitwise XOR sum of component values; total value 0 is a losing state, while non-zero states can be reduced to 0 in one move.
Example: $\operatorname{mex}{0,1,3} = 2$. Two sub-games with values 3 and 5 combine to $3 \oplus 5 = 6$.
Applies to impartial games under normal play with finite transitions; a player moves in exactly one sub-game per turn.
Principle Explained
Every impartial game is equivalent to a one-heap Nim game of size equal to its Grundy value. For terminal states without transitions, $\operatorname{mex}\emptyset = 0$. In standard Nim, a single heap of $n$ stones satisfies $g(n) = n$, but for arbitrary games, stone counts must not be confused with Grundy values.
Chomp
Chomp Strategy Stealing
Rules: A grid of chocolate with the bottom-left square poisoned. Pick any square to eat it along with all squares above and to the right; eating the poisoned square loses.
Result: For any rectangular grid with $m \times n > 1$, the first player possesses a winning strategy, provable via strategy stealing.
Limitation: The existence proof is non-constructive and does not reveal the general winning opening move.
Eating only the top-right square is the basis of the proof, not necessarily the universal winning move for all board shapes.
Principle Explained
Suppose the first player takes just the single top-right corner. If this move is winning, the claim holds. If not, the second player must have a winning response $M$. But because that response leaves a sub-board reachable on the very first turn, the first player could have played $M$ initially, "stealing" the strategy. Hence the second player cannot possess a winning strategy, proving a first-player win exists.
Strategic Games
Nash Equilibrium: A strategy profile where no player can unilaterally deviate to improve their own payoff given the strategies of others.
Prisoner's Dilemma
Prisoner's Dilemma Dominant Strategy
Payoffs: (Player 1, Player 2).
| Player 1 \ Player 2 | Cooperate | Defect |
|---|---|---|
| Cooperate | (3,3) | (0,5) |
| Defect | (5,0) | (1,1) |
Conclusion: Defection strictly dominates cooperation regardless of the opponent's choice; the unique Nash equilibrium is mutual defection $(1,1)$.
Insight: The equilibrium $(1,1)$ is Pareto-dominated by mutual cooperation $(3,3)$; individual rationality leads to collective inefficiency.
Principle Explained
If the opponent cooperates, defecting yields $T=5 > R=3$. If the opponent defects, defecting yields $P=1 > S=0$. Defection is a strictly dominant strategy. Standard models also impose $2R > T+S$ to ensure that mutual cooperation yields higher total welfare than alternating exploitation.
Rock–Paper–Scissors
Rock–Paper–Scissors Mixed Strategy Equilibrium
Rules: Simultaneous choices where rock beats scissors, scissors beats paper, and paper beats rock.
Strategy: Under standard payoffs (+1 win, -1 loss, 0 draw), randomizing uniformly with probability $1/3$ each achieves an expected payoff of 0; no pure-strategy equilibrium exists.
Asymmetric payoffs alter the equilibrium probabilities; uniform mixing applies strictly to symmetric payoffs.
Principle Explained
Every pure strategy has a unique best response that defeats it, ruling out pure Nash equilibria. In a zero-sum symmetric game, mixing with equal weights $(1/3, 1/3, 1/3)$ makes the opponent completely indifferent across all their choices, yielding zero expected payoff.
Pirate Game
Pirate Game Backward Induction
Rules: 5 rational pirates sequentially propose how to divide 100 gold coins; if at least $50%$ vote in favor, the proposal passes; otherwise the proposer is executed.
Strategy: Solve backward from the final 2-pirate scenario. Pirate 1 votes for themselves and gives 1 coin each to Pirates 3 and 5, who would receive 0 in the next round.
Assumes the proposer votes; pirate preferences are: maximize survival, maximize coins, cast tie-breaking votes against the proposer. Strict super-majority rules alter the distribution.
Principle Explained
Induction from the end: with only Pirates 4 and 5 remaining, Pirate 4 votes for themselves and takes all 100 coins. With 3 pirates, Pirate 3 buys Pirate 5's vote with 1 coin (giving $(99,0,1)$). With 4 pirates, Pirate 2 gives 1 coin to Pirate 4 (giving $(99,0,1,0)$). Thus Pirate 1 needs two votes and buys Pirates 3 and 5 with 1 coin each, keeping 98.
Centipede Game
Centipede Game Subgame Perfection
Rules: Players alternate deciding whether to stop or continue; continuing increases the total pot but passes the decision to the opponent.
Conclusion: In the final round, Player B prefers 16 over continuing for 8. Inducing backward, Player A stops immediately on round 1.
Relies on finite known horizon and common knowledge of rationality; imperfect information or altruistic models yield cooperation.
Principle Explained
Payoffs are written as (Player A, Player B). On the final decision node, Player B chooses stop for 16 rather than continue for 8. Foreseeing this, Player A on the preceding node stops for 8 rather than 4. Propagating backward, Player B would stop for 4 rather than 2, and Player A stops on round 1 for 2 rather than 1.
Repeated Prisoner's Dilemma
Infinitely Repeated PD Grim Trigger Strategy
Strategy: In an infinitely repeated game, both players cooperate until either defects; after any defection, both defect forever (Grim Trigger).
Condition: Cooperation is sustainable as a subgame perfect equilibrium whenever the discounted value of sustained cooperation outweighs a one-shot deviation.
Example: For $T=5, R=3, P=1$, cooperation is sustained whenever discount factor $\delta \ge 1/2$.
Tit-for-Tat copies the opponent's previous move and requires separate analysis; finitely repeated games with known horizon unravel via backward induction.
Principle Explained
Discounted value of perpetual cooperation is $R/(1-\delta)$. A player defecting once collects $T$ immediately and receives $P/(1-\delta)$ thereafter. Comparing these yields the threshold. Because mutual defection is a static Nash equilibrium, the eternal punishment threat is credible.
Chicken Game
Chicken Game Anti-Coordination
Payoffs: (Player 1, Player 2).
| Player 1 \ Player 2 | Swerve (S) | Straight (G) |
|---|---|---|
| Swerve (S) | (0,0) | (−1,+1) |
| Straight (G) | (+1,−1) | (−10,−10) |
Conclusion: One swerving while the other drives straight forms two pure-strategy Nash equilibria; mutual confrontation $(-10,-10)$ is catastrophic.
Mixed Equilibrium: Both players randomize, driving straight with probability $q = 1/10$.
Only credible, observable commitments (e.g., throwing the steering wheel out the window) reshape the game; cheap talk does not alter the strategy space.
Principle Explained
When the opponent swerves, driving straight gives $+1 > 0$. When the opponent goes straight, swerving gives $-1 > -10$. If the opponent drives straight with probability $q$, the expected payoff of driving straight is $1-11q$ while swerving gives $-q$. Setting them equal yields the mixed strategy $q = 1/10$.
Probability & Statistics
Probabilistic conclusions depend on sample spaces, sampling mechanisms, and information conditioning. Clarify assumptions before computing conditional probabilities or expectations.
Monty Hall Problem
Monty Hall Host Protocol Matters
Conditions: One car and two goats placed uniformly at random behind three doors. The host knows where the car is, always reveals a goat behind an unchosen door, and always offers the option to switch.
Conclusion: Staying wins with probability $1/3$; switching wins with probability $2/3$.
Intuition: Switching wins whenever the initial choice was a goat, which occurs with probability $2/3$.
If the host opens a door randomly (Monty Fall) or only offers a switch when you picked the car, the probabilities change completely.
Principle Explained
Assume Door 1 is initially chosen. There are three equally likely states: if the car is behind Door 1, switching loses; if behind Door 2 or Door 3, the host is forced to reveal the other goat, so switching wins in both cases.
Birthday Problem
Birthday Problem Complementary Probability
Conditions: Birthdays are independent, identically and uniformly distributed across 365 days, ignoring leap years. Problem evaluates whether any two people share a birthday.
Results: With 23 people, $P \approx 50.7%$; with 50 people, $P \approx 97.0%$; with 70 people, $P \approx 99.9%$.
Method: Calculate the probability that all $n$ birthdays are distinct, then take the complement.
Valid for $n \le 365$; for $n \ge 366$, $P=1$ by the Pigeonhole Principle. "Sharing a birthday with *you*" is a different question.
Principle Explained
Person 1 can have any birthday; Person 2 has $364/365$ chance of avoiding Person 1; Person 3 has $363/365$, and so forth. With 23 people, there are $\binom{23}{2} = 253$ distinct pairs. Pairing count grows quadratically:
For hash collisions across $M$ buckets, the collision threshold scales as $\mathcal{O}(\sqrt{M})$.
Boy or Girl Paradox
Boy or Girl Conditioning & Sampling Protocol
Conditions: Assume independent binary sexes with $P(B)=P(G)=1/2$. A two-child family is drawn at random, conditioned on having "at least one boy".
Conclusion: Ordered by birth, the sample space reduces to ${BB, BG, GB}$; probability both are boys is $1/3$.
Variants: If told "the elder child is a boy", probability is $1/2$. If a child is randomly encountered and observed to be a boy, the sibling is a boy with probability $1/2$.
The statement "at least one boy" is ambiguous without specifying the observation protocol.
Principle Explained
Conditioning on family properties: ${BB, BG, GB, GG}$ each have probability $1/4$. Excluding $GG$ leaves three equiprobable outcomes, of which $BB$ is one. Encountering a random child is different: a $BB$ family provides two chances to observe a boy, weighting $BB$ twice as heavily as $BG$ or $GB$, yielding posterior probability $1/2$.
Medical Testing & False Positives
Base Rate & Bayes Base Rate Fallacy
Parameters: Disease prevalence $1%$, test sensitivity $99%$, false positive rate $5%$.
In 10,000 individuals: 100 diseased produce 99 positive tests; 9,900 healthy produce 495 false positive tests.
Conclusion: Out of 594 total positive results, only 99 actually have the disease: posterior probability is $1/6 \approx 16.7%$.
Test sensitivity is $P(+\mid D)$, which must not be confused with the positive predictive value $P(D\mid +)$.
Principle Explained
Let $p$ be prevalence, $s$ sensitivity, and $f$ false positive rate. Applying Bayes' Theorem:
When a condition is rare ($p$ is small), false positives from the large healthy population easily outnumber true positives from the infected cohort.
St. Petersburg Paradox
St. Petersburg Paradox Expected Value vs. Utility
Rules: Repeatedly flip a fair coin until heads appears for the first time on the $k$-th flip; payoff is $2^k$.
Paradox: Every outcome contributes $2^k \times 2^{-k} = 1$ to expected winnings; the theoretical expectation is infinite.
Resolution: Real decision makers evaluate expected utility rather than monetary value. With logarithmic utility $u(x) = \ln x$, the certainty equivalent is 4.
A certainty equivalent of 4 depends on the chosen utility function; initial wealth, entry fees, and bankroll caps alter pricing.
Principle Explained
The probability of first heads on flip $k$ is $2^{-k}$. Under logarithmic utility $u(X) = \ln X$:
In physical reality, the house has finite capital $W$, capping payouts at $2^K \le W$, which renders expected value finite and modest (e.g., if cap is $2^{30} \approx 10^9$, expected value is only 30).
Simpson's Paradox
Simpson's Paradox Confounding & Reversal
Phenomenon: Success rate of group A exceeds group B in every individual subgroup, yet reverses in aggregate data.
| Subgroup | Group A Success / Total | Group B Success / Total |
|---|---|---|
| Easy Cases | 4/5 = 80% | 350/500 = 70% |
| Hard Cases | 20/100 = 20% | 1/10 = 10% |
| Combined | 24/105 ≈ 22.9% | 351/510 ≈ 68.8% |
Causal inference and DAG modeling are required to determine whether to condition on the confounder; neither partitioned nor aggregate numbers are universally "correct".
Principle Explained
Aggregate success is a weighted average of subgroup rates. Here, 100 out of 105 of A's trials were assigned to the hard category, whereas 500 out of 510 of B's trials were assigned to the easy category. Unbalanced sample allocation across subgroups creates the paradox.
Numerical Puzzles & Search
Fix allowed operations and constraints first, then apply enumeration, congruences, recurrences, binary division, or optimal stopping.
24 Game
24 Game Expression Tree Search
Rules: Use four given numbers exactly once with $+$, $-$, $\times$, $\div$ and parentheses to yield 24; intermediate numbers may be fractions or negative.
Method: Recursively pick two numbers, combine them with an operator, and recurse on the remaining three numbers; check non-commutative order for subtraction and division, guarding against division by zero.
Example: $3, 3, 8, 8$ yields $8 \div (3 - 8 \div 3) = 24$.
Use exact rational arithmetic to prevent floating-point rounding errors.
Principle Explained
Four numbers have 5 distinct binary bracket topologies. The unpruned brute-force search space has an upper bound of $4! \times 4^3 \times 5 = 7,680$ expressions (including commutative duplicates and divide-by-zero errors).
Drawing 4 cards from $1\text{--}13$ with replacement yields 1,820 multisets. Under standard four-operation rules, exactly 1,362 multisets are solvable and 458 are impossible.
Chinese Remainder Theorem
Chinese Remainder Theorem Simultaneous Congruences
Problem: Find the smallest positive integer $x$ satisfying $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, and $x \equiv 2 \pmod 7$.
Solution: Smallest positive solution is 23; general integer solution is $x = 23 + 105k$ for $k \in \mathbb{Z}$.
Theorem: If moduli $m_1, m_2, \dots, m_k$ are pairwise coprime, the system of simultaneous congruences has a unique solution modulo $M = \prod m_i$.
Moduli must be pairwise coprime; non-coprime moduli require consistency checks of remainders modulo pairwise GCDs.
Principle Explained
Notice that $70 \equiv 1 \pmod 3$ and $70 \equiv 0 \pmod{35}$; $21 \equiv 1 \pmod 5$ and $21 \equiv 0 \pmod{21}$; $15 \equiv 1 \pmod 7$ and $15 \equiv 0 \pmod{15}$. Constructing $2 \times 70 + 3 \times 21 + 2 \times 15 = 233$, and reducing modulo $105 = 3 \times 5 \times 7$, yields $23$.
Josephus Problem
Josephus Problem Recurrence & Bit Shifts
Rules: $n$ people numbered $1\text{--}n$ stand in a circle; counting starts at 1, every $k$-th person is eliminated, and the circle closes until one remains.
Result: For step $k=2$, let $n = 2^m + l$; the surviving position is $2l + 1$. For $n=41 = 32 + 9$, survivor is $2 \times 9 + 1 = 19$.
General Case: Solve for arbitrary $k$ via dynamic programming recurrence from $1$ to $n$.
Verify 0-indexed vs. 1-indexed labeling conventions before applying recurrences.
Principle Explained
Under 1-indexed numbering, the recurrence is:
For $k=2$, the closed form is equivalent to a 1-bit left circular shift of the binary representation of $n$: $41 = 101001_2 \to 010011_2 = 19$.
Binary Search
Binary Search One Bit per Query
Problem: A secret integer lies in $1\text{--}N$; each query receives a reliable yes/no answer.
Strategy: Query whether the number is greater than the interval midpoint, halving remaining candidates each step.
Conclusion: Worst-case queries require $\lceil \log_2 N \rceil$; searching $1\text{--}1,000$ requires at most 10 questions.
Assumes noiseless binary answers; noisy channels with errors require error-correcting codes (Rényi-Ulam game).
Principle Explained
$q$ binary queries can distinguish at most $2^q$ outcomes. Distinguishing $N$ states requires $2^q \ge N$. Midpoint bisection balances the entropy across branches, minimizing worst-case search depth.
Secretary Problem
Secretary Problem Optimal Stopping & 1/e
Conditions: $n$ candidates arrive in uniform random order with distinct ranks. Decisions are immediate and irrevocable; objective is to select the single best candidate.
Strategy: Reject the first $r$ candidates unconditionally, tracking their maximum quality; thereafter, select the first candidate who exceeds all observed candidates.
Conclusion: As $n \to \infty$, optimal cutoff is $r \approx n/e$, yielding success rate $1/e \approx 36.8%$. For $n=10$, optimal $r=3$, succeeding with $\approx 39.9%$.
$1/e \approx 37\%$ is an asymptotic rule; unknown population size or recall allowances require modified stopping rules.
Principle Explained
If the overall best applicant appears at position $k > r$, the algorithm succeeds if and only if the best among the first $k-1$ candidates occurred within the rejected sample $1\text{--}r$. Summing over $k$:
Setting $x = r/n$ as $n \to \infty$, the sum converges to $-x \ln x$, maximized at $x = 1/e$.
Water Jug Problem
Water Jug GCD & State-Space BFS
Rules: Two unmarked jugs of capacities $a$ and $b$; unlimited water source. Allowed actions: fill, empty, or pour from one jug into another until source is empty or target is full.
Solvability: Measuring $c$ liters in either jug is possible if and only if $\gcd(a,b)$ divides $c$, with $0 \le c \le \max(a,b)$.
Example: Measuring 4 liters using 3L and 5L jugs requires 6 steps, reaching $(3,4)$.
If the goal requires measuring $c$ as the sum of both jugs or prohibits waste, re-evaluate constraints.
Principle Explained
Any sequence of valid operations maintains water volumes as integer linear combinations of $a$ and $b$. By Bézout's identity, $ax + by = c$ is solvable if and only if $\gcd(a,b) \mid c$. Finding the minimum number of steps corresponds to Breadth-First Search (BFS) on the state graph of pairs $(x,y)$.
Common Mathematical Notations
| Symbol | Definition & Quick Explanation |
|---|---|
| $\oplus$ | Bitwise XOR operator (Nim-sum) |
| $\operatorname{mex}$ | Minimum excluded non-negative integer, e.g., $\operatorname{mex}{0,1,3} = 2$ |
| $\lfloor x \rfloor, \varphi$ | Floor function; Golden ratio $\varphi = (1+\sqrt{5})/2 \approx 1.618$ |
| $T, R, P, S$ | Payoffs: Temptation, Reward, Punishment, Sucker's payoff |
| $\delta$ | Discount factor for future payoffs, $0 \le \delta < 1$ |
| $P(A\mid B)$ | Conditional probability of event $A$ given event $B$ |
| $\mathbb{E}[X], \mathrm{CE}$ | Expected value of random variable $X$; Certainty equivalent under utility |
| $\gcd(a,b)$ | Greatest common divisor of integers $a$ and $b$ |
| $x \equiv a \pmod m$ | Modular congruence: $x$ and $a$ have the same remainder modulo $m$ |
| $e$ | Base of the natural logarithm, $e \approx 2.71828$ |
Six Pre-Analysis Checkpoints
- Win Condition: Normal play (last mover wins) or misère play (last mover loses)?
- Action Constraints: How many heaps/stones per turn, and do prior moves restrict current limits?
- Information & Sequence: Simultaneous vs. sequential moves; is the horizon finite and known?
- Payoffs & Utility: Are survival, monetary payoffs, voting thresholds, or punishments quantified?
- Probability Framework: Are prior independence, uniform priors, and observation protocols verified?
- Search Goal: Finding any valid configuration, the shortest path, or maximizing success probability?
Algorithms & Implementation Complexity
| Problem | Method | Constraints & Complexity |
|---|---|---|
| Nim Evaluation | XOR all heap sizes, then find a heap reducible to zero the sum | $\mathcal{O}(N)$ time, $\mathcal{O}(1)$ space for $N$ heaps |
| Bash Game | Check $n \bmod (m+1)$ | $\mathcal{O}(1)$ time; requires consecutive $1\text{--}m$ removals |
| Wythoff Evaluation | Sort pair, compute difference $k$, check $a = \lfloor k\varphi \rfloor$ | $\mathcal{O}(1)$ time; guard against floating-point errors on large integers |
| Fibonacci Nim | Greedily find Zeckendorf minimal term | $\mathcal{O}(\log n)$ time; compare term with current move limit $r$ |
| General SG Games | Directed Acyclic Graph memoization with $\operatorname{mex}$ computation | Complexity scales with state space size and out-degree |
| Birthday Probability | Sequentially multiply distinct probability, then take complement | $\mathcal{O}(n)$ time for $n \le 365$; for $n \ge 366$, probability is 1 |
| 24 Game | Recursive pairs reduction with rational fractions | Exact fraction class prevents rounding errors |
| Chinese Remainder | Extended Euclidean algorithm to compute modular inverses | Moduli must be coprime; otherwise check pairwise compatibility |
| Josephus Survivor | 1D dynamic programming recurrence | $\mathcal{O}(n)$ time, $\mathcal{O}(1)$ space; closed form for $k=2$ |
| Binary Search | Maintain interval, bisecting candidates by half | $\lceil \log_2 N \rceil$ queries; requires noiseless answers |
| Secretary Cutoff | Accumulate harmonic sum backward, comparing cutoff $r$ | $\mathcal{O}(n)$ time; asymptotic threshold $n/e$ for large $n$ |
| Water Jug Shortest Path | Breadth-First Search on state space $(x,y)$ | At most $(a+1)(b+1)$ states; unweighted edge BFS guarantees shortest path |
References & Further Reading
- Ben Lynn: Nim and Grundy Values
- Yale CS: Nim and XOR Proofs
- Allen & Ponomarenko: Fibonacci Nim Winning Moves
- Gabriel Nivasch: Wythoff's Game
- IMSc: The Game of Chomp
- Yale Open Courses: Repeated Games and Credible Threats
- Berkeley: Monty Hall Host Rules & Conditional Probability
- Harvard: Probability, Bayes, Birthday & Monty Hall
- Blitzstein & Hwang: Conditional Probability and Simpson's Paradox
- MIT 6.042J: Number Theory, State Machines & Discrete Probability
- Ferguson: The Classical Secretary Problem and Optimal Stopping
- Algorithm Complexity Cheat Sheet · Python 3 Cheat Sheet