Problem 1876

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{aligned} |S| &\le ka < \frac{1}{2} \left( \frac{2003}{a} + 1 \right) a = \frac{2003 + a}{2} \\ &\le 1335, \end{aligned}$$
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{align*} |S| &\le ka + (2003 - 2ka) = 2003 - ka \\ &= 2003 - \left( \frac{\left\lfloor \frac{2003}{a} \right\rfloor}{2} - 1 \right) a \\ &\le 2003 - \left( \frac{\frac{2003}{a} - 1}{2} \right) a \\ &= \frac{2003 + a}{2} \le 1335. \end{align*}$$
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$.