Paper 4, Section II, E

Numbers and Sets | Part IA, 2014

(i) State and prove the Inclusion-Exclusion Principle.

(ii) Let n>1n>1 be an integer. Denote by Z/nZ\mathbb{Z} / n \mathbb{Z} the integers modulo nn. Let XX be the set of all functions f:Z/nZZ/nZf: \mathbb{Z} / n \mathbb{Z} \rightarrow \mathbb{Z} / n \mathbb{Z} such that for every jZ/nZ,f(j)f(j1)≢jj \in \mathbb{Z} / n \mathbb{Z}, f(j)-f(j-1) \not \equiv j (modn)(\bmod n). Show that

X={(n1)n+1n if n is odd (n1)n1 if n is even |X|= \begin{cases}(n-1)^{n}+1-n & \text { if } n \text { is odd } \\ (n-1)^{n}-1 & \text { if } n \text { is even }\end{cases}

Typos? Please submit corrections to this page on GitHub.