BxMO Team Selection Test

For the first few values of $f$, note that $f(1)=0$, $f(2)=f(3)=f(4)=1$, $f(5)=f(6)=2$, $f(7)=f(8)=3$, $f(9)=f(10)=5$. We claim that for $n\ge 11$, $f(n)$ is strictly increasing as a function of $n$. Therefore there is only a finite number of pairs as in the problem.

We view a way of taking a test as a subset of $\{1,2,\dots ,n\}$ by taking the set of numbers of questions that are answered correctly. We say that a subset $S_n$ of $\{1,2,\dots ,n\}$ is an $n$-equally correct set if the sum of all elements of $S_n$ is equal to the number of elements in the complement of $S_n$ in $\{1,2,\dots ,n\}$. So by definition, $f(n)$ is the number of $n$-equally correct sets. Note that a subset $S_n$ of $\{1,2,\dots ,n\}$ is $n$-equally correct if and only if the sum of all elements of $S_n$ plus the number of elements of $S_n$ equals $n$.

We first claim that $f(n)$ is non-decreasing for $n\ge 1$. Let $S_{n-1}$ be an $(n-1)$-equally correct set. Then adding $1$ to the largest element of $S_{n-1}$ gets us a subset $S_n$ of $\{1,2,\dots ,n\}$. This subset has as many elements as $S_{n-1}$ and has sum $1$ higher than the sum of $S_{n-1}$, which is therefore an $n$-equally correct set. This procedure defines an injective map $F_n$ from the set of $(n-1)$-equally correct sets to the set of $n$-equally correct sets for all $n\ge 2$. Therefore $f(n)\ge f(n-1)$ for all $n\ge 2$.

We now show that, for $n\ge 11$, there exists an $n$-equally correct set that is not in the image of $F_n$. Note that an $n$-equally correct set of which the two largest elements differ by exactly $1$ cannot be in the image of $F_n$; the reason is that a set in this image is one that is obtained by adding $1$ to the largest element of a subset of $\{1,2,\dots ,n-1\}$. If $n=2k+1$ with $k\ge 5$, then $S=\{1,k-2,k-1\}$ is $n$-equally correct, as $1+(k-2)+(k-1)+|S|=2k+1=n$. Similarly, if $n=2k$ with $k\ge 6$, then $S=\{2,k-3,k-2\}$ is $n$-equally correct, because $2+(k-3)+(k-2)+|S|=2k=n$. We conclude that $f(n)>f(n-1)$ for all $n\ge 11$. $\square$