Berkeley Math Circle: Monthly Contest 2

Solution:
The answer is $\binom{199}{100}$. We claim that the functions are precisely those of the form $f(n)=n+a_{n}$, where

$$-99 \leq a_{100}<a_{99}<\cdots<a_{1} \leq 99$$

is an arbitrary sequence. The answer follows from this.

To see that all functions are of this form, we rewrite the given as $f(b)-b<f(a)-a$, which tells us that $f(100)-100<f(99)-99<\cdots<f(1)-1$. Since $f(100)-100 \geq -99$ and $f(1)-1 \leq 99$, this shows all functions are of the form claimed above, i.e. that $1-n \leq f(n)-n \leq 100-n$.

Finally, it remains to check that all functions of the form satisfy the conditions. The inequality $f(b)<f(a)+(b-a)$ is immediate. Moreover, it is easy to see that $a_{100} \geq -99, a_{99} \geq -98$, and so on, so $1 \leq n+a_{n}$ holds; similarly, $n+a_{n} \leq 100$ holds too. Thus $n+a_{n}$ is indeed an element of $X$.