USA IMO 2003

The maximum and minimum values of $f$ are $1334$ and $668$, respectively.

a. First, we will show that the maximum value of $f$ is $1334$. The set $S=\{1,2,\dots ,667\}\cup \{1336,1337,\dots ,2002\}$ is a skipping set for $(a,b)=(667,668)$, so $f(667,668)\ge 1334$.

Now we prove that for any $0<a<b<1000$, $f(a,b)\le 1334$. Because $a\ne b$, we can choose $d\in \{a,b\}$ such that $d\ne 668$. We assume first that $d\ge 669$. Then consider the $2003-d\le 1334$ sets $\{1,d+1\},\{2,d+2\},\dots ,\{2003-d,2003\}$. Each can contain at most one element of $S$, so $|S|\le 1334$.

We assume second that $d\le 667$ and that $\lceil \frac{2003}{a}\rceil$ is even, that is, $\lceil \frac{2003}{a}\rceil =2k$ for some positive integer $k$. Then each of the congruence classes of $1,2,\dots ,2003$ modulo $a$ contains at most $2k$ elements. Therefore at most $k$ members of each of these congruence classes can belong to $S$. Consequently, $$\begin{array}{rl}|S|& \le ka<\frac{1}{2}\left(\frac{2003}{a}+1\right)a=\frac{2003+a}{2}\\ & \le 1335,\end{array}$$ implying that $|S|\le 1334$.

Finally, we assume that $d\le 667$ and that $\lceil \frac{2003}{a}\rceil$ is odd, that is, $\lceil \frac{2003}{a}\rceil =2k+1$ for some positive integer $k$. Then, as before, $S$ can contain at most $k$ elements from each congruence class of $\{1,2,\dots ,2ka\}$ modulo $a$. Then $$\begin{array}{rl}|S|& \le ka+(2003-2ka)=2003-ka\\ & =2003-\left(\frac{\lfloor \frac{2003}{a}\rfloor }{2}-1\right)a\\ & \le 2003-\left(\frac{\frac{2003}{a}-1}{2}\right)a\\ & =\frac{2003+a}{2}\le 1335.\end{array}$$ The last inequality holds if and only if $a=667$. But if $a=667$, then $\frac{2003}{a}$ is not an integer, and so the second inequality is strict. Thus, $|S|\le 1334$. Therefore the maximum value of $f$ is $1334$.

b. We will now show that the minimum value of $f$ is $668$. First, we will show that $f(a,b)\ge 668$ by constructing a skipping set $S$ for any $(a,b)$ with $|S|\ge 668$. Note that if we add $x$ to $S$, then we are not allowed to add $x$, $x+a$, or $x+b$ to $S$ at any later time. Then at each step, let us add to $S$ the smallest element of $\{1,2,\dots ,2003\}$ that is not already in $S$ and that has not already been disallowed from being in $S$. Then since adding this element prevents at most three elements from being added at any future time, we can always perform this step $\lceil \frac{2003}{3}\rceil =668$ times. Thus, $|S|\ge 668$, so $f(a,b)\ge 668$.

Now notice that if we let $a=1,b=2$, then at most one element from each of the $668$ sets $\{1,2,3\},\{4,5,6\},\dots ,\{1999,2000,2001\},\{2002,2003\}$ can belong to $S$. This implies that $f(1,2)=668$, so indeed the minimum value of $f$ is $668$.