math

Mathematical Problem Solving

Specify the worlds, the legal actions and the claim before calculating.

Published 2026-08-30 · Updated 2026-10-14

On this page

Find a section

A quantitative puzzle often needs only elementary tools. The difficult step is choosing a model that preserves the question. An average, a probability and a worst-case guarantee are different claims, even when they concern the same process.

First describe possible worlds and legal actions. Then ask what an action changes, reveals or preserves. Counting and algebra become useful only after those meanings are clear.

What would count as an answer?

Match the wording to its proof obligation
Question	Needed evidence
Is it possible?	One valid construction
Must it happen?	A proof covering every allowed case
With what probability?	A specified random experiment and event
On average?	An expectation under that model
Can we guarantee it?	A strategy against the worst allowed case
What is the minimum?	An impossibility bound and a matching construction

A randomized strategy can have a small mean cost and an unbounded worst case. A strategy using k steps proves an upper bound, not optimality. An information limit proves a lower bound, not an attainable procedure.

Write down replacement policy, independence, available observations, legal queries and what the answer must identify. A counterfeit coin's identity and its heavy/light status may be different requested outputs.

Define the elementary outcomes

Counting requires a definition of distinct outcomes. Choosing three people for a committee ignores order. Choosing a chair, secretary and treasurer preserves order. Drawing with replacement permits repeated choices; drawing without replacement does not.

Counts for n distinct options and 0≤k≤n where needed
Construction	Count
Choose k without order	$\binom nk=\frac{n!}{k!(n-k)!}$
Choose and order k without repetition	$\frac{n!}{(n-k)!}$
Order all n	n!
Length-k sequence with repetition	nᵏ

The product rule multiplies stage counts when every preceding construction has the stated number of continuations. If the next count depends on the first choice, sum the counts of those branches instead.

P(A)=\frac{|A|}{|\Omega|}

A is a subset of a finite nonempty sample space Ω. Every elementary outcome must have the same probability; counting category labels does not give them equal weights.

Two fair-coin tosses have four equally likely sequences: HH, HT, TH, TT. Grouping them into “two heads”, “one head” and “zero heads” does not make those three categories equally likely. Their probabilities are 1/4, 1/2 and 1/4.

Conditioning changes the relevant worlds

\begin{aligned}P(A^{\mathrm c})&=1-P(A)\\P(A\cup B)&=P(A)+P(B)-P(A\cap B)\\P(A\cap B)&=P(A)P(B\mid A)\end{aligned}

The complement is relative to the sample space. The last expression requires P(A) > 0 to define P(B | A). None of these rules assumes independence.

For ten independent fair-die rolls, at least one six is easier through its complement: $1-\left(\frac56\right)^{10}$ . Multiplication is valid because the rolls are independent. Events occurring at different times are not automatically independent.

For $P(B)>0$ , $P(A\mid B)=\frac{P(A\cap B)}{P(B)}$ . Keep only worlds compatible with B and renormalize their weights. If a message was produced by a selection procedure, include that procedure; the message's wording alone may not specify its likelihood.

\begin{aligned}P(A)&=\sum_i P(A\mid B_i)P(B_i)\\P(B_i\mid A)&=\frac{P(A\mid B_i)P(B_i)}{P(A)}\end{aligned}

The finite or countable cases Bi are disjoint and exhaustive. Use positive-probability cases for the conditional terms; zero-probability cases contribute zero. Bayes' formula requires P(A) > 0.

A table of hidden types, prior probabilities and observation likelihoods helps with tests, boxes, doors and family-information puzzles. Probability and Distributions → gives the full conditional/joint framework.

For independent events with P(A) > 0, P(B | A) equals P(B), so the intersection probability is P(A)P(B). For mutually exclusive events, the union rule reduces to P(A)+P(B).

Mutually exclusive events have zero overlap. Independent events have product overlap. Positive-probability mutually exclusive events therefore cannot also be independent.

Count events with indicators

For a discrete quantity X with a finite expectation, $\mathbb E[X]=\sum_x xP(X=x)$ . Instead of finding its complete distribution, sometimes write X as a sum of indicators. Indicator Iᵢ is 1 when event i occurs and 0 otherwise, so $\mathbb E[I_i]=P(\text{event }i)$ .

