Let $V$ be the set of vertices, $E$ be the set of edges and for $i=1,2,3$ let $E_i$ be the set of edges of $K_{2017}$ which are labelled with number $i$. Finally let $G_1$ be the subgraph of $K_{2017}$ which have all vertices in $V$ end all edges in $E_1$. Lemma: considering the graph $G_1$ (it may be disjoint) let's define a function $f:V\rightarrow\mathbb{N}$ which associates each vertex with the maximum degree of vertices connected to it. Then $$\sum_{v\in V}f\left(v\right)\ge 2\left|E_1\right|$$ proof: considering $G_1$, define a function $g:V\rightarrow\mathbb{Q}$ which associates each vertex with the average of the degrees of vertices connected to it. Obviously $g\left(v\right)\le f\left(v\right)$ so if we show that $\sum_{v\in V}g\left(v\right)\ge\sum_{v\in V}\deg\left(v\right)=2\left|E_1\right|$ we are done (remember that in this case degrees are defined on $G_1$). Indeed it's evident that if $S$ is the set of ordered couples of connected vertices in $G_1$, we have that $$\sum_{v\in V}g\left(v\right)=\sum_{\left(u,v\right)\in S}\frac{\deg\left(u\right)}{\deg\left(v\right)}$$so if $S_1$ is the set of non ordered couples of connected vertices in $G_1$ (actually $S_1\equiv E_1$), $$\sum_{v\in V}g\left(v\right)=\sum_{\left(u,v\right)\in S_1}\frac{\deg\left(u\right)}{\deg\left(v\right)}+\frac{\deg\left(v\right)}{\deg\left(u\right)}\stackrel{AM-GM}{\ge}\sum_{\left(u,v\right)\in S_1}2=2\left|S_1\right|=2\left|E_1\right|\ \ \blacksquare$$ Now let's go back to the main problem. Considering $K_{2017}$, let $h$ be a function that associates each vertex to the number of edges in $E_3$ which starts from it. Clearly $$\frac{1}{2}\sum_{v\in V}h\left(v\right)=\left|E_3\right|$$Besides note that $h\left(v\right)\ge f\left(v\right)-1$ (remember that $f$ is defined on $G_1$ and not on $K_{2017}$), infact consider the vertex $u$ such that $\left(u,v\right)\in E_1$ and such that its degree in $G_1$ is $f\left(v\right)$. Now let's define $V_{1,u}$ as the set of vertices which are connected to $u$ in $G_1$. Hence $\left\{v\right\}\times \left(V_{1,u}\setminus v\right)\subseteq E_3$ (obviously we are considering each edge as a couple of vertices) in order to respect the hypothesis that any triangol has sum of labels at least $5$. So we can say that $$\left|E_3\right|=\frac{1}{2}\sum_{v\in V}h\left(v\right)\ge\frac{1}{2}\sum_{v\in V}\left(f\left(v\right)-1\right)=-\frac{2017}{2}+\frac{1}{2}\sum_{v\in V}f\left(v\right)\stackrel{\text{lemma}}{\ge}\left|E_1\right|-\frac{2017}{2}$$Hence, since $\left|E_3\right|$ is integer, it must be at least $\left|E_1\right|-1008$. So, since if we fix $\left|E_1\right|$ then the minimum average of labels of edges in $K_{2017}$ is reached when $\left|E_3\right|$ is minimum, we can say that the minimum average is at least $$\frac{3\left(\left|E_1\right|-1008\right)+\left|E_1\right|+2\left(\binom{2017}{2}-2\left|E_1\right|+1008\right)}{\binom{2017}{2}}=\frac{4033}{2017}$$Calling $v_1,v_2,...,v_{2017}$ the edges of $K_{2017}$ this optimal situation is effectively reached if all edges of graph $K_{2017}$ are labelled with $2$ except for edges connecting $v_{2i-1}$ and $v_{2i}$ for $i=1,...,1008$ which will be labelled with $1$. It's easily verifiable that in this case the hypothesis are respected so we are done.

