IMO Team Selection Contest

Let $A$, $B$, and $C$ be the sets of the points on different sides and $a$, $b$ and $c$ their cardinalities respectively. Let us count all the triplets $(p,q,r)$, where $p\in A$, $q\in B$, and $r\in C$ and they are either pairwise connected or pairwise not connected. For all $p\in A$, $q\in B$ there exist exactly $k$ points $r\in C$, for which the condition holds: if $p$ and $q$ are connected, then choose the $k$ points which are connected to both; if $p$ and $q$ are not connected, then pick the $k$ points which are connected to neither of them. Therefore the total number of such triplets is $kab$. Similarly, for all $q\in B$, $r\in C$ we find that the total number of those triplets is $kbc$, and for all $r\in C$, $p\in A$ we find that the number of those triplets is $kca$. Therefore, $ab=bc=ca$, implying $a=b=c=\frac{n}{3}$.

Let us now count all the other triplets $(p,q,r)$ in which $p\in A$, $q\in B$ and $r\in C$. Similarly to the previous paragraph, we can see that for all $p\in A$, $q\in B$ there exist exactly $k$ points $r\in C$ for which $r$ is connected to neither of those if $p$ and $q$ are connected to each other, and $r$ is connected to both if $p$ and $q$ are not connected to each other. The number of such triplets $(p,q,r)$ is $kab=k{\left(\frac{n}{3}\right)}^2$. Similarly, we then count the triplets $(p,q,r)$ in which $p$ is connected to neither of $q$ or $r$ if $q$ and $r$ are connected to each other and $p$ is connected to both $q$ and $r$ if $q$ and $r$ are not connected to each other. The number of such points is also $k{\left(\frac{n}{3}\right)}^2$. Finally, we count the triplets $(p,q,r)$ in which $q$ is connected to neither of $r$ and $p$ if $r$ and $p$ are connected to each other and $q$ is connected to both $r$ and $p$ if $r$ and $p$ are not connected. The number of those triplets is also $k{\left(\frac{n}{3}\right)}^2$. We have now counted all the possible triplets. Therefore, the total number of triplets $(p,q,r)$ ($p\in A$, $q\in B$ and $r\in C$) is $4k{\left(\frac{n}{3}\right)}^2$. On the other hand, the number of triplets is ${\left(\frac{n}{3}\right)}^3$. The equality $4k{\left(\frac{n}{3}\right)}^2={\left(\frac{n}{3}\right)}^3$ gives us $n=12k$.

It remains to prove that it is possible to mark $4k$ points on each side to satisfy the conditions. Let us first look the case $k=1$. Let the sides of triangle be labelled as $0$, $1$, and $2$ with each of the sides containing points labelled as $0$, $1$, $2$, and $3$. For all $i=0,1,2$ we connect the even numbered points on the side $i$ with points $0$ and $1$ on the side $(i+1)\mathrm{mod}3$ and the odd numbered points on the side $i$ with points $2$ and $3$ on the side $(i+1)\mathrm{mod}3$.



Then we have for each pair of points (which are not on the same side) exactly one point of the third side which are connected to both and exactly one point which is connected to neither of them. For case $k>1$ we substitute each point with $k$ different points and connect those which were generated from points that were connected before.