\mathbb E\!\left[\sum_{i=1}^n I_i\right]=\sum_{i=1}^n\mathbb E[I_i]=\sum_{i=1}^nP(I_i=1)

For a finite number n of indicator variables. Independence is not required. When n = 0, both sums are zero.

In a uniformly random permutation of n≥1 objects, let Iᵢ indicate that object i stays in its original position. Each has probability 1/n, so the expected number of fixed points is $n\cdot\frac1n=1$ .

Linearity also applies to any finite sum of random variables with finite absolute expectations: the expectation of the sum equals the sum of their expectations. Indicators are a useful special case, not a separate independence assumption.

The events are dependent. For two objects, either both remain or neither remains. Dependence does not invalidate linearity. The empty permutation has zero fixed points; the $\frac1n$ argument does not cover n=0.

An expectation is not a typical outcome or a guarantee. If signed quantities have divergent positive and negative parts, an expression such as ∞−∞ does not define an expectation. Infinite sums require additional convergence or nonnegativity conditions.

Keep only the useful past

For a waiting-time problem, store enough history to predict the next transition, but no irrelevant history. To wait for HH in independent fair tosses, the useful suffix is either empty or H. Once HH appears, the process has finished.

\begin{aligned}E_0&=1+\frac12E_1+\frac12E_0\\E_1&=1+\frac12\,0+\frac12E_0\\E_0&=6,\qquad E_1=4\end{aligned}

Independent fair tosses, stopping at the first consecutive HH. Each next toss costs one. E0 and E1 are finite expected remaining tosses from no useful suffix and suffix H; the finished state's expectation is zero.

From the empty state, H leaves suffix H and T leaves no useful suffix. From H, another H finishes, while T resets. The reset term is why “two heads means four tosses on average” is not the correct calculation for consecutive heads.

The equations have a finite solution here. One independent two-toss block succeeds with probability 1/4, giving a finite upper bound of eight tosses by checking only disjoint blocks. Allowing overlapping successes can only finish earlier. This supports using finite first-step expectations.

For a nonnegative integer completion time T and nonnegative integer cutoff m, $\mathbb E[\min(T,m)]=\sum_{j=0}^{m-1}P(T>j)$ . Each included toss contributes one exactly when completion has not yet occurred. The finite sum measures truncated waiting, not a guaranteed completion by m.

A state must be sufficient for the actual model. A biased or dependent coin changes the transition probabilities, and a longer target can require more suffix states. This is stochastic state reasoning, related to Dynamic Programming →, not enumeration of every past sequence.

Probability mass moves through suffix states

Exact distribution over independent fair-coin sequences, not one random animation. Finished mass stays finished as toss count increases.

Step 6 / 24

No useful suffixT → hereH → suffix H

Suffix HT → no suffixH → finished

Finished HHStay finished

No suffix

20.31%

Suffix H

12.50%

Finished

67.19%

After 6 tosses, P(T > 6) = 32.81%. Here T is the first completion time, not an individual coin outcome.

E[min(T,6)] = 4.281250 tosses. This finite partial tail sum approaches 6; it is not the full expectation at a finite step.

Exact small input, not a speed benchmark. Step order follows the algorithm; playback is optional. Rows show probability mass. Every state is labeled; bar width is measured on the same probability scale.

A rate is not a probability

A homogeneous Poisson process has stationary independent increments and a constant rate λ>0. In a short interval Δ, one arrival has probability λΔ+o(Δ), and multiple arrivals have probability o(Δ). A constant long-run average alone does not establish these properties.

\begin{aligned}\mu&=\lambda t,\qquad N(t)\sim\operatorname{Poisson}(\mu)\\P(N(t)=j)&=\frac{e^{-\mu}\mu^j}{j!}\\\mathbb E[N(t)]&=\operatorname{Var}(N(t))=\mu\end{aligned}

A homogeneous Poisson process has rate λ > 0 and interval t ≥ 0 in matching time units. The count j is a nonnegative integer. At μ = 0 the count is zero almost surely; use the PMF convention 0^0 = 1 at j = 0.

Six calls per hour during ten minutes gives $\mu=6\cdot\frac{10}{60}=1$ . Therefore $P(\text{at least one call})=1-e^{-1}$ , about 63.21%. The number six is a rate, not a probability of a call.

