On a Counting Problem, From HCMUS TST

On a Counting Problem

From a Student Olympiad Team Selection Exam

Long Do
January 10, 2026

View Full Post

Problem

Let \(S=\{1,2,\ldots,100\}\). Let \(\mathcal F\) be the set of functions \(f:S\to S\) satisfying

$$ f(k)\le f(k+1)\le f(k)+1,\qquad k=1,2,\ldots,99. $$

1. Find \(|\mathcal F|\).
2. For each \(f\in\mathcal F\), let \(n(f)\) be the number of solutions of \(f(x)=x\). Compute $$ \sum_{f\in\mathcal F} n(f). $$

Solution

We first solve the problem using the classical “stars and bars” (Euler candy distribution) method.

Suppose the distinct values taken by \(f(x)\) are

$$ f_1 Because \(f(k)\le f(k+1)\le f(k)+1\), we must have $$ f_{i+1}=f_i+1. $$

Hence the values are

$$ f_1,f_1+1,\ldots,f_1+m-1. $$

Let \(k_i\) be the number of indices \(x\) such that \(f(x)=f_i\). Then

$$ k_1+k_2+\cdots+k_m=100, \qquad k_i\ge1. $$

Thus the number of such choices equals

$$ \binom{99}{m-1}. $$

For each \(m\), the first value \(f_1\) can be chosen in

$$ 1\le f_1\le 101-m $$

ways. Therefore

$$ |\mathcal F|=\sum_{m=1}^{101}(101-m)\binom{99}{m-1}=101\cdot2^{98}. $$

Part (2)

Let

$$ T=\sum_{f\in\mathcal F}n(f). $$

We rewrite

$$ T=\sum_{x=1}^{100} N_x $$

where \(N_x\) is the number of functions satisfying \(f(x)=x\).

Fix \(x\). The condition \(f(x)=x\) splits the sequence into two independent parts.

For the left part \(1,\ldots,x\), the sequence is non-decreasing and each step increases by at most 1. The number of possibilities is

$$ 2^{x-1}. $$

For the right part \(x,\ldots,100\), we have \(100-x\) steps each increasing by 0 or 1. Hence the number of possibilities is

$$ 2^{100-x}. $$

Thus

$$ N_x=2^{x-1}\cdot2^{100-x}=2^{99}. $$

Therefore

$$ T=\sum_{x=1}^{100}2^{99}=100\cdot2^{99}. $$

Remark

This problem admits several elegant approaches:

• Lattice path interpretation. View \((k,f(k))\) as lattice points. The condition means each step moves right by 1 and up by at most 1.
• Recurrence method. Define \(g(n,a,b)\) as the number of valid functions with \(f(1)=a\) and \(f(n)=b\). One obtains $$ g(n,a,b)=g(n-1,a,b)+g(n-1,a,b-1). $$
• Generating functions. Each step contributes a factor \((1+x)\), corresponding to whether the value increases or not.