5. Let $A$ be a finite set of natural numbers. A partition of $A$ into two non-empty disjoint subsets $A_{1}$ and $A_{2}$ is called demonic if the least common multiple of the elements of $A_{1}$ is equal to the greatest common divisor of the elements of $A_{2}$. What is the smallest number of elements that $A$ must have for there to be exactly 2016 demonic partitions?
Solution (Louis): Let $A=A_{1} \cup A_{2}$ be a demonic partition and let $a=\max \left(A_{1}\right), b=\min \left(A_{2}\right)$. We then have that the least common multiple of the elements of $A_{1}$ is greater than or equal to $a$ and the greatest common divisor of the elements of $A_{2}$ is less than or equal to $b$. Therefore, $a < b$, and thus $A_{1}$ and $A_{2}$ are obtained from $A$ by placing all elements less than a certain number in $A_{1}$ and all remaining elements in $A_{2}$. In particular, if $A$ has $n$ elements, the number of demonic partitions is at most $n-1$.

Now let's construct a set $A$ that admits exactly 2016 demonic partitions. We write the pair $(x, y)$ to represent the number $2^{x} \cdot 3^{y}$, and the set $A$ is then

$$
A=\{(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2), \ldots,(1008,1008)\}
$$

We see easily that we can place the separation between $(a, a)$ and $(a+1, a)$ or between $(a, a+1)$ and $(a+1, a+1)$ to obtain demonic sets. This gives exactly 2016 demonic sets, and $A$ has 3025 elements.

It remains to show that $A$ must necessarily have at least 3025 elements. To fix the notation, let

$$
A=\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}
$$

First, we cannot have that $A_{1}=\left\{x_{1}\right\}$ and $A_{1}^{\prime}=\left\{x_{1}, x_{2}\right\}$ are two demonic partitions. Indeed, if $A_{1}, A_{2}$ is a demonic partition, the least common multiple of $A_{1}$ is $x_{1}$ and thus the greatest common divisor of $A_{2}$ is also $x_{1}$, so $x_{1} \mid x_{i}$ for all $i \geq 1$. In particular, $x_{1} \mid x_{2}$, so the least common multiple of $A_{1}^{\prime}$ is $x_{2}$, which implies that the greatest common divisor of $A_{2}^{\prime}$ is $x_{2}$ and thus $x_{2} \mid x_{i}$ for all $i \geq 2$. But then the greatest common divisor of $A_{2}$ is $x_{2}$, which contradicts the fact that $A_{1}, A_{2}$ is a demonic partition. Suppose there exists $i$ such that $A_{1}=\left\{\ldots, x_{i}\right\}, A_{1}^{\prime}=\left\{\ldots, x_{i}, x_{i+1}\right\}, A_{1}^{\prime \prime}=\left\{\ldots, x_{i}, x_{i+1}, x_{i+2}\right\}$ form three demonic partitions. We then have the relations

$$
\begin{gathered}
x_{i}\left|\operatorname{lcm}\left(A_{1}\right)=\operatorname{gcd}\left(A_{2}\right)\right| b \quad \forall b \in A_{2} \\
x_{i+1}\left|\operatorname{lcm}\left(A_{1}^{\prime}\right)=\operatorname{gcd}\left(A_{2}^{\prime}\right)\right| b^{\prime} \quad \forall b^{\prime} \in A_{2}^{\prime}
\end{gathered}
$$

and

$$
x_{i+2}\left|\operatorname{lcm}\left(A_{1}^{\prime \prime}\right)=\operatorname{gcd}\left(A_{2}^{\prime \prime}\right)\right| b^{\prime \prime} \quad \forall b^{\prime \prime} \in A_{2}^{\prime \prime}
$$

However, the last two relations imply that $\operatorname{gcd}\left(A_{2}^{\prime}\right)=x_{i+2}$ and $\operatorname{gcd}\left(A_{2}\right)=x_{i+1}$, and therefore also that $\operatorname{lcm}\left(A_{1}\right)=x_{i+1}$ because $A_{1}, A_{2}$ is monotonic. We now arrive at a contradiction because $A_{1}^{\prime}$ is constructed by adding only the element $x_{i+1}$ to $A_{1}$, so $\operatorname{lcm}\left(A_{1}^{\prime}\right)=x_{i+1}$ as well, and since we have already proved that $\operatorname{gcd}\left(A_{2}^{\prime}\right)=x_{i+2}$, the pair $A_{1}^{\prime}, A_{2}^{\prime}$ could not be demonic. Thus it is impossible to obtain 2016 demonic pairs if $A$ has strictly fewer than 3025 elements.

## Marking Scheme :

- $|A| \leq 3025$ : 3 points
- $|A| \geq 3025$ : 4 points, with one point if it is shown that it suffices to consider the $|A|-1$ partitions given by separating the smallest elements from the largest.
- If the argument is correct but the number of elements calculated is wrong: -1 point