This is pathetic... Anybody who has studied the probabilistic method can know in an instance that this problem is about the 'alteration' technique. Disappointed by the quality of the last problem.

Well there goes my chances for FKMO Excellence Award XD @above, can you show the details? I know what alteration is but with my lack of combinatorics skills I failed solve it.

rkm0959 wrote: Well there goes my chances for FKMO Excellence Award XD @above, can you show the details? I know what alteration is but with my lack of combinatorics skills I failed to solve it. Define a set of six triangles 'bad' if they satisfy the second condition. Choose each triangle with probability $p$, independently. Let $X$ be the random variable denoting the number of chosen triangles, and $Y$ be the random variable of the number of bad sets, and all six triangles being chosen. $E[X] = pm$ and $E[Y] = p^6n$ where $n$ is the total number of bad sets. If we remove one triangle from each bad sets such that all six are chosen, then we get a set satisfying the condition with at least $X-Y$ elements. Now what is the expected value of $X-Y$? We just use the linearity of expectation to get \[E[X-Y] = pm - p^6n \geq pm - 3p^6m^2 \]$n\leq 3m^2$ or maybe something similar($\alpha m^2$) can be shown easily. Now take the derivative of w.r.t. $p$ and determine $p$ to make the RHS maximal. Now, to finish, you only need the fact that if you are lucky enough on your coin-flipping, then you can actually achieve something $\geq E[X-Y]$

By the way, @jaydoubleuel you mixed up the variables $m$ and $n$. In the solution above, $n$ is the number of triangles, whereas in the problem, $m$ is the number of triangles.

Thanks I fixed it

Indeed $n\leq 3m(m-1)$ holds: Counting $(A,B,C,D,E,F)$ with $ABC,DEF\in U$ gives $36m(m-1)$, and it's at least $12n$, hence the desired result. Now setting $p=(18m)^{-1/5}$ we get the result.

IsoLyS wrote: Counting $(A,B,C,D,E,F)$ with $ABC,DEF\in U$ gives $36m(m-1)$, and it's at least $12n$, hence the desired result. I am confused here, can you explain specifically? Thanks

jaydoubleuel wrote: Choose each triangle with probability $p$, independently. Are you sure you can choose them idependently? Because if you select $ABC,BCD,CDA$, then you also selected $DAB$, if it is in $U$. This should change $E[X]$ and $E[Y]$.

mjuk wrote: jaydoubleuel wrote: Choose each triangle with probability $p$, independently. Are you sure you can choose them idependently? Because if you select $ABC,BCD,CDA$, then you also selected $DAB$, if it is in $U$. This should change $E[X]$ and $E[Y]$. We are making a set of 'triangles' $W$ of our own. We have freedom to include $DAB$ in $W$ or not. It is not something like including all triangles that are induced by the chosen segments and points.

@Complex2Liu, Count 6-tuple of distinct points $(A,B,C,D,E,F)$ with $ABC, DEF$ included in $U$. First, select a triangle for first one, and select another for next one: this is $m(m-1)$. Next, determine its order: Each triangle makes $3!$ times, hence there are $36m(m-1)$ tuples. Now consider $(A,B,C,D,E,F)$ with $ABC,BCD,CDE,DEF,EFA,FAB)$ in $U$. Each circular permutation with symmetry allowed, which is all different, is counted 12 times, since beginning point counts 6 times and the direction counts 2 times. Therefore they are $12n$, which means $36m(m-1)$ is at least $12n$.

Standard alteration problem. We say that a $6$-tuple $(A, B, C, D, E, F)$ is bad if the triangles $ABC$ and $DEF$ are in $W$. Note that the number of bad tuples is at most $(3!)^2 \cdot m(m-1)=36m(m-1)$. We proceed via alteration, a probabilistic technique. We select elements of $U$ that induce $W$, each triangle chosen with probability $p>0$. After the selection is complete, we make $W$ well-defined by considering all bad $6$-tuples $(A, B, C, D, E, F)$ and deleting one of $ABC$ and $DEF$. Now, note that \[\mathbb{E}[|W|]=p \cdot m - \frac{36m(m-1)}{2! \cdot 3!} \cdot p^6 = p \cdot m - 3(m^2-m)p^6,\]so it remains to select an appropriate value of $p$ such that $\mathbb{E}[|W|] \ge 0.45 \cdot m^{0.8}$. This can be easily seen by IVT, and we conclude.