Remark 1. If a triangle has $2$ of its edges both labelled $1$ then the other edge must be labelled $3$. There is a way to label $K_{2017}$ so that the average of labels of edges $T$ is minimum. In such labelling, consider edges $BC$ so $BC$ is labelled $3$. Consider all triangles $ABC$ so $CA,CB$ are both labelled $1$. If we change the labels of edges of $\triangle ABC$ from $1,1,3$ to $1,2,2$ ($BC$ is changed to $2$) then the average of labels $T$ remains the same and is still minimum. We do the same for all triangles $XBC$ with $XB,XC$ labelled $1$ then move on to other edges like $BC$ whose original label is $3$. After this, we obtain a new label $\mathcal{T}$ for $K_{2017}$ so that no edge is labelled $3$ and the average of labels $T$ is still minimum. Since no edge is labelled $3$ in this configuration $\mathcal{T}$ so according to remark 1, there doesn't exist two edges sharing same endpoint and are both labelled $1$. This follows, number of edges labelled $1$ is at most $\frac{2016}{2}=1008$, the remaining edges are labelled $2$. Thus, the minimum average of labels is $$T= \frac{1}{ \binom{2017}{2}} \left[ 2 \cdot \left( \binom{2017}{2}-1008 \right)+1008 \right]= 2- \frac{1008}{\binom{2017}{2}}=2-\frac{1}{2017}.$$Construction: Consider $2017$ vertices $A_1, \ldots, A_{2017}$ with $A_1A_2,A_3A_4, \ldots, A_{2015}A_{2016}$ are labelled $1$. The remaining edges are labelled $2$.

Bern's first lemma is also important in this problem.

shinichiman wrote: We do the same for all triangles $XBC$ with $XB,XC$ labelled $1$ Maybe I misunderstood but how can you do the same if you have already changed the label of BC into 2?

bern-1-16-4-13 wrote: Maybe I misunderstood but how can you do the same if you have already changed the label of BC into 2? Yes, $BC$ is already changed to $2$ so you only need to change one of $XB,XC$ to $2$. Sorry for my bad English.

but in this way the average doesn't remain unchanged, because the sum of labels increase by $1$

bern-1-16-4-13 wrote: but in this way the average doesn't remain unchanged, because the sum of labels increase by $1$ No. First, you find all edges labelled $3$ and change to $2$. Next, you find all $\triangle XBC$ where $BC$ is originally $3$ and $XB,XC$ are both $1$. Since $BC$ is already changed to $2$, you change one of $XB,XC$ from $1$ to $2$. Hence, $XBC$ will from $1,1,3$ to $1,2,2$ which still has the sum of labels $5$ and therefore the sum of labels of $\binom{2017}{2}$ edges is still minimal.

No! Suppose $XB$,$XC$,$AB$,$BC$ worth $1$. Then if you change wlog $XB$ into $2$, $AB$ into $2$, and $BC$ into $2$ the sum increases by $1$ so the average changes.

To bern what was the motivation for such a brilliant proof.

First of all one should guess how looks like the cases of equality (there are many as the title of the topic says XD). Since the average of labels depends just on the difference of number of labels $1$ and number of $3$, you'd love to find a lower bound for the number of labels $3$ in function of the number of labels $1$. So it could be a good idea to count how many labels $3$at least start from a fixed vertice (in this way you come across the function $f$ I've defined, and you are happy because $f$ gives you a very good bound in the cases of equality). Now since you can see the number of labels $1$ as the half of the sum of degrees in $G_1$ you must try to find a relation between this quantity and the sum of $f\left(v\right)$ over all vertices. The final idea is to minorize $f$ with the function $g$, and it may be suggested by the fact that the sum of degrees in $G_1$ is completely simmetric over the vertices, and $g$ has more simmetry than $f$ so it could be esier to work on it.

There is one simpler motivation. Bern is a very smart guy, he easily solves even the hardest math olympiad problems. He is surely going to win a gold medal at IMO, and mental processes of IMO gold medalists cannot be understood by us common mortals. I give my congratulations to him for his solution, and for his IMO gold medal in advance.

