Korean Mathematical Olympiad

Let $U^{\prime }$ be a subset of $U$ by choosing each triangle with the probability $p$ independently at random. Then the expected number of triangles in $U^{\prime }$ is $mp$.

A sequence of 6 distinct points $(x_1,x_2,\dots ,x_6)$ is called a bad configuration if all 6 triangles $x_1{x}_2{x}_3,x_2{x}_3{x}_4,\dots ,x_4{x}_5{x}_6,x_5{x}_6{x}_1,x_6{x}_1{x}_2$ belong to $U$.

The number of bad configurations in $U$ is at most $m(m-1)(3!{)}^2\le 36m^2$, because it is less than or equal to the number of selecting two triangles, selecting $x_1,x_2,x_3$ from the first triangle, and selecting $x_4,x_5,x_6$ from the second triangle.

If $(x_1,x_2,\dots ,x_6)$ is a bad configuration, then $(x_i,x_{i+1},\dots ,x_{i+6})$ and $(x_i,x_{i-1},\dots ,x_{i-6})$ are bad configurations and so $6\cdot 2=12$ bad configurations form a bunch. Thus the number of bunches of bad configurations in $U$ is at most $36m^2/12=3m^2$.

The probability that a fixed bad configuration of $U$ is contained in $U^{\prime }$ is $p^6$ and therefore the expected number of bunches of bad configurations in $U^{\prime }$ is at most $3m^2{p}^6$.

Thus, the expected number of triangles in $U^{\prime }$ minus the number of bunches of bad configurations in $U^{\prime }$ is at least $mp-3m^2{p}^6$.

Take $p=c{m}^{-1/5}$. Then $$mp-3m^2{p}^6\ge c{m}^{6/5}-3c^6{m}^2{m}^{-6/5}=(c-3c^6)m^{4/5}.$$ By taking $c=1/2$, we deduce $mp-3m^2{p}^6\ge (\frac{1}{2}-\frac{3}{64})m^{4/5}\ge 0.45m^{4/5}$.

Therefore there exists a subset $U^{\prime }$ of $U$ such that the number of triangles in $U^{\prime }$ minus the number of bunches of bad configurations in $U^{\prime }$ is at least $0.45m^{4/5}$. Let $W$ be a subset of $U^{\prime }$ by discarding one triangle in each bunch of bad configurations. Then $W$ contains at least $0.45m^{4/5}$ triangles and no bad configurations, as desired.