Small Cases and Pattern Finding

The most reliable technique for constructive and ad-hoc problems: compute the answer for tiny inputs by brute force, then look at it.

The workflow

1. Write a brute force that solves $n=1,2,3,\dots ,8$ exhaustively.
2. Print the answers, and the solutions themselves, not just the values.
3. Look for a pattern: a formula, a period, a construction, or a rule about which cases are possible.
4. Conjecture.
5. Verify the conjecture against the brute force on a wider range.
6. Prove it, or trust it if the verification is convincing.

Step 5 is the one people skip, and it is where wrong answers come from.

What to look for

Observation	Likely conclusion
Answers are $1,2,4,8,16$	$2^n$
$1,1,2,3,5,8$	Fibonacci
$1,1,2,5,14,42$	Catalan
$1,2,6,24,120$	$n!$
Possible for even $n$ only	a parity invariant
Possible except for $n=2,3$	small exceptions plus a general construction
The answer is a polynomial in $n$	interpolate it
Grundy values repeat with period $p$	a periodic Grundy sequence
The construction extends the $n-1$ case	induction; write the inductive step
Answers match a known sequence	search OEIS

OEIS is a legitimate contest technique

Compute 8-12 terms and search oeis.org. It very often names the sequence, gives a closed form or recurrence, and links a proof. This is fast, allowed, and frequently the intended path.

Writing a useful brute force

// enumerate every candidate for small n and record which work
for (int n = 1; n <= 8; n++) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    bool found = false;
    do {
        if (valid(p)) { print(n, p); found = true; break; }   // print the SOLUTION
    } while (next_permutation(p.begin(), p.end()));
    if (!found) printf("n=%d: impossible\n", n);
}

Print the actual solutions, not just yes/no. The construction’s shape — alternating, symmetric, built from the previous case — is usually visible immediately and is exactly what you need to generalise.

Common construction patterns

Pattern	Shape
Alternate	odd positions then even, or high/low interleaved
Pair up	$i$ with $n+1-i$, so pairs sum to $n+1$
Recursive halves	solve $n/2$, combine (as in Hanoi)
Induction by one	extend the $n-1$ solution
Handle small cases separately	a general rule plus 2-3 exceptions
Rotate/shift	a cyclic construction, $a_i=(i\cdot k)\mathrm{mod}n$
Greedy from an extreme	largest first, or most constrained first
Symmetric	mirror the first half
Binary structure	use the bits of $i$

Recognising the shape from small cases is the whole skill; the proof usually follows once you can see it.

Stress testing the conjecture

for i in $(seq 1 10000); do
  ./gen $i > in.txt
  ./brute < in.txt > out1.txt
  ./fast  < in.txt > out2.txt
  if ! diff -q out1.txt out2.txt > /dev/null; then echo "FAIL on seed $i"; break; fi
done

Run this before submitting any construction you guessed. Ten thousand random small tests take a few seconds and catch nearly every wrong conjecture. See Debugging and Stress Testing.

When there is no pattern

• Widen the range — the pattern may start at $n=6$.
• Change what you print — the count, the lexicographically smallest solution, the number of solutions, the solution’s structure.
• Look mod $k$ for small $k$.
• Look at differences or ratios between consecutive answers.
• Consider that the answer may depend on more than $n$ (parity, divisibility, the input’s structure).
• The problem may genuinely need an algorithm rather than a formula — in which case small cases still help you check it.

Why this works

Constructive problems are usually built from a pattern the setter found. Small cases reveal that pattern faster than any amount of thinking about the general case, and they simultaneously give you a test oracle.

See also: General · Stress Testing · Classic Constructions