A finite set of integers is called bad if its elements add up to 2010. A finite set of integers is a Benelux-set if none of its subsets is bad. Determine the smallest integer $n$ such that the set $\{502,503,504, \ldots, 2009\}$ can be partitioned into $n$ Benelux-sets.

(A partition of a set $S$ into $n$ subsets is a collection of $n$ pairwise disjoint subsets of $S$, the union of which equals $S$.)
As $502+1508=2010$, the set $S=\{502,503, \ldots, 2009\}$ is not a Benelux-set, so $n=1$ does not work. We will prove that $n=2$ does work, i.e. that $S$ can be partitioned into 2 Benelux-sets.

Define the following subsets of $S$:

$$
\begin{aligned}
A & =\{502,503, \ldots, 670\}, \\
B & =\{671,672, \ldots, 1005\}, \\
C & =\{1006,1007, \ldots, 1339\}, \\
D & =\{1340,1341, \ldots, 1508\}, \\
E & =\{1509,1510, \ldots, 2009\}.
\end{aligned}
$$

We will show that $A \cup C \cup E$ and $B \cup D$ are both Benelux-sets.

Note that there does not exist a bad subset of $S$ of one element, since that element would have to be 2010. Also, there does not exist a bad subset of $S$ of more than three elements, since the sum of four or more elements would be at least $502+503+504+505=2014>2010$. So any possible bad subset of $S$ contains two or three elements.

Consider a bad subset of two elements $a$ and $b$. As $a, b \geq 502$ and $a+b=2010$, we have $a, b \leq 2010-502=1508$. Furthermore, exactly one of $a$ and $b$ is smaller than 1005 and one is larger than 1005. So one of them, say $a$, is an element of $A \cup B$, and the other is an element of $C \cup D$. Suppose $a \in A$, then $b \geq 2010-670=1340$, so $b \in D$. On the other hand, suppose $a \in B$, then $b \leq 2010-671=1339$, so $b \in C$. Hence $\{a, b\}$ cannot be a subset of $A \cup C \cup E$, nor of $B \cup D$.

Now consider a bad subset of three elements $a, b$ and $c$. As $a, b, c \geq 502, a+b+c=2010$, and the three elements are pairwise distinct, we have $a, b, c \leq 2010-502-503=1005$. So $a, b, c \in A \cup B$. At least one of the elements, say $a$, is smaller than $\frac{2010}{3}=670$, and at least one of the elements, say $b$, is larger than 670. So $a \in A$ and $b \in B$. We conclude that $\{a, b, c\}$ cannot be a subset of $A \cup C \cup E$, nor of $B \cup D$.

This proves that $A \cup C \cup E$ and $B \cup D$ are Benelux-sets, and therefore the smallest $n$ for which $S$ can be partitioned into $n$ Benelux-sets is $n=2$.

Remark. Observe that $A \cup C \cup E_{1}$ and $B \cup D \cup E_{2}$ are also Benelux-sets, where $\left\{E_{1}, E_{2}\right\}$ is any partition of $E$.