It's so enjoyable when you jinx in italian, but in english it's even more "lovely" The truth is that YOU're simply gonna take a perfect score But let's not go OT

Suppose we have a labelling which gives the minimum sum of labels. Consider a vertex $V$. If there are as many edges labelled $3$ as that of $1$ coming out of $V$, change all of them to $2$. Clearly this can only decrease the sum, and the condition of problem is still satisfied. Call this $(1)$. Hence for each vertex, there are more $1$ edges than $3$ edges. Say for a vertex $A$ there are $n$ edges labelled $1$. Then the $n$ endpoints of these edges exluding $A$ forms a $K_n$, whose labels are all $3$. Let one of these endpoints be $B$. Then from $(1)$, $B$ must have at least $n$ edges labelled $1$. Let the endpoints of these edges, excluding $A$, form a group $S$ (so $|S|\geq n-1$). This means that any edge conencting $A$ to a vertex $C$ in $S$ is labelled $3$. (Consider triangle $ABC$). Combined with $(1)$, $A$ must have exactly $n-1$ edges labelled $3$. Thus for each vertex $A$ the sum of labels $S_A$ of its edges is minimally $2\cdot 2016-1$. As the sum of all $S_A$ must be even, one of them is at least $2\cdot 2016$, giving the lower bound for the question.

disregard

In general, the answer for $2m+1$ is $2 - \frac{1}{2m+1}$. We prove the lower bound by induction on $m$: assume some edge $vw$ is labeled $1$. Then we delete it, noting that edges touching $v$ and $w$ contribute a sum of at least $4 \cdot (2m-1) = 8m-4$. Thus by induction hypothesis the total is at least \[ \binom{2m-1}{2} \left( 2 - \frac{1}{2m-1} \right) + (8m-4) + 1 = \binom{2m+1}{2} \left( 2 - \frac{1}{2m+1} \right) \]as desired. Interestingly, there are (at least) two equality cases. One is to have all edges be $2$ except for $m$ disjoint edges, which have weight $1$. Another is to split the vertex set into two sets $A \cup B$ with $|A| = m$ and $|B| = m+1$, then weight all edges in $A \times B$ with $1$ and the remaining edges with $3$. Remark: In fact, given any equality case on $c$ vertices, one can generate one on $c+2$ vertices by two vertices $u$ and $v$, connected to the previous $c$ vertices with weight $2$, and then equipping $uv$ with weight $1$.

My solution involved deleting one vertex at a time. The key idea is to consider the sum of the weights attached to any vertex: if this is at least $2n$ for even $n$ and $2n-1$ for odd $n$, we can remove and proceed by induction. If not, then it violates the minimum total weight for $n-1$ (usually). Since the answer for $2m$ is also $2 - \frac{1}{2m-1}$, this created some bounding complications for the even case of the inductive step. Thankfully there is only one exact configuration with any issues, and it can easily be disproved due to needing more $3$ weighted edges than it can sustain. Of course if I'd just noted the relation between $1$s and $3$s used there worked generally, the proof would've taken 10 minutes instead of the 2.5 hours Very nice idea, bern. How long did that take to develop and write? The solution provides nice insights, but if it took you too long you might have been hoodwinked just like I was xD

Among all 6 problems, it's the only problem I didn't solve. I found about $n/2$ case of equality case. I have no clue where I should adjust the problem to.

