MathDB
Putnam 2013 B5

Source:

December 9, 2013
Putnamfunctioninductionprobabilitylinear algebramatrixalgebra

Problem Statement

Let X={1,2,…,n},X=\{1,2,\dots,n\}, and let k∈X.k\in X. Show that there are exactly k⋅nn−1k\cdot n^{n-1} functions f:X→Xf:X\to X such that for every x∈Xx\in X there is a j≥0j\ge 0 such that f(j)(x)≤k.f^{(j)}(x)\le k.
[Here f(j)f^{(j)} denotes the jjth iterate of f,f, so that f(0)(x)=xf^{(0)}(x)=x and f(j+1)(x)=f(f(j)(x)).f^{(j+1)}(x)=f\left(f^{(j)}(x)\right).]
Back to ProblemsView on AoPS