Maths Olympiad Prep

Library / /12 of 14

Combinatorics Difficulty 6.8 National olympiad Prove it Singapore

There are 20122012 distinct points in the plane each of which is to be coloured using one of nn colours so that the number of points of each colour are distinct. A set of nn points is said to be multi-coloured if their colours are distinct. Determine nn that maximizes the number of multi-coloured sets.

Solution

Let m1<m2<<mnm_1 < m_2 < \dots < m_n be the number of points of each colour. We call m1,m2,,mnm_1, m_2, \dots, m_n the colour distribution. Then m1++mn=2012m_1 + \dots + m_n = 2012 and the number of multi-coloured sets is M=m1m2mnM = m_1 m_2 \dots m_n. We have the following observations.

(i) m1>1m_1 > 1. For if m1=1m_1 = 1, then m1m2mn<m2m3mn1(1+mn)m_1 m_2 \dots m_n < m_2 m_3 \dots m_{n-1} (1 + m_n). This means if we use n1n-1 colours with colour distribution m2,m3,,mn1,(1+mn)m_2, m_3, \dots, m_{n-1}, (1+m_n), we obtain a larger MM.

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

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

(iv) mi+1mi=2m_{i+1} - m_i = 2 for exactly one ii. For if mi+1mi=1m_{i+1} - m_i = 1 for all ii, then m1++mn=nm1+n(n1)2=2012=4503m_1 + \dots + m_n = n m_1 + \frac{n(n-1)}{2} = 2012 = 4 \cdot 503. Thus n(2m11+n)=8503n(2m_1 - 1 + n) = 8 \cdot 503. Since 503503 is prime, the parity of nn and 2m11+n2m_1 - 1 + n are opposite and 2m11+n>n2m_1 - 1 + n > n, we have n=8n=8 and m1=248m_1 = 248. The colour distribution with m1m_1 replaced by two numbers 2,2462, 246 (using n+1n+1 colours) yields a larger MM.

(v) m1=2m_1 = 2. If mnmn1=2m_n - m_{n-1} = 2, then from (iv), we have m1++mn=nm1+n(n1)2+1=2012m_1 + \dots + m_n = n m_1 + \frac{n(n-1)}{2} + 1 = 2012. Thus n(2m11+n)=22011n(2m_1 - 1 + n) = 2 \cdot 2011. Since 20112011 is prime, we get n=2n=2 and m1=1005m_1 = 1005 which will lead to a contradiction as in (iv). Thus mnmn1=1m_n - m_{n-1} = 1. mi+1mi=2m_{i+1} - m_i = 2 for some 1in21 \le i \le n-2. Suppose m13m_1 \ge 3. Let m=mi+22m' = m_{i+2} - 2. Then mi<m<mi+1m_i < m' < m_{i+1} with replacing mi+2m_{i+2} by 2,m2, m' yields a larger MM. Thus m1=2m_1 = 2.

From the above analysis, with nn colours, we see that the colour distribution 2,3,,i1,i+1,i+2,,n+1,n+22, 3, \dots, i-1, i+1, i+2, \dots, n+1, n+2, with 3in3 \le i \le n, yields the maximum MM. Now we have mi=12(n+1)(n+4)i=2012\sum m_i = \frac{1}{2}(n+1)(n+4) - i = 2012. Thus n2+5n4020=2in^2 + 5n - 4020 = 2i, 3in3 \le i \le n, i.e., n2+5n4026n^2 + 5n \ge 4026 and n2+3n4020n^2 + 3n \le 4020. Thus n=61n=61 and i=3i=3. Thus the maximum is achieved when n=61n=61 with the colour distribution 2,4,5,6,,632, 4, 5, 6, \dots, 63.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.