\begin{aligned}P(T_1>t)&=P(N(t)=0)=e^{-\lambda t}\\f_{T_1}(t)&=\lambda e^{-\lambda t},\qquad t\ge0\\\mathbb E[T_1]&=\frac1\lambda,\qquad\operatorname{Var}(T_1)=\frac1{\lambda^2}\end{aligned}

T1 is the wait from the start until the first arrival, with positive rate λ. Its density is zero for t < 0. Mean has time units; variance has squared-time units. The rate-zero lab boundary is not this exponential distribution.

The wait Tₖ to the kth arrival is Gamma with shape k and rate λ, also called Erlang for integer k. $\mathbb E[T_k]=\frac{k}{\lambda}$ and $P(T_k\le t)=P(N(t)\ge k)$ . Counts and waiting times describe the same arrivals from different directions.

Exponential memorylessness gives $P(T_1>s+t\mid T_1>s)=P(T_1>t)$ , for nonnegative s and t. Waiting without an arrival does not make one due. This conclusion is not appropriate for scheduled buses, aging hardware or history-dependent rates. Poisson definition and waiting-time derivation ↗

The mean wait is not the median, which is $\frac{\ln2}{\lambda}$ , or a deadline. Bursts, resource limits and self-exciting arrivals require a different model. The lab includes zero rate as a no-arrival boundary case, not an exponential distribution with rate zero.

One count event, one waiting-time event

Keep the homogeneous independent-increment assumptions fixed. Change rate, interval length and the arrival number.

Rate, arrivals/hour 6Interval, minutes 10Arrival number

μ = 6 arrivals/hour × 10/60 hour = 1.000 arrivals.

36.79%

18.39%

6.13%

1.53%

0.31%

0.05%

0.01%

<0.01%

P(N(t) ≥ 1) = P(T₁ ≤ t) = 63.21%. Both expressions describe the same event.

Expected time to arrival 1: 10.00 minutes. That mean is not a deadline or a guaranteed waiting time.

Bars use a fixed 0–100% scale. The 9+ row groups the remaining count tail, not exactly nine arrivals. This is a model calculation, not sampled traffic.

Combine, label and condition arrival streams

Independent Poisson streams with rates λᵢ combine into a Poisson stream with rate Σᵢλᵢ. For two positive-rate streams, the next arrival's type is 1 with probability λ₁/(λ₁+λ₂), and the waiting time is exponential with their combined rate.

Independent labeling of each event as retained with probability p gives retained rate pλ and discarded rate (1−p)λ. The two labeled streams are independent before conditioning on a total. Keeping every second event is not independent labeling and does not have this thinning guarantee. Merging and independent thinning ↗

Given N(t)=n for t>0, the unordered event locations have the distribution of n independent uniform points in the interval. The ordered arrival times are their order statistics, not mutually independent ordered values.

\begin{aligned}N(s)\mid N(t)=n&\sim\operatorname{Binomial}\!\left(n,\frac{s}{t}\right)\\P(N(s)=j\mid N(t)=n)&=\binom{n}{j}\left(\frac{s}{t}\right)^j\left(1-\frac{s}{t}\right)^{n-j}\end{aligned}

For rate λ > 0, t > 0, 0 ≤ s ≤ t, integer n ≥ 0 and 0 ≤ j ≤ n. Conditioning fixes the total. The endpoint cases are degenerate binomials; use 0^0 = 1 where required. Probability is zero outside the integer j range.

For four arrivals in an hour, the number in its first quarter has mean $4\cdot\frac14=1$ . Its complement count is four minus that number. The two counts are no longer independent once their total is fixed. Conditional arrival locations, Lecture 4 ↗

A lower bound is not a strategy

b^k\ge N\quad\Longrightarrow\quad k\ge\left\lceil\frac{\log N}{\log b}\right\rceil

N ≥ 1 distinct requested answers, integer branching bound b ≥ 2 and integer worst-case depth k ≥ 0. This leaf-capacity condition is necessary, not a construction of legal queries.

A depth-k adaptive decision tree has at most b^k leaves. If every hidden world must be identified separately, there must be at least N leaves. Yes/no questions have at most two branches; a balance scale has at most three.