I have a solution using weight shifting like arguments. First let's prove the following lemma which kills the problem: Lemma: Given a $C_3$-free graph on $2017$ vertices and $k>1008$ edges. We call a pair of vertices $(u,v)$ fat if there exists a vertex $x$ adjacent to both $u$ and $v$. There exist at least $k-1008$ different fat pairs. Proof: We will prove this algorithmically. Start with a $C_2$-free( ) graph on $2017$ vertices. Now we will add in our $k$ edges, but we will start by adding first all the non-adjacent edges(call them initial edges), which are at most $1008$ at number. It is clear that any edge we will add from this point(call those edges - babies) will be adjacent to at least one initial edge. Everytime we add a baby, let's say $uv$ we pick exactly one segment, $vr$ and color it in red, if it isn't already painted in red, where $ur$ is an initial edge, if there are more segments that we can choose, we pick one randomly. Suppose that at a certain point, after adding a baby , let's say $uv$, we can't pick any non-red segment and paint it, this means that the segment $vr$ is already red, where $ur$ is an initial edge, this means that there exists a vertex $t$ for which $vt$ is an initial edge and $rt$ is a baby, but this means that segment $ut$ is also already painted in red, which means that there is an initial edge different from $ur$ and $vt$ which is adjacent to either $u$ or $t$, but this is impossible. Note that the two endpoints of a red segment form a fat pair, and also note that we have painted exactly $k-1008$ segments in red, thus the lemma is proven. Back to the problem: We prove that the minimum average is $2-\frac{1}{2017}$. To show this, first of all label all the edges with $2$, now start re-labelling some with $1$, suppose that we have re-labelled $m$ edges, now from lemma we have that we are required to re-label from $2$ to $3$ at least $m-1008$ edges, which implies that the minimum sum of the labels that we can achieve is $\dbinom{2017}{2}-1008$, and hence the conclusion.

v_Enhance wrote: Official Solution: In general, the answer for $2m+1$ is $2 - \frac{1}{2m+1}$. We prove the lower bound by induction on $m$: assume some edge $vw$ is labeled $1$. Then we delete it, noting that edges touching $v$ and $w$ contribute a sum of at least $4 \cdot 2m = 8m$. Thus by induction hypothesis the total is at least \[ \binom{2m-1}{2} \left( 2 - \frac{1}{2m-1} \right) + 8m + 1 = \binom{2m+1}{2} \left( 2 - \frac{1}{2m+1} \right) \]as desired. Interestingly, there are (at least) two equality cases. One is to have all edges be $2$ except for $m$ disjoint edges, which have weight $1$. Another is to split the vertex set into two sets $A \cup B$ with $|A| = m$ and $|B| = m+1$, then weight all edges in $A \times B$ with $1$ and the remaining edges with $3$. Remark: In fact, given any equality case on $c$ vertices, one can generate one on $c+2$ vertices by two vertices $u$ and $v$, connected to the previous $c$ vertices with weight $2$, and then equipping $uv$ with weight $1$. I think this solution is slightly wrong. The edges would contribute $4(2m-1)$ since there are only $2m-1$ vertices when we delete the edge. Then, we compute \[ \binom{2m-1}{2} \left( 2 - \frac{1}{2m-1} \right) + 8m - \mathbf{3} = \binom{2m+1}{2} \left( 2 - \frac{1}{2m+1} \right), \]so fortunately the solution works out. This is a funny case of two wrongs luckily (or unluckily depending on how you look at it) making the solution not fundamentally wrong.

No induction Let $A$ be a set of all edges labeled with $1$ or $3$ such that for every edge in $A$ there exists other edge in $A$ such that numbers on these edges give sum $4$ and they have exactly one common vertice. In other words: take any vertice and if it has at least one edge $1$ and at least one edge $3$, then put into $A$ all these edges labeled with $1$ or $3$ connected to this vertice. Repeat this for all vertices and in final set we consider each element to appear only once (though edge could be connected to two vertices satisfying conditions). Now divide $A$ into $2$ element subsets of such that "in every subset we have two different edges from $A$ sharing one common vertice and they labels sum to $4$ (i.e. one is 1-labeled and second is 3-labeled)". There's one restriction: some edges in $A$ may be left if and only if they have no partner with which they could satisfy this "in every...". So actually the partition is a little bit random but is absolutely complete (i.e. after this process we are unable to make another required 2-element subset from so far unused elements of $A$). We can vanish all $1$'s and $3$'s written on edges from $2$-element required subsets and replace them with $2$'s. (In this place a reader is committed to do the casework and see that this operation doesn't harm the condition "any triangle has sum of labels at least $5.$") Now we are very satisfied to see that no vertice has two edges with $1$ and $3$. So if you did the casework you would see that these triangles with at least one edge $3$ are the following types $2+2+3,2+3+3$ or $3+3+3 $ (as there's no $1$-labeled edge) thus each $3-$labelled edge can be now modified into $2$-labeled and still our labeling is fine and sum of all labels decreased (or remained the same). At this moment all labels are equal to $1$ or $2$. Observe all $1$ edges are by above algorithm disjoint. By PIE there can be at most $1008$ disjoint edges. So the sum of all labels is now $2\cdot\left(\dbinom{2017}{2}-k\right)+1\cdot k\ge 2\cdot\left(\dbinom{2017}{2}-1008\right)+1\cdot 1008$. Limit is attainable: you make edges $\lbrace{1,2}\rbrace,\lbrace{3,4}\rbrace,...,\lbrace{2015,2016}\rbrace$ labeled with ones and the rest with twos. I'd like to know if you found any faults or doubts.

