iv. Contest Mathematics

The math that contest problems assume without naming it. Each fact is short; the skill is noticing which one applies.

Floor, ceiling and division

long long floorDiv(long long a, long long b) { return a / b - ((a % b != 0) && ((a < 0) != (b < 0))); }
long long ceilDiv(long long a, long long b) { return a / b + ((a % b != 0) && ((a < 0) == (b < 0))); }
long long modFloor(long long a, long long m) { return ((a % m) + m) % m; }      // m > 0, result in [0, m)

Identity	Condition
$\lceil a/b\rceil =\lfloor (a+b-1)/b\rfloor$	$a\ge 0$, $b>0$
$\lfloor \lfloor n/a\rfloor /b\rfloor =\lfloor n/(ab)\rfloor$	$n\ge 0$, $a,b>0$
$\lfloor x\rfloor +\lfloor y\rfloor \le \lfloor x+y\rfloor \le \lfloor x\rfloor +\lfloor y\rfloor +1$	real $x,y$
$n=b\lfloor n/b\rfloor +(n\mathrm{mod}b)$	$b>0$, with $0\le n\mathrm{mod}b<b$
$\lfloor n/i\rfloor$ takes at most $2\sqrt{n}$ distinct values	see Floor Sums
${\sum }_{i=1}^n\lfloor n/i\rfloor ={\sum }_{k=1}^{n}d(k)\approx n\ln n$	divisor counting

Proof: the floor identities

Ceiling. Write $a=qb+r$ with $0\le r<b$. If $r=0$, both sides equal $q$. Otherwise $\lceil a/b\rceil =q+1$ and $a+b-1=(q+1)b+(r-1)$ with $0\le r-1<b$, so the floor is $q+1$. Nested floor. Let $q=\lfloor n/a\rfloor$, so $qa\le n<(q+1)a$. Let $k=\lfloor q/b\rfloor$, so $kb\le q\le kb+b-1$. Then $kab\le qa\le n$ and $n<(q+1)a\le (kb+b)a=(k+1)ab$, so $\lfloor n/(ab)\rfloor =k$. Sum of floors. With $x=\lfloor x\rfloor +\{x\}$, $\lfloor x+y\rfloor =\lfloor x\rfloor +\lfloor y\rfloor +\lfloor \{x\}+\{y\}\rfloor$ and $0\le \{x\}+\{y\}<2$. The helpers were tested against floating-point division for all $|a|\le 60$, $|b|\le 13$.

Inequalities

Inequality	Statement	Equality
AM–GM	$\frac{a_1+\cdots +a_n}{n}\ge \sqrt[n]{a_1\cdots a_n}$ for $a_i\ge 0$	all equal
Cauchy–Schwarz	$(\sum a_i{b}_i{)}^2\le \sum a_i^2\sum b_i^2$	proportional vectors
rearrangement	$\sum a_i{b}_{\sigma (i)}$ is maximal when both are sorted the same way	—
Jensen	$f(\text{mean})\le \text{mean}(f)$ for convex $f$	all equal or $f$ linear
triangle	$	a + b
Bernoulli	$(1+x{)}^n\ge 1+nx$ for $x\ge -1$, $n\ge 1$	$x=0$ or $n=1$
harmonic bound	$\ln (n+1)\le H_n\le 1+\ln n$	—

Proof: AM–GM and Cauchy–Schwarz

Cauchy–Schwarz. The quadratic $\sum (a_{i}t-b_i{)}^2=t^2\sum a_i^2-2t\sum a_i{b}_i+\sum b_i^2$ is non-negative for all real $t$, so its discriminant is $\le 0$: $4(\sum a_i{b}_i{)}^2-4\sum a_i^2\sum b_i^2\le 0$. AM–GM. $\ln$ is concave, so by Jensen $\ln \frac{\sum a_i}{n}\ge \frac{\sum \ln a_i}{n}$ for positive $a_i$ (zeros make the right side $0$); exponentiate. Jensen for two points is the definition of convexity, and it extends to $n$ points by induction, writing the mean of $n$ points as a weighted mean of one point and the mean of the other $n-1$.

Sums and sequences

Sum	Closed form
${\sum }_{i=1}^{n}i$, $\sum i^2$, $\sum i^3$	$\frac{n(n+1)}{2}$, $\frac{n(n+1)(2n+1)}{6}$, ${\left(\frac{n(n+1)}{2}\right)}^2$
geometric ${\sum }_{i=0}^{n-1}{r}^i$	$\frac{r^n-1}{r-1}$ ($r\ne 1$); modulo $p$ use an inverse or a doubling recursion
${\sum }_{i\ge 1}i{x}^i$	$\frac{x}{(1-x{)}^2}$ for $
telescoping $\sum (f(i+1)-f(i))$	$f(n+1)-f(1)$; e.g. $\sum \frac{1}{i(i+1)}=1-\frac{1}{n+1}$
arithmetic progression mod $m$	period $m/\gcd (d,m)$
linear recurrence	characteristic roots, matrix power (Matrix Power)

Proof: power sums and the geometric series

Each formula is checked at $n=1$ and by induction: adding the next term to the right side gives the formula at $n+1$ (for $\sum i^3$: ${\left(\frac{n(n+1)}{2}\right)}^2+(n+1{)}^3=\frac{(n+1{)}^2(n^2+4n+4)}{4}={\left(\frac{(n+1)(n+2)}{2}\right)}^2$). For the geometric series, $(r-1){\sum }_{i<n}{r}^i=r^n-1$ by telescoping.

Modular and counting observations

Observation	Use
squares are $0,1(\mathrm{mod}4)$ and $0,1,4(\mathrm{mod}8)$ (odd squares $\equiv 1(\mathrm{mod}8)$)	impossibility of sums of squares
$a\equiv$ digit sum $(\mathrm{mod}9)$	digit problems
$n^5\equiv n(\mathrm{mod}30)$; $p\mid \left(\genfrac{}{}{0ex}{}{p}{k}\right)$ for $0<k<p$	Fermat-style simplifications
pigeonhole on prefix sums mod $n$	some subarray sum divisible by $n$
double counting	count pairs (element, set) both ways
stars and bars $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$	distribute identical items
bijections	count an easier set of the same size

More: Modular Arithmetic, Counting Fundamentals, Invariants.