There are $ 63$ points arbitrarily on the circle $ \mathcal{C}$ with its diameter being $ 20$. Let $ S$ denote the number of triangles whose vertices are three of the $ 63$ points and the length of its sides is no less than $ 9$. Fine the maximum of $ S$.
Problem
Source: China TST 2007, Problem 3
Tags: algorithm, combinatorics unsolved, combinatorics
30.12.2008 19:05
Lemma: consider a graph with $ 63$ vertices, each two connected by (one) blue or red edge. Suppose there are no blue $ 7$-cliques in the graph. Define $ S_1 = \{V_1, V_2, ... V_{11}\}$ $ S_2 = \{V_{12}, V_{13}, ..., V_{22}\}$ $ S_3 = \{V_{23}, V_{24}, ..., V_{33}\}$ $ S_4 = \{V_{34}, V_{35}, ..., V_{43}\}$ $ S_5 = \{V_{44}, V_{45}, ..., V_{53}\}$ and $ S_6 = \{V_{54}, V_{55}, ..., V_{63}\}$ Then the maximimum number of blue triangles is attained when two vertices are connected by a blue edge if and only if they lie in different $ S_i$'s (this distribuition is the same in Turan's theorem). Proof: take a graph $ G$ and an arbitrary red clique $ C$. Take in $ C$ the vertex that lies in more blue triangles and call it $ V$. We can change our graph by making each vertex in $ C$ be linked with the vertices already linked with $ V$ (and only with this vertices). We are going to prove that this does not make a blue $ 7$-clique appear in the graph and does not decrease the number of triangles. First, notice that a blue triangle can obviously have at most one vertex in $ C$. Thus, since a blue $ 7$-clique with vertices in $ G - C$ cannot have appeared (the edges in this graph are the same), any blue $ 7$-clique has exactly one vertex in $ C$. However, if we change this vertex by $ V$, the colors of the edges will be the same (by construction), therefore we had a $ 7$-clique before. Contradiction! On the other hand, the number of blue triangles with no vertices in $ C$ didn't change, and the number of blue triangles having a given vertex of $ C$ became the number of blue triangles having the vertex $ V$. By the maximality of $ V$, we get the result (there is no decrease). Now we are going to show an algorithm which makes any graph become the described graph (or a graph with less blue triangles), based on the operation $ O$ above. Take a red clique $ R$ (with at least $ 2$ vertices) and make the operation $ O$. If some vertex in $ R$ is connected with some vertex $ A \in G - R$ by a red edge, then all the vertices in $ R$ are. Thus, $ R \bigcup \{A\}$ is a red clique. Make the operation $ O$ and repeat this procedure, until we get a red clique $ R_1$ such that any edge between $ R_1$ and $ G - R_1$ is blue. Now we make the same thing with $ G - R_1$, getting a red clique $ R_2$ and another graph $ G - R_1 - R_2$. Now there are no red edges between $ R_1$ and $ R_2$ or $ R_1$ and $ G - R_1 - R_2$ or $ R_2$ and $ G - R_1 - R_2$. We can make this until we get $ R_6$, at most (if we had $ 7$ red cliques as we said, taking a vertex in each of them, we would get a blue $ 7$-clique). Our algorithm only stops when all the remaining edges are blue (in particular, if $ |G - R_1 - ...| \le 1$, i.e., if there are no edges in the remaining graph). In any case, in the end we will have a partition $ G = R_1 \bigcup ... \bigcup R_k \bigcup B$, where $ B$ is a (maybe empty) blue clique and each $ R_i$ is a red clique (with at least two vertices). Case $ |B| + k \ge 7$, it is obvious that there is a blue $ 7$-clique, which we are assuming false. Else, we can think the vertices in $ B$ as unitary red cliques, therefore having a partition $ G = R_1 \bigcup R_2 \bigcup ... R_n$, with $ n \le 6$. Moreover, if now we accept empty cliques, we may assume $ n = 6$. Now the result is trivial! We just need to prove that, if $ a = |R_1| > |R_2| + 1 = b + 1$, moving a vertex from $ R_1$ to $ R_2$ is going to increase the number of blue triangles. This would imply that, in the maximum, the best distribuition for the points is the most balanced one. Moving a vertex $ X$ from $ R_1$ to $ R_2$ makes the blue triangles with vertices in $ X$ and some point in $ R_2$ disappear and the triangles with vertices in $ X$, some point in $ R_1$ and some point in $ R_3$, $ R_4$, $ R_5$ or $ R_6$ become blue. Since $ a - 1 > b$, we have $ (a - 1)(\sum_{i = 3, 4, 5, 6} |R_i|) > b(\sum_{i = 3, 4, 5, 6} |R_i|)$, id est, the number of triangles becomes greater. Back to the problem. Two vertices of the $ 63$-agon are going to be connected with a blue edge if and only if the distance between them is $ \le 9$. The other pairs of vertices are going to be connected by a red edge. Suppose now we have a blue $ 7$-clique, say $ P_1P_2...P_7$, with $ P_i$ between $ P_{i - 1}$ and $ P_{i + 1}$. We know that an arc has always a length greater than the corresponding chord. Then the circle has length $ \widehat{P_1P_2} + \widehat{P_2P_3} + ... + \widehat{P_7P_1} > 9 + 9 + ... + 9 = 63 > 20\pi$, absurd! It follows that the maximum number of triangles is obtained when $ P_1 \approx ... P_{11} \approx A$, $ P_{12} \approx ... P_{22} \approx B$, $ P_{23} \approx... P_{33} \approx C$, $ P_{34} \approx ... P_{43} \approx D$, $ P_{44} \approx ... P_{53} \approx E$ and $ P_{54} \approx ... P_{63} \approx F$ and $ ABCDEF$ is a regular hexagon (its side must be the radius of $ \mathcal{C}$, that is $ 10$, that is $ > 9$, which means the maximum is really attained). It is easy to see that this number is $ 11^3 + 9.11^2.10 + 9.11.10^2 + 10^3 = 23121$.
01.01.2009 16:57
Did somebody read my post? I want to know if it is right...
10.07.2009 08:04
Hi Renan, I think that your proof is not right. I have the number 25515 to be the answer. The example would be when the 63 points are divided into 7 groups of 9 points each(the points in a group are closely together), 6 form a regular hexagon and the other is the center of the hexagon. It is easy to see that the example verify. You made a great mistake when saying that the arc is greater to the corresponding chord leads to an absurd. My proof is actually quite similar to that of the Turan Theorem. I will post it later (it is 0:00 and I am sleepy).
10.02.2015 14:23
No,Cuenca,it says 63 points ON the circle.
10.02.2015 14:56
But i think Feliz should connect a blue edge if and only if the distance >=9