Section 4.4

Parity and Divisibility of Random Sums

Whether a random sum is even, odd or divisible by k: uniform residues of dice sums, the (1-2p)^n parity identity, parity constraints in grids.

Toolkit

Many “mod-k” sum problems reduce either to a uniformity argument (one term’s residue is equidistributed and independent of the rest, forcing the overall sum’s residue to be uniform) or to a generating-function / transform trick for parity.

If some summand $X_i$ is independent of the rest and uniform on $\{0,\dots,k-1\}$ under addition mod $k$ , then the total sum is uniform mod $k$ , so $\mathbb{P}(\text{sum}\equiv r)=1/k$ for every $r$ .
For independent terms, use the parity transform $\mathbb{E}[(-1)^S]=\prod_i\mathbb{E}[(-1)^{X_i}]$ ; for i.i.d. Bernoulli $(q)$ summands this gives

\mathbb{E}[(-1)^S]=(1-2q)^n,\qquad \mathbb{P}(S\text{ odd})=\frac{1-(1-2q)^n}{2}.

Divisibility by $2^m$ or $10^m$ depends only on the last $m$ base-digits; enumerate residues directly.
Parity of a sum/product of integers depends only on the parities (and, for primes, on whether $2$ is among the chosen numbers) of the individual terms; condition on the first/last step to set up a recursion $p = f(p)$ for self-consistent parity probabilities.

Problems