Maths Olympiad Prep

Library / /40 of 40

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it China

Consider 12 figures on the clock face as 12 points. Color them in four colors: red, yellow, blue and green. Each color is used for three points. Configure nn convex quadrilaterals with vertices in these points, such that
(1) there are no same color of vertices for each quadrilateral.
(2) among any three of these quadrilaterals, there is a color of vertices such that the vertices of that color are different.

Find the largest number of nn. (posed by Tao Pingsheng)

Solution

We use A,B,C,DA, B, C, D to represent these four colors, respectively, and the points in the same color by lower letters as a1,a2,a3;b1,b2,b3;c1,c2,c3a_1, a_2, a_3; b_1, b_2, b_3; c_1, c_2, c_3 and d1,d2,d3d_1, d_2, d_3 respectively.

Now consider color AA. If, in nn quadrilaterals, the number of points a1,a2,a3a_1, a_2, a_3 in color AA are n1,n2,n3n_1, n_2, n_3 respectively, then n1+n2+n3=nn_1 + n_2 + n_3 = n. Suppose that n1n2n3n_1 \ge n_2 \ge n_3. If n10n \ge 10, then n1+n27n_1 + n_2 \ge 7. Consider these seven quadrilaterals (its AA color vertex is either a1a_1 or a2a_2), if the numbers of points b1,b2,b3b_1, b_2, b_3 in color BB are m1,m2,m3m_1, m_2, m_3, respectively, then m1+m2+m3=7m_1 + m_2 + m_3 = 7. By symmetricity, we may suppose that m1m2m3m_1 \ge m_2 \ge m_3, then m32m_3 \le 2, that is, m1+m25m_1 + m_2 \ge 5.

Consider these five quadrilaterals (its AA color point is either a1a_1 or a2a_2, and its BB color point is either b1b_1 or b2b_2), if the numbers of points c1,c2,c3c_1, c_2, c_3 in color CC are k1,k2,k3k_1, k_2, k_3, respectively, then k1+k2+k3=5k_1 + k_2 + k_3 = 5. By symmetricity, we may suppose that k1k2k3k_1 \ge k_2 \ge k_3, then k31k_3 \le 1, that is, k1+k24k_1 + k_2 \ge 4.

Consider these four quadrilaterals, denoted as T1,T2,T3,T4T_1, T_2, T_3, T_4 (its color AA point is either a1a_1 or a2a_2, its color BB point is either b1b_1 or b2b_2, and its color CC point is either c1c_1 or c2c_2). Since there are only three points in color DD, there are two quadrilaterals that have the same color DD point. Suppose that the same color DD point of T1,T2T_1, T_2 is d1d_1.

Then, in three quadrilaterals T1,T2,T3T_1, T_2, T_3, whatever be the color of the vertex, there are repeated points, which contradicts condition (2). Hence, n9n \le 9.

We show the maximal number n=9n = 9 by construction of these nine quadrilaterals.

Figure 1

We draw three “concentric annulus” with four points on each radius representing four vertices and the color. So nine radii represent nine quadrilaterals, which satisfy condition (1).

Next, we show that they also satisfy condition (2). Take any three radii (or three quadrilaterals).
If these three radii come from a concentric annulus, for each color except AA, there are three points.
If these three radii come from three concentric annuli, then for color AA, there are three points.
If these three radii come from two concentric annuli, call these three figures Fig. 1, Fig. 2 and Fig. 3. The radius directions are called “up radius”, “left radius” and “right radius”, and denoted, respectively, by SS, ZZ and YY. If three radii have three directions, then there are three points of color BB in three quadrilaterals. If the three radii have only two directions, then there are all cases as shown in the tables below, where 1, 2 and 3 stand for Fig. 1, Fig. 2 and Fig. 3, respectively.

Here, the color in figure means that the three quadrilaterals have color with different figures.

Figure 2
C
Figure 3
D

| | S | 1, 3 | 1, 3 | 1 | | 3 |
|---|-----|------|------|-----|-----|-----|
| Z | 3 | | 1, 3 | 1, 3| 1 |
| Y | | 1 | | 3 | 1, 3|
C
| | S | 1, 3 | 1, 3 | 3 | | 1 |
|---|-----|------|------|-----|-----|-----|
| Z | 1 | | 1, 3 | 1, 3| 3 |
| Y | | 3 | | 1 | 1, 3|
D
| | S | 2, 3 | 2, 3 | 3 | | 2 |
|---|-----|------|------|-----|-----|-----|
| Z | 2 | | 2, 3 | 2, 3| 3 |
| Y | | 3 | | 2 | 2, 3|
C
| | S | 2, 3 | 2, 3 | 2 | | 3 |
|---|-----|------|------|-----|-----|-----|
| Z | 3 | | 2, 3 | 2, 3| 2 |
| Y | | 2 | | 3 | 2, 3|
D

Thus, the maximal number of nn is 9. \square

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.