Eight hidden cases need at least 3 binary answers. Arbitrary subset questions can attain this bound by successively halving the cases. A scale cannot necessarily realize every desired partition: legal weighings restrict which cases produce each outcome.

If the answer must identify both one of n suspect coins and its heavy/light status, there are 2n worlds. If only a coarser answer is required, worlds that can safely share that answer need not occupy separate leaves. State the identification objective before counting.

Impossible branches, unequal splits and legal-query restrictions can make the bound unattainable. Adaptive strategies choose the next query from previous outcomes; non-adaptive strategies fix every query beforehand. Prove both the lower bound and a legal matching construction before claiming an optimum.

Information Theory → connects probabilities to average code lengths. A worst-case leaf-count bound is not the same as an expected-length entropy bound.

Delay the event as long as possible

The pigeonhole principle guarantees a repeated box when more objects than boxes are assigned. More generally, N objects in n>0 boxes force at least one box to contain ⌈N/n⌉ objects.

With twelve birth months, thirteen people force a shared month. Twelve people do not: put one in each month. This arrangement supplies the matching lower-bound example, not merely an intuitive argument.

For a guarantee of at least an integer r≥1 objects in one of n boxes, the delaying arrangement puts r−1 in every box. Thus n(r−1)+1 objects suffice and n(r−1) need not suffice, assuming those assignments are all allowed. Unequal capacity or prohibited assignments change the argument.

No probability model is needed. A birthday probability question with random birthdays is a different calculation; worst-case assignment is not replaced by an average distribution.

A legal move cannot repair every difference

An invariant is a property preserved by every legal move. Candidate properties include parity, a sum or difference, a residue modulo m, permutation parity or a connectivity feature. Prove preservation for the actual move; do not assume a component count stays fixed when moves can connect components.

Remove opposite corners of an 8×8 chessboard. Both have the same color, leaving 30 of that color and 32 of the other. Every domino covering adjacent squares uses exactly one of each color. Therefore 31 dominoes cannot cover the remaining board.

××

Two opposite corners have the same color. Remaining: 30 blue, 32 burgundy. Every domino needs one of each.

Equivalently, every placed domino changes the uncovered color counts by (−1,−1), preserving their difference of two. A fully covered board would have difference zero, so it is unreachable.

Equal color counts would only remove this obstruction. They would not prove a tiling exists: disconnected regions or other shape restrictions can still prevent one. An invariant usually proves impossibility before it provides a construction.

Strict progress needs a well-founded domain

A monovariant changes strictly in one direction on each move. To prove termination, the possible values must forbid an infinite chain in that direction. A decreasing nonnegative integer works because each move lowers it by at least one.

\begin{aligned}M_{t+1}&<M_t,\qquad M_t\in\mathbb Z_{\ge0}\\M_L&\le M_0-L\\0\le L&\le M_0\end{aligned}

Every legal step strictly decreases a nonnegative integer. After L steps the value has fallen by at least L, so at most M0 such steps are possible. A lower-bounded real-valued decrease alone does not give this result.

Strict decrease and a real lower bound alone are insufficient. $M_t=\frac1{t+1}$ decreases forever while staying above zero. A real-valued potential needs an additional argument, such as a uniform decrease of at least ε>0 or a finite set of allowed values.

Separate termination from efficiency. A potential can prove that a process ends without giving a useful bound in the input size. Also verify strict progress for every legal step, including ties and no-op moves.

Preserve the experiment, not just the picture

A transformation can equate case probabilities only when it preserves the random experiment and exchanges those cases. Relabeling a fair die's faces preserves its procedure. A weighted die can have the same shape without preserving the probability law.

Rotate, reflect, permute or relabel to simplify cases. Check exceptional configurations: some have fewer distinct images under the transformation. For two fair tosses, swapping toss positions exchanges HT and TH but leaves HH unchanged. Counting symmetry classes as equally likely would reproduce the wrong three-category model.

A bijection proves equal counts when it pairs valid objects. Probability equality additionally requires preserving their weights. Symmetry is a proof tool, not a substitute for defining the experiment.

Use total time instead of every trip

