[indiscipline][2] 初中不等式

飞机上半昏迷状态下以为无法调整, 暴力算出来的搞笑解答. 非常具有统计色彩 (nod)

题面

A simple graph G is called complete k-partite if there's a partion of V(G): A_1,..., A_k s.t. for all i there's no edge with both vertices in A_i , and for any v\in A_i and any u\in A_j with i\ne j, vu\in E(G). A Turán graph is a complete k-partite graph with any A_i being of size \lfloor{n\over k}\rfloor or \lceil{n\over k}\rceil, where n=|V(G)|. Prove that any k-partite complete graph with vertex number n which is not Turán has strictly less edges than a Turán graph with same vertex number.

幽默方法

Let a_i=|A_i|, it's very easy to see that for a complete k-partite graph the total number of edges is {1\over 2}\sum a_i(n-a_i), where n is the number of vertices, and we have \sum a_i=n. Hence to prove Turán graph has maximal edges is equivalent to proving \sum a_i^2 or \sum (a_i-{n\over k})^2 is minimized for the setting, as \sum a_i(n-a_i)=n\sum a_i-\sum a_i^2=n^2-\sum a_i^2, and \sum (a_i-{n\over k})^2 can be similarly written as \sum a_i^2 plus a constant. In fact, the second expression is inspired by the notion of variance.

Now for a Turán graph, letting n=qk+r where q\in\mathbb Z, 1\le r\le k-1 as if k|n the result is immediate, we have r A_i with size \lceil{n\over k}\rceil and k-r with size \lfloor{n\over k}\rfloor. Therefore in this setting \sum (a_i-{n\over k})^2=r({k-r\over k})^2+(k-r)({r\over k})^2={r(k-r)\over k}, and \sum a_i^2=(k-r)q^2+r(q+1)^2=kq^2+2rq+r. Note that this is also compatible with r=0, or r=k, namely q'=q+1 and r'=0.

We proceed by induction on k. It's easy to verify the base case. Now assume \sum a_i^2 is minimized by the setting of Turán graph for any k-1 tuple of a_i with fixed sum, if without losing generality a_1\le q-j with j\ge 1, if j\ge k-r, \sum(a_i-{n\over k})^2\ge (a_1-{n\over k})^2\ge (k-r)^2>{r(k-r)\over k} as 1\le r\le k-1. Hence \sum_{i=2}^k a_i=n-q+j=q(k-1)+r+j. Using induction hypothesis \sum a_i^2\ge (q-j)^2+(k-1)q^2+2(r+j)q+r+j=kq^2+2rq+j^2+j+r>kq^2+2rq+r as j\ge 1.

When WLOG a_1\ge q+1+j where j\ge 1 is similar. If you just wanna kill your time you may try this almost identical calculation.