Classic Constructions

A catalogue of constructions that recur across constructive problems.

Permutations

Goal	Construction
$|p_i-i|$ all distinct	$1,n,2,n-1,3,\dots$ (alternate the ends)
No fixed points (derangement)	shift by 1: $p_i=i\mathrm{mod}n+1$
Adjacent elements differ by $\ge k$	odd positions first, then even
$p_i+i$ all distinct mod $n$	$p_i=2i\mathrm{mod}n$ (needs $n$ odd)
Maximum $\sum |p_i-i|$	reverse the two halves
Every prefix sum distinct mod $n$	$1,-1,2,-2,\dots$ pattern
Exactly $k$ inversions	sort, then reverse a suitable prefix and adjust
$k$ distinct adjacent differences	$1,k+1,2,k,3,\dots$

Alternating the extremes ($1,n,2,n-1,\dots$) is the single most reusable permutation construction — it maximises adjacent differences and separates values that must not be close.

Grids and matrices

Goal	Construction
Latin square	$a_{ij}=(i+j)\mathrm{mod}n$
Two orthogonal Latin squares	$(i+j)\mathrm{mod}n$ and $(i+2j)\mathrm{mod}n$, for odd $n$
Magic square, odd $n$	the Siamese method (move up-right, drop down on collision)
All row and column sums equal	a circulant matrix
No two adjacent equal	chessboard colouring
Every $2\times 2$ has all four values	tile with a fixed $2\times 2$ block
Fill so all rows/columns are distinct	$(i+j)\mathrm{mod}n$ again

Sequences

Goal	Construction
All pairwise sums distinct (Sidon set)	powers of 2, or $\{i^2\}$-based
All subset sums distinct	$1,2,4,8,\dots$
Prefix sums all distinct	strictly positive values
No three in arithmetic progression	base-3 digits avoiding 2 (the greedy/Stanley sequence)
Sum $=S$ with $n$ distinct positives	$1,2,\dots ,n-1$, then $S-\left(\genfrac{}{}{0ex}{}{n}{2}\right)$
Maximum gcd of a partition	multiples of the intended gcd
All XOR-distinct	a linear basis

Graphs

Goal	Construction
Exactly $k$ edges, connected	a path plus $k-(n-1)$ extra edges
$d$-regular graph	a circulant: connect $i$ to $i\pm 1,\dots ,i\pm d/2$
Bipartite with given degrees	Gale-Ryser condition, then greedy
Given degree sequence	Erdős-Gallai condition, then Havel-Hakimi
Diameter exactly $k$	a path of length $k$, everything else attached to the middle
Exactly $c$ components	a clique of the right size plus isolated vertices
Tree with given degrees	Prüfer code with the right multiplicities
Maximum edges, no triangle	complete bipartite $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ (Turán)
Maximum edges, no $K_{r+1}$	the Turán graph — a balanced $r$-partite complete graph

Havel-Hakimi for realising a degree sequence: repeatedly take the highest-degree vertex, connect it to the next $d$ highest, decrement, and recurse.

Number-theoretic

Goal	Construction
$n$ numbers, pairwise coprime	distinct primes, or $2^{2^i}+1$ (Fermat numbers)
$n$ numbers with gcd $g$ and lcm $L$	scale a construction by $g$
Sum $=S$, product $=P$	solve the quadratic for $n=2$; use 1s to pad
$a+b=a\oplus b$	disjoint bit sets ($a\&b=0$)
$a\oplus b\oplus c=0$	$c=a\oplus b$
$n$ numbers with all subset sums distinct	powers of 2
Sum of $k$ distinct squares	greedy from the largest
Prescribed remainders	CRT

$a+b=a\oplus b⟺a\&b=0$ is worth memorising — it appears constantly, and it is the statement that XOR is addition without carries.

The XOR toolbox

Fact	Use
$1\oplus 2\oplus \cdots \oplus n$ has period 4 in $n$	prefix XOR in $O(1)$
$4k\oplus (4k+1)\oplus (4k+2)\oplus (4k+3)=0$	pair up ranges to cancel
$x\oplus x=0$	duplicate to cancel
Any $n$ values can be made to XOR to 0 by adding one element	that element is their XOR
Consecutive pairs $2k,2k+1$ XOR to 1	build a target XOR from pairs

The general recipes

1. Alternate. High-low interleaving separates values.
2. Pair up. Match $i$ with $n+1-i$ so pairs have a constant sum.
3. Recurse. Solve $n/2$ or $n-1$, then extend.
4. Handle small $n$ separately. Most constructions have 2-3 exceptional cases.
5. Use powers of two. They make sums and XORs independent.
6. Use a shift or rotation. $a_i=(ci+d)\mathrm{mod}n$ is a rich family.
7. Colour or partition. Split by parity, residue, or a colouring.
8. Be greedy from an extreme. Largest first, or most constrained first.

Always verify

Write the construction, then check it with a brute force on $n\le 8$ — including the exceptional cases. Constructions are easy to get almost right, and “almost” fails on exactly one test.

See also: Small Cases · General · Invariants