Two objects moving directly toward each other at constant speeds v₁ and v₂ close a separation D at rate v₁+v₂. The collision time is $t=\frac{D}{v_1+v_2}$ , for positive total closing speed.

A fly traveling continuously at speed v_f until the collision covers v_ft. Summing every back-and-forth trip adds complexity without changing the total available flight time. This uses instantaneous turning and no pauses as idealized assumptions.

\begin{aligned}r_i&=\frac1{T_i},\qquad i=1,\ldots,n\\r_{\mathrm{total}}&=\sum_{i=1}^n r_i\\T_{\mathrm{together}}&=\frac1{r_{\mathrm{total}}}\end{aligned}

For n ≥ 1 workers, each completing one unit in positive time Ti at a constant rate. Work is perfectly divisible, rates add without interference and every worker operates throughout. Rate units are work/time; completion time is time per one unit.

Machines taking two and three hours per unit have combined rate $\frac12+\frac13=\frac56$ units/hour. They complete one unit in $\frac65$ hours, not the average of their completion times.

Sequential dependencies, indivisible tasks, interference and varying speed can invalidate rate addition. Track units: distance=speed×time and work=rate×time. Matching units is necessary but does not by itself establish the physical model.

Translate statements into constraints

Name unknowns before manipulating numbers. If a father and child have current ages x and y, their ages d years ago are x−d and y−d. Shift both ages by the same duration; their difference stays x−y.

Choose a representation that makes actions explicit: a table for hidden cases, a graph for routes, a state tuple for containers, a decision tree for adaptive observations, equations for conserved quantities.

When the goal is highly constrained, work backward through possible predecessor states. Every reversed step must correspond to a legal forward move. Directed transitions are not automatically reversible; a backward search may need incoming edges rather than the ordinary forward rule.

Choosing Algorithms → connects representation, requested output and maintained state. The representation should simplify the legal operations without losing information needed by the question.

The same observation can fit different models

Suppose the probability of seeing at least one truck in one hour is 0.99. That number alone does not determine the half-hour probability.

If the two half-hours have identical independent no-arrival probabilities q, then $q^2=0.01$ . Therefore q=0.1 and the half-hour arrival probability is 0.9. A homogeneous Poisson model supplies these assumptions, but the single observation does not prove that model.

Distinct models with the same one-hour probability
Model	One-hour arrival probability	Half-hour arrival probability
Independent identical halves	0.99	0.90 in either half
With probability 0.99, a truck in each half; otherwise none	0.99	0.99 in either half
With probability 0.99, only the first half has a truck	0.99	0.99 first half; 0 second half

The second model has identical halves but dependence. The third loses stationarity. These constructions show exactly which additional assumptions the square-root answer uses.

Recognizing underdetermination is a valid result. State the extra assumption needed for a unique answer instead of silently solving a stronger question.

From a conjecture to a proof

Use small cases n=1,2,3,4 to find a candidate pattern or counterexample. Then seek induction, a recurrence, an invariant, a bijection or a counting argument. Small successes suggest a theorem; they do not prove it.

Check empty sets, probabilities zero/one, equal values, attained boundaries and singleton states. For a minimum, pair an impossibility argument with a matching legal strategy. For an expectation, verify finiteness or state that it diverges.

Write the objective and hidden states.
Specify the random model and legal observations.
List assumptions: independence, replacement, constant rates, information and movement rules.
Choose a representation and a preserved or changing quantity.
Try small cases or legal backward steps.
Derive the result, then check probability bounds, units and edge cases.
Separate a bound, a construction and an optimality proof.

For revisiting these tools, a useful order is conditioning/counting, then indicators and state equations, then arrivals, guarantees, information bounds and invariants. Rates and algebra are often simpler than a long simulation.

Common failure modes are multiplying without independence, counting without equal weights, confusing means with guarantees, claiming a lower bound is attainable, using visual symmetry as probability evidence and assuming bounded real progress must terminate.

References

Poisson counts and arrival times ↗ · Independent stream operations ↗ · Conditional arrival locations ↗

Backtracking → makes legal branch exploration and restoration explicit. Bits, Numbers, and Geometry → applies arithmetic and coordinate invariants to algorithms.

Interactive probabilities are calculated from explicitly stated idealized models. They are not measured arrival data or claims about a particular physical system.