Harvard-MIT Mathematics Tournament

Solution:

We first note that the condition for $f$ is equivalent to $i - f(i) \leq j - f(j)$ for all $1 \leq i < j \leq n$. Letting $f'(x) = x - f(x)$, we see this is equivalent to saying that $f'$ is decreasing. Thus, we only need that $f'(x) \leq f'(x+1)$; in other words, we only require the statement to be true for $j = i+1$.

Fix $m, n$. For any function $g$ satisfying the conditions for $B$, we construct a function $f$ satisfying the conditions for $A$ as follows. For a given function $g$ and $1 \leq i \leq 2n + m$, say that $g$ has an up step at $i$ if $g(i) - g(i-1) = 1$, and say it has a down step at $i$ otherwise. We see that $g$ must be composed of $m + n$ up steps and $n$ down steps. Let $i_1, i_2, \ldots, i_n$ be the indices for which down steps occur, in ascending order. Let $f$ be the function such that $f(j) = (m+1) - g(i_j)$ for $1 \leq j \leq n$. By our argument in the first paragraph, it suffices to show that $f(k) - f(k-1) \leq 1$ for $1 < k \leq n$, or that $g(i_{k-1}) - 1 \leq g(i_k)$. If this were not the case for some $k$, then there would be at least 1 down step in between $i_{k-1}$ and $i_k$, a contradiction, so the condition indeed holds.

We now claim that this construction is a bijection. For injectivity, note that for any two distinct $g, g'$, there exists a $k$ for which the values of $g(i_k), g'(i'_k)$ are distinct, in which case the functions $f, f'$ must be distinct. For surjectivity, consider any suitable $f$. Let $f'$ be the function such that $f'(k) = (m+1) - f(k)$ for all $1 \leq k \leq n$. (The range of this function is still $\{1,2, \ldots, m\}$.) Then, we can find a $g$ as follows: for each $1 \leq k \leq n$ in sequence, have $g$ make up steps until it reaches the value $f'(k)$, then take one down step. This is always possible, as $f'(k+1) - f'(k) \leq 1$. Thus, our claim is true, and our proof is complete.