Could you post all the problems from Bulgarian TST 2007?

They are here : http://www.mathlinks.ro/Forum/viewtopic.php?highlight=2007+tst+bulgarian&t=142964 Аlso this is not the TST for IMO 2007, this TST is only for Balkan MO and All-Russian Mathematical Olympiad

Let us divide the graph in two subgraphs $U_{1}$, $U_{2}$ such that $U_{1}$ is the collection of vertices which are are isolated from the others at the beginning and $U_{2}$ the collection of vertices with degree at least $1$ at the beginning. Let $|U_{1}|= 4n-m$ and $|U_{2}|=m$ and clearly $m \leq 2n$. First set of operations is the following: we take one by one all vertices from the $U_{1}$ and apply $\phi_{x}$. After $4n-m$ steps we obtain a completely disjoint graph $U_{1}$, but each vertex form $U_{1}$ is connected with all from $U_{2}$. After first set of operations we can assure that we obtain $(4n-m)\cdot n$ triangles, counting triangle that are formed joining each vertex from $U_{1}$ with $n$ edges in $U_{2}$. However it is not enough in case $2n \geq m \geq \frac{7n}{4}.$ Thus we need the next set of operations, for this we need to analyze $U_{2}$. Let $x_{i}$ be the number of vertices in $U_{2}$ with degree $i$. Then counting on vertices and edges we have $x_{1}+x_{2}+...+x_{k}=m$ and $x_{1}+2x_{2}+3x_{3}+...+kx_{k}=2n$ Thus $2n=x_{1}+2x_{2}+3x_{3}+...+kx_{k}\geq 2m-x_{1}$ and $x_{1}\geq 2m-2n$. As we remember is $x_{1}$ is the number of vertices with degree $1$. Let us find the least number $p$ of pairs that are isolated in $U_{2}$. $2p\geq x_{1}-x_{2}-x_{3}-...-x_{k}=2x_{1}-m\geq 3m-4n$. Observe that $p=\frac{3m-4n}{2}\geq \frac{n}{4}$, because $m \geq \frac{3n}{2}$. Divide $U_{2}$ in two subgraphs $V_{1},V_{2}$ where $V_{1}$ is the set of $\frac{n}{4}$ isolated pairs in $U_{2}$ and $V_{2}$ all that remained. Second set of operations is done on every pair from $V_{1}$. Take first vertex from a pair and apply $\phi_{x}$, then take the second vertex from this pair and apply $\phi_{x}$. Observe that number of edges in $V_{1}$ remained the same $\frac{n}{4}$. $V_{1}$ lost all connections with $U_{1}$, but gained connection with every vertex from $V_{2}$. In $V_{2}$ remained unchanged $\frac{3n}{4}$ edges. Thus the number of triangles that we can assure is $(4n-m)\cdot \frac{3n}{4}_{U_{1}\to V_{2}}+\frac{n}{2}\cdot \frac{3n}{4}_{V_{1}\to V_{2}}+(m-\frac{n}{2})\cdot \frac{n}{4}_{V_{2}\to V_{1}}\geq \frac{9n^{2}}{4}$. To prove the desired inequality we multiply it by $8$ $6n(4n-m)+3n^{2}+(2m-n)n\geq 18n^{2}$ that is equilvalent to $8n^{2}\geq 4nm$ or $2n\geq m$ and we are done.

prowler wrote: $2p\geq x_{1}-x_{2}-x_{3}-...-x_{k}$ Why is this so?

I don't think it's even true

I was thinking in the following way: If $X_{1}$ is the set of the vertices with degree $1$, then each vertex should be connected with another vertex. The minimal numbers of pairs that are connected between them, but disconnected from all other vertices is when, every vertex from $X_{1}$ is connected to some vertex from $X_{i}$ $(i\geq 2)$. Thus $x_{1}-x_{2}-...-x_{k}$ are connected in independent pairs. Therefore $2p \geq x_{1}-x_{2}-...-x_{k}$.

But $x_{k}$ is connected to $k$ vertices, yet you subtract it only once...

prowler wrote: I was thinking in the following way: If $X_{1}$ is the set of the vertices with degree $1$, then each vertex should be connected with another vertex. The minimal numbers of pairs that are connected between them, but disconnected from all other vertices is when, every vertex from $X_{1}$ is connected to some vertex from $X_{i}$ $(i\geq 2)$. Thus $x_{1}-x_{2}-...-x_{k}$ are connected in independent pairs. Therefore $2p \geq x_{1}-x_{2}-...-x_{k}$. You can consider, say, when one vertex is connected to all the other $k$ vectices, and there are no more edges. So $x_{1}=k$ and $x_{k}=1$. But $p=0$.

Sorry, becoming old So we have $2p \geq x_{1}-(2x_{2}+3x_{3}+...+kx_{k})$ $2p\geq 2x_{1}-2n\geq 2(2m-2n)-2n=4m-6n \geq 7n-6n=n$, Thus $p\geq \frac{n}{2}$. Hope now is correct.

I think we can get $ \frac{7n^{2}}{3} $ too.

I'm sorry. We can't get $ \frac{7n^2}{3} $.

Call a vertex lonely if it isn't the endpoint of any edges, else call it social . Call the operation described in the problem a toggle . There are clearly at least $4n - 2 \cdot n = 2n$ lonely vertices. If there are $\ge \frac{9n}{4}$ lonely vertices then we are done by simply toggling all lonely vertices. Otherwise, suppose that there are $2n \le x < \frac{9n}{4}$ lonely vertices. Call one of the $n$ edges isolated if both of its endpoints have degree $1.$ Since there are $>\frac{7n}{4}$ social vertices, there are $>\frac{n}{2}$ isolated edges. Simply toggle the endpoints of $\frac{n}{4}$ of the isolated edges and all the lonely vertices to get a total of $(4n-x-\frac{n}{2}) \frac{n}{4} + \frac{n}{2} (n-\frac{n}{4}) + x(n-\frac{n}{4}) = -\frac{n^2}{4} + (6n-2x) \frac{n}{4} + xn = \frac{5n^2}{4} + \frac{xn}{2} \ge \frac{9n^2}{4}$ triangles, as desired. $\square$