We claim the minimum is $2-1/2017$, achieved when we have a matching of $1008$ edges all $1$ and the rest of the edges at $2$. We prove by induction that for all odd $n\ge 3$, the minimum average of the $\binom{n}{2}$ labels in a $K_n$ is $2-1/n$. The case $n=3$ is trivial to verify. Now suppose the statement is true for $n-2$, and we want to show it for $n$. If there is no edge labeled $1$ in the $K_n$, then we are done as the average is already $\ge 2$. Otherwise, there is an edge $e=uv$ labeled $1$. For any edge $ux$ incident to it that is also a $1$, the edge $xv$ must be labeled $3$. Thus, the average of all edges incident to $e$ is $2$, so the average of all the edges is at least \[\frac{\left(2-\frac{1}{n-2}\right)\binom{n-2}{2}+2\cdot(n-2)+1}{\binom{n}{2}}=2-1/n,\]which completes the induction and the proof.

Perform the following operation. If there are two adjacent edges labelled 1 , the third edge completing the triangle will be labelled 3. Now change this 1,1,3 to 1,2,2 .Note that the average is unchanged. Now continue this process till there are no adjacent edges labelled 1. Now in this configuration we can easily see that the minimum occurs when there max allowed 1's that is 1008. And rest are 2. The corresponding average comes $2-\frac{1}{2017} $

The answer is $2-\tfrac{1}{2017}$. The following construction works: have every edge be weight $2$, except for $1008$ disjoint edges which have a weight of $1$. Hence it suffices to prove that a lower average is impossible. In fact, for $n=2m+1$, the answer is $2-\tfrac{1}{2m+1}$, with the construction eing the same.. I will prove this by induction on $m$. For $m=1$, we can manually check that having one edge with weight $1$ and two with weight $2$ works, giving an average of $2-\tfrac{1}{2(1)+1}$ which fits. Now suppose that $2m+1$ works, and consider $2m+3$. By averaging the average weight of each $K_{2m+1}$ subgraph of the $K_{2m+3}$, the answer must be at least $2-\tfrac{1}{2m+1}$. On the other hand, since we divide the integer edge weight sum by the number of edges, which is $(m+1)(2m+3)$, we can improve this answer by forcing the denominator to be a factor of $(m+1)(2m+3)$. Since $$2-\frac{m+2}{(m+1)(2m+3)}<2-\frac{1}{2m+1}<2-\frac{m+1}{(m+1)(2m+3)},$$this means that the average for $2m+3$ must be at least $2-\tfrac{m+1}{(m+1)(2m+3)}=2-\tfrac{1}{2m+3}$, completing the induction. $\blacksquare$

The answer is $2-\frac{1}{2017}.$ Construction is $1008$ disjoint edges have label $1$ and rest have label $2.$ We show the difference $D$ between the number of $1$ edges and the number of $3$ edges is at most $1008.$ Take any edge $AB$ with label $1$ if it exists. Note that for any vertex $C \ne A,B,$ the labels of $CA$ and $CB$ sum to $\ge 4.$ So just remove $A$ and $B,$ decreasing $D$ by $\le 1.$ Repeat until no edges with label $1$ remain, the end. $\blacksquare$

