Singapore Mathematical Olympiad (SMO)

Let $m_1<m_2<\cdots <m_n$ be the number of points of each colour. We call $m_1,m_2,\dots ,m_n$ the colour distribution. Then $m_1+\cdots +m_n=2012$ and the number of multi-coloured sets is $M=m_1{m}_2\dots m_n$. We have the following observations.

(i) $m_1>1$. For if $m_1=1$, then $m_1{m}_2\dots m_n<m_2{m}_3\dots m_{n-1}(1+m_n)$. This means if we use $n-1$ colours with colour distribution $m_2,m_3,\dots ,m_{n-1},(1+m_n)$, we obtain a larger $M$.

(ii) $m_{i+1}-m_i\le 2$ for all $i$. For if there exists $k$ with $m_{k+1}-m_k\ge 3$, then the colour distribution with $m_k,m_{k+1}$ replaced by $m_k+1,m_{k+1}-1$ yields a larger $M$.

(iii) $m_{i+1}-m_i=2$ for at most one $i$. For if there exist $i<j$ with $m_{i+1}-m_i=m_{j+1}-m_j=2$, the colour distribution with $m_i,m_{j+1}$ replaced by $m_i+1,m_{j+1}-1$ yields a larger $M$.

(iv) $m_{i+1}-m_i=2$ for exactly one $i$. For if $m_{i+1}-m_i=1$ for all $i$, then $m_1+\cdots +m_n=n{m}_1+\frac{n(n-1)}{2}=2012=4\cdot 503$. Thus $n(2m_1-1+n)=8\cdot 503$. Since $503$ is prime, the parity of $n$ and $2m_1-1+n$ are opposite and $2m_1-1+n>n$, we have $n=8$ and $m_1=248$. The colour distribution with $m_1$ replaced by two numbers $2,246$ (using $n+1$ colours) yields a larger $M$.

(v) $m_1=2$. If $m_n-m_{n-1}=2$, then from (iv), we have $m_1+\cdots +m_n=n{m}_1+\frac{n(n-1)}{2}+1=2012$. Thus $n(2m_1-1+n)=2\cdot 2011$. Since $2011$ is prime, we get $n=2$ and $m_1=1005$ which will lead to a contradiction as in (iv). Thus $m_n-m_{n-1}=1$. $m_{i+1}-m_i=2$ for some $1\le i\le n-2$. Suppose $m_1\ge 3$. Let $m^{\prime }=m_{i+2}-2$. Then $m_i<m^{\prime }<m_{i+1}$ with replacing $m_{i+2}$ by $2,m^{\prime }$ yields a larger $M$. Thus $m_1=2$.

From the above analysis, with $n$ colours, we see that the colour distribution $2,3,\dots ,i-1,i+1,i+2,\dots ,n+1,n+2$, with $3\le i\le n$, yields the maximum $M$. Now we have $\sum m_i=\frac{1}{2}(n+1)(n+4)-i=2012$. Thus $n^2+5n-4020=2i$, $3\le i\le n$, i.e., $n^2+5n\ge 4026$ and $n^2+3n\le 4020$. Thus $n=61$ and $i=3$. Thus the maximum is achieved when $n=61$ with the colour distribution $2,4,5,6,\dots ,63$.