shinichiman wrote: Remark 1. If a triangle has $2$ of its edges both labelled $1$ then the other edge must be labelled $3$. There is a way to label $K_{2017}$ so that the average of labels of edges $T$ is minimum. In such labelling, consider edges $BC$ so $BC$ is labelled $3$. Consider all triangles $ABC$ so $CA,CB$ are both labelled $1$. If we change the labels of edges of $\triangle ABC$ from $1,1,3$ to $1,2,2$ ($BC$ is changed to $2$) then the average of labels $T$ remains the same and is still minimum. We do the same for all triangles $XBC$ with $XB,XC$ labelled $1$ then move on to other edges like $BC$ whose original label is $3$. After this, we obtain a new label $\mathcal{T}$ for $K_{2017}$ so that no edge is labelled $3$ and the average of labels $T$ is still minimum. Since no edge is labelled $3$ in this configuration $\mathcal{T}$ so according to remark 1, there doesn't exist two edges sharing same endpoint and are both labelled $1$. This follows, number of edges labelled $1$ is at most $\frac{2016}{2}=1008$, the remaining edges are labelled $2$. Thus, the minimum average of labels is $$T= \frac{1}{ \binom{2017}{2}} \left[ 2 \cdot \left( \binom{2017}{2}-1008 \right)+1008 \right]= 2- \frac{1008}{\binom{2017}{2}}=2-\frac{1}{2017}.$$Construction: Consider $2017$ vertices $A_1, \ldots, A_{2017}$ with $A_1A_2,A_3A_4, \ldots, A_{2015}A_{2016}$ are labelled $1$. The remaining edges are labelled $2$. This solution is absolutely wrong, how do you change 1 1 3 into 1 2 2, you haven't any proof about that is right

Denote respectively by $E_1$, $E_2$ and $E_3$ the set of edges that are labeled $1$,$2$ and $3$. Obviously $|E_1|+|E_2|+|E_3|={2017 \choose 2}$. We claim that $|E_3|\geq |E_1|-1008$. Lemma [ Friendship paradox: On average your friends are more popular than you ]: Let $H=(V_0,E_0)$ be a simple graph. For each $u\in V_0$, define $a(u)=\frac{1}{\deg u}\sum\limits_{w\in N(u)}\deg w$ to be the average degree of the neighbors of $u$. Then $$\sum\limits_{u\in V_0}a(u) \geq \sum\limits_{u \in V_0}\deg u$$Proof of the lemma: \begin{align*} \sum\limits_{u\in V_0}a(u)&=\sum\limits_{u\in V_0}\sum\limits_{v\in N(u)}\frac{\deg v}{\deg u} \\ &=\sum\limits_{uv\in E_0} \frac{\deg u}{\deg v} + \frac{\deg v}{\deg u} \\ &\geq \sum\limits_{uv\in E_0} 2 \\ &=2|E_0| \\ &=\sum\limits_{u\in V_0}\deg u \end{align*}Hence the lemma. $\blacksquare$ Consider the subgraph $G=(V,E_1)$. Notice that because every triangle has sum of labels at least $5$, if $xy\in E_1$ and $xw\in E_1$, then $yw\in E_3$. Therefore \begin{align*} \sum\limits_{u\in V} \deg_{E_3}u&\geq \sum\limits_{u\in V}|N(N(u))|-1 \\ &\geq \sum\limits_{u\in V}\max_{w\in N(u)}\deg w-1 \\ &\geq \sum\limits_{u\in V}a(u)-1 \\ &\geq \sum\limits_{u\in V}\deg u -2017 \end{align*}Which gives us $2|E_3|\geq 2|E_1|-2017$, from here we conclude that$|E_3|\geq |E_1|-1008$. This shows that the average of the labels is at least $2-\frac{1008}{{2017\choose 2}}=\frac{4033}{2017}$.