This problem was created by federico Ardila, Colombian IMO team leader an exmember of the IMO AB.

This problem follows easy by induction. In a) is easy to guess that the answer is n-1, but guess the answer in b) is practicaly imposible. In b) we can get: If f(n) is the number of labellings 2f(n)=∑ [C(n-1;a)C(n-1;b)f(a)f(b)] for a+b=n when C(n-1;i) is the binomial coeficient There is some method to get the value of f(a) ? There is other solution to this problem or the only solution is guess the answer and prove by induction?

I haven't checked what you've done, but I suspect it can be done by considering the generating function $F(x) = \sum_{n \geq 1} \frac {f(n)x^n}{n!(n - 1)!}$. (Both the form of the recursion and answer indicate that this, or something very similar, will work.) Then the expression you've written is very close to a convolution (i.e. the product $F(x)\cdot F(x)$). Also, LaTeX is enabled on this forum, and it would be much easier to read what you write if you use it. (See e.g. the link in the previous sentence or http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690.)

m.candales wrote: In b) we can get: If f(n) is the number of labellings 2f(n)=∑ [C(n-1;a)C(n-1;b)f(a)f(b)] for a+b=n when C(n-1;i) is the binomial coeficient This is slightly off... consider a vertex $V$ with $k\ge2$ of its edges labeled $n-1$, which clearly must exist since some triangle must have two sides labeled $r=n-1$. Let the $k$ vertices connected to $V$ be group $A$ and the other $n-k$ vertices (including $V$) be group $B$. It's easy to check that all edges between $A$ and $B$ must be labeled $n-1$, and all other edges are labeled at most $n-2$. By part (a), group $A$ has at most $k-1$ different labels and group $B$ has at most $n-k-1$ labels. Hence to get the labels from $1$ to $n-1$ in $A\cup B$, we must choose $k-1$ labels from $\{1,2,\ldots,n-2\}$ to be the labels in group $A$, so the remaining $n-k-1$ will be those in group $B$. Thus we have the recursion $$\begin{align*} 2f(n) &= \sum_{k=1}^{n-1}\binom{n}{k}\binom{n-2}{k-1}f(k)f(n-k)\\ &= n!(n-2)!\sum_{k=1}^{n-1}\left(\frac{f(k)}{k!(k-1)!}\right)\left(\frac{f(n-k)}{(n-k)!(n-k-1)!}\right). \end{align*}$$ After this if we let $f(x)=x!(x-1)!g(x)$ then we have $$2(n-1)g(n)=\sum_{k=1}^{n-1}g(k)g(n-k).$$ From here it's pretty easy to guess the answer after a few small cases (this is basically what JBL had...).

The polygon doesn't matter, it is a graph theory problem. To distinguish, the vertices have numbers ($n$ vertices numbered $1$ through $n$) and the edges have "colors" ($r$ colors, from $1$ to $r$). For part (a), the easy part: Suppose the answer is $R(n)$. Take any edge with color $r$. Say this edge is $AB$. It is easy to see that for any other vertex $C$, exactly one of $CA$ and $CB$ has color $r$. Call $S_A$ the set of vertices $C$ such that $CA$ is color $r$, and $S_B$ the analogous set. It is easy to see $\{1,...,n\} = S_A \cup S_B$ is a partition. Suppose $|S_A|=a$, $|S_B|=b$. Clearly $a+b=n$. Also, $R(n)=R(a)+R(b)+1$. From induction it is easy to see $R(n)=n-1$. Now for the difficult part, part (b). Here is the idea. In the original graph, suppose we draw a circle/oval around the whole graph. Then, we draw a circle/oval around $S_A$ and another one around $S_B$. Clearly $S_A$ is also partitioned into two "smaller" graphs. Draw a circle/oval around each of these. Do this again and again until you are finished, and each vertex has a circle drawn around it, and every circle is "paired" with one other circle, both inside a bigger circle. We want to count the number of possible final drawings. But what if we draw them in reverse? First draw a circle around each vertex. Then, draw a circle that contains exactly two circles (in this case, these smaller circles will have only a vertex inside). Then draw a circle that contains two circles. Then draw a circle that contains two circles. Etcetera... At the end, we clearly have drawn $2n-1$ circles in total. Now, take the moment when we draw the circles around each vertex. After the moment, we will label the first circle we draw with a $1$. We will label the second circle we draw with a $2$. Etcetera... Then we will label the last circle we draw (the one around the entire graph) with $n-1$. The trick is that, if a circle is labeled $x$, then the graph inside the circle will contain only edges with color $\le x$, and the only edges with color $x$ will be edges between vertices from one of the circle's "sub-circles" to the other "sub-circle" (remember each circle has two sub-circles). For example, the biggest circle is labeled $n-1$, and the edges labeled $n-1$ go from $S_A$ (a subcircle) to $S_B$ (another subcircle). Therefore, the process of drawing circles (the order is important!!!) completely determines the final configuration of colors. Now, say the answer for part (b) is $B(n)$. Then, draw the first $n$ circles (around the vertices), and then draw the $n+1$-th circle. There are ${n}\choose{2}$ ways of doing this. Then, we can consider this $n+1$-th circle as normal circle (a circle that only has one vertex inside), and then proceed as if we only had $n-1$ vertices, pretending like this $n+1$-th circle didn't have two vertices inside it. Then, $B(n) =$ ${n}\choose{2}$$B(n-1)$. From this, it is very easy to conclude $B(n)=\frac{n!(n-1)!}{2^{n-1}}$. This is a really beautiful and simple problem in my opinion.

Excellent problem. Note that we may simply let the regular polygon be a complete graph on $n$ vertices; let the vertices be $A_1,A_2,\cdots, A_n.$ Let $f(A_iA_j)$ return the label of the edge connecting $A_i$ and $A_j.$ a) We claim that $r=n-1\ \forall\ n.$ First, we show that we cannot have $r\geq n$ for any $n.$ Assume this is true for $n=3,4,\cdots, k-1.$ Assume for the sake of contradiction that it is also possible for $n=k.$ Then by the first restriction, there must exist an edge with label $k$, WLOG let it be $A_{k-1}A_k.$ Obviously the claim holds for $n=3.$ Then for $1\leq i\leq k-2,$ exactly one of $j\in\{k-1,k\}$ must satisfy $f(A_iA_j)=k$ by the second condition. Let $X_1,X_2$ be the set of indices such that $j=k,k-1$ respectively. Let $x_1=|X_1|,x_2=|X_2|$ and WLOG $x_1\geq x_2.$ Case 1: $x_2=0.$ Then $f(A_{k-1}A_i)\neq k\ \forall\ i,$ and no two $i,j\in X_1$ can have $f(A_iA_j)=k$ without violating the second condition (we get a triangle with equal labels on all sides). Hence we may ignore $A_k,$ since all other edges (which aren't connected to $A_k$ ) must have label less than $k.$ Hence we must distribute labels from $1,2,\cdots, k-1$ to the remaining edges formed by $A_1,A_2,\cdots, A_{k-1},$ but this is impossible by the induction hypothesis. Case 2: $x_2\neq 0.$ Claim: If this case is doable, it is always doable by letting $f(A_iA_j)=k$ for all $i\in X_1,j\in X_2.$ Proof: This is a very natural claim. Note that since no edge with both vertices in one of $X_1,X_2$ can have label $k.$ Hence by replacing any edge between the two sets with label not $k,$ we can replace the label with $k$ without causing a contradiction (no triangles are formed, and the other conditions are easy to check). Now it suffices to label $X_1\cup \{n-1\}$ and $X_2\cup \{n\},$ but each of these can give us less than $x_1,$ $x_2$ colors, meaning their union gives us less than $n$ colors. Hence we may conclude $r<n.$ We inductively construct a graph for $r=n-1.$ For $k=3,$ start with a triangle $A_1A_2A_3$ with $f(A_1A_2)=f(A_2A_3)=3, f(A_3A_1)=1.$ Then we can use induction to show that the perimeter of a valid configuration with $k-1$ vertices has labels $1,2,3,\cdots,k-2,k-1,k-1.$ Now increment the label of every edge in the initial config; this gives us every label in $\{2,k+1\}$ by induction hypothesis. Then if the points are indexed so that $f(A_1A_2)=2,f(A_2A_3)=3,\cdots, f(A_{n-2}A_{n-1})=k-1, f(A_{n-1}A_n)=f(A_nA_1)=k,$ let $f(A_{k+1}A_1)=1,f(A_{k+1}A_k)=2,f(A_{k+1}A_{k-1})=3,$ etc. It is easy to verify that this is indeed valid, although the details are quite tedious. b) Intuitively, it should be obvious that each valid configuration should be unique up to symmetry. Indeed, we claim that there can only be $1$ edge with label $1.$ Assume otherwise; let a valid $n$-graph have $AB$ and $CD$ with label $1.$ (we cannot have $f(AB)=1$ and $f(AC)=1$ without violating the second condition). Then removing point $A$ gives a valid configuration with $n-1$ vertices, since the first condition is obviously satisfied (If $f(AX)=f(BX)\ \forall\ X$) and the second follows quite easily. But this gives a valid configuration with $n-1$ vertices with $r=n-1,$ contradicting the result of a). Now if $g(x)$ is the number of ways to label with $x$ vertices, the proof of the above claim shows that there exists a bijection between each valid $x$-graph with $f(A_iA_j)=1$ and a valid $x-1$-graph, i.e. $g(x)=\binom{x}{2}g(x-1)$ since there are $\binom{x}{2}$ ways to choose the side with label $1.$ Hence by induction, it follows that $\boxed{g(x)=\dfrac{x!(x-1)!}{2^{x-1}}}.$

Very good problem with a lot of solutions quite original for me ! I don't understand how so many people thought about generating function. Someone could explain the motivation ? Here's my solution. We'll call "valid graph" a graph labelled in the conditions of the problem. a) We go by induction to show that $r = n-1$ is the maximum. First for the construction : The base case is trivial. Assume you have a valid graph for $n$ vertices with $n-1$ labels. Add one vertex $V$, then label with $n$ all edges going from V. This graph is valid and we're done. Now for the upper bound we'll go by contradiction. First, note that if we start with a valid graph and we remove one vertex and its adjacent edges, then we have a new valid graph (considering thati f you have removed a label, you just have to substract $1$ to all labels above the one removed). Moreover, if we remove a vertex then we remove at most one label in the graph. Indeed, consider $3$ vertices A, B and V and assume labels VA and VB are distincts. If we remove one vertex V, then the triangle VAB we'll use only 2 labels, so if you remove V you can't remove from the graphs yhr two labels on VA and VB. Then if we remove the point V and its edges, we can remove at most one label in the graph. Suppose we start with a valid graph with $r$ labels, where $r$ is strictly more than $n-1$. Remove one by one vertices and its edges. We remove at most one label each time. Then in the end, when we have just 3 vertices, we have at least 3 different labels which is clearly absurd. b) From the observations above, we know that when we remove one vertex we must remove exactly one label on the graph. Lemma : In a valid graph, there are $i$ segments label $i$. Proof : By induction, assume it's true for n vertices. Add one vertex $V$, then you must label one edge with $n$ (otherwise the graph is not maximal). Let A, B two other vertices. Assume VA is not labelized by $n$ and VB is. Then VAB doesn't fit the conditions. So all labels from V are $n$, and there are $n$ edges from V so we're done. Let $f(n)$ the number of ways to label a complete graph of n vertices. First we choose an edge, we have $\binom{n}{2}$ choices. Say we choose AB and we label it with $r=n-1$. WLOG, say all edges from A are $r$. There are $n-1$ edges from A, so no more edges we'll be label $r$ in the graph. Then we're left with a complete graph of $n-1$ edges to label. So we have the relation $f(n) = \binom{n}{2} f(n-1)$. From here, the result follow easily.

Nice problem! The main idea is that the problem is actually rigid and understanding the condition (2) takes priority over trying to solve either parts. (I had to peak at the answer at the end though, in order to get that pesky gen func correct.) Pentakratie wrote: Let $n\geq 3$ be a fixed integer. Each side and each diagonal of a regular $n$-gon is labelled with a number from the set $\left\{1;\;2;\;...;\;r\right\}$ in a way such that the following two conditions are fulfilled: 1. Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label. 2. In each triangle formed by three vertices of the $n$-gon, two of the sides are labelled with the same number, and this number is greater than the label of the third side. (a) Find the maximal $r$ for which such a labelling is possible. (b) Harder version (IMO Shortlist 2005): For this maximal value of $r$, how many such labellings are there? Proposed by Federico Ardila, Colombia The regular $n$-gon phrasing is not required since we are working on a $K_n$. Call a colouring of type (2) to be popular. Now $r=r(n)$ denotes the maximum number of colours we can employ to make a colouring popular. Part (a): We claim by induction on $n \ge 3$ that $r(n)=n-1$. For construction, simply make a linear ordering of the vertices and colour them accordingly by the number of the larger vertex. For bound, we provide the main claim (which will also find a use in part (b)): Lemma. It is possible to partition $K_n$ into two disjoint subgraphs $A \cup B$ such that all edges with ends across $A$ and $B$ have the colour $r$. (Proof) Pick an edge $uv$ with colour $r$. For any vertex $w \not \in \{u, v\}$ we obtain by (2) that exactly one of the edges $\{\overline{uw}, \overline{vw}\}$ is coloured by $r$. Now set $A=\{u\} \cup \{w: \overline{vw} \, \text{is coloured} \, r\}$ and $B=\{v\} \cup \{w: \overline{uw} \, \text{is coloured} \, r\}$. Clearly, this partition works. $\blacksquare$ Now we see that $r(n) \le r(|A|)+r(|B|)+1=|A|+|B|-1=n-1$ proving part (a). Part (b): Notice that equality occurs in the previous line. Hence the two subdivisions are in fact partitioned according to both (1) and (2). Let $|A|=k$ and $|B|=n-k$ and let $f(n)$ be the number of colourings for some $n \ge 3$. Then we have $\binom{n}{k}$ ways to pick $A$ (this fixes $B$), one choice for the colour linking $A$ and $B$, $(n-1)$ colours to use; and $\binom{n-2}{k-1}$ choices for choosing the colours we'll use on $A$. Thus, we see that $$2f(n)=\sum^{n-1}_{k=1} \binom{n}{k}\binom{n-2}{k-1}f(k)f(n-k)$$ since we can also swap $A$ and $B$. Now suppose $g(n) \overset{\text{def}}{:=} \tfrac{f(n)}{n!(n-1)!}$ so we obtain the recursion $$2(n-1)g(n)=\sum^{n-1}_{k=1} g(k)g(n-k)$$ which on solving alongside base cases shows $g(n)=\tfrac{1}{2^{n-1}}$ proving part (b).

We'll solve the problem for all $n\ge 1$. We claim the maximal value of $r$ is $n-1$, and the number of ways to color the edges with $r=n-1$ colors is $f(n)$, which is the unique function such that $f(1)=1$ and $$f(n)=\frac{1}{2}\sum_{a=1}^{n-1}\binom{n}{a}\binom{n-2}{a-1}f(a)f(n-a),$$ where we'll find a closed form for $f(n)$ later. The proof proceeds by induction on $n$. The base case of $n=1$ is obvious, since we can't have $r\ge 1$ (since there are no edges and each color needs to be used at least once). Now suppose the result is true for all $m<n$, and we're faced with $K_n$ to color with $r$ colors. Suppose we're given a coloring. Let $G$ be the graph with all the edges colored with $r$ edges removed. We claim that $G$ is the disjoint union of $K_a$ and $K_{n-a}$ for some $1\le a\le n-1$. If $n=2$, then the result is obvious since there is only one coloring, which is coloring the single edge by the color $1$. So suppose $n\ge 3$. Suppose $H$ is a connected component of $G$. We claim that $H$ is a complete graph. Indeed, for any two vertices $x,y\in H$, consider the shortest path connecting them. If the path is not a single edge, then looking at two consecutive edges in the path shows that there are three vertices $a$, $b$, and $c$ in a path with edges $\{ab,bc\}$, but not $ac$. Thus, the edge $ac$ in the original $K_n$ is $r$, but neither of $ab$ or $bc$ are $r$, which is a contradiction to the condition of the problem. Therefore, $x$ and $y$ are connected by a single edge, so $H$ is complete. Now, suppose $G$ has at least $3$ connected components. Pick vertices $a$, $b$, and $c$ all from different connected components. We see that all the edges $ab$, $bc$, and $ca$ are missing from $G$, so in the original $K_n$, they are colored $r$, so we have a triangle with all the same color, a contradiction. Therefore, $G$ has at most $2$ connected components. If $G$ has one connected component, then the color $r$ is never used, which can't be. If $G$ has $0$ connected components, then all edges are colored $r$, which is a contradiction since there is a monochromatic triangle. Therefore, $G$ is the disjoint union of $K_a$ and $K_{n-a}$ for some $1\le a\le n-1$. Conversely, any valid coloring on $K_a$ and $K_{n-a}$, and coloring all the edges between the two $r$, which is not in the set of colors already used, is a valid coloring of $K_n$. By the inductive hypothesis, $K_a$ has at most $a-1$ colors and $K_{n-a}$ has at most $n-a-1$. The color $r$ has to be a new color to these $n-2$ colors, so $K_n$ can have at most $n-1$ colors, as desired. Now, we'll show the number ways to color the graph with $r=n-1$ is $f(n)$. There are $\binom{n}{a}$ ways to pick a group of $a$ vertices, and there are $\binom{n-2}{a-2}$ ways to pick the set of colors it gets. This uniquely determines the other $n-a$ vertices and their colors, so the total number of ways to do the coloring in this case $$\binom{n}{a}\binom{n-2}{a-1}f(a)f(n-a).$$ However, the case $a$ and $n-a$, so the total number of colorings is $$\frac{1}{2}\sum_{a=1}^{n-1}\binom{n}{a}\binom{n-2}{a-1}f(a)f(n-a)=f(n),$$ as desired. Now to the task of solving the recursion for $f(n)$. Expanding out the binomial coefficients, we see that the substitution $g(n)=\frac{f(n)}{n!(n-1)!}$ kills of most of the factorials. The new recursion is $g(1)=1$ and $$g(n)=\frac{1}{2(n-1)}\sum_{a=1}^{n-1}g(a)g(n-a).$$ It is easy to see that $g(n)=2^{1-n}$ satisfies this recursion, so we have $f(n)=\boxed{\frac{n!(n-1)!}{2^{n-1}}}$, completing the solution.

I claim that $r=n-1$, and we get $\frac{n!(n-1)!}{2^{n-1}}$ labelings with this value. Suppose that we have a labeling with maximal number of labelings, and consider the graph, $G$, formed by edges with label $r(n)$. Claim: $G$ is complete bipartite. Proof: For any three points in $G$, we must have exactly $2$ or $0$ edges between them in order to satisfy condition 2. In particular, $G$ is triangle free. Now, consider an odd cycle of minimum length (of course, $\ge 5$). If we choose a set of $3$ points such that $2$ of them are neighbors, and the 3rd one is adjacent to neither, this set of $3$ points has only $1$ edge on the cycle, so there must be an edge in the cycle, which divides it into two different cycles. One of these is a smaller odd cycle, so we have a contradiction. Thus, $G$ has no odd cycles, and is bipartite. Now, if our two parts are $X$, $Y$, and there are vertices $x\in X$, $y,y'\in Y$ such that $xy$ is an edge, but not $xy'$, then we get a contradiction since this triplet has exactly 1 edge. So, if a vertex has one edge, it connects to all points in the other part, and we can use this to generate all edges in the graph. So, $G$ is complete. If $G$ is a bipartite graph splitting our $n$ points into two groups of $k$ and $n-k$, note that each group can be labeled separately. Thus, $r(n)=\max_{1\le k < n}(r(k)+r(n-k)+1)$, and a quick induction shows $r(n)=n-1$ as desired. Suppose the number of labelings is $L_n$. Casework on $k$ gives $$L_n=\frac{1}{2}\sum_{k=1}^{n-1}\binom{n}{k}\binom{n-2}{k-1}L_kL_{n-k}$$ where $\binom{n}{k}$ chooses the groups, and $\binom{n-2}{k-1}$ chooses which labels to assign to which group. We show that $L_n=\frac{n!(n-1)!}{2^{n-1}}$ through induction. The base case is trivial, and note that $$\binom{n}{k}\binom{n-2}{k-1}L_kL_{n-k}=\frac{n!(n-2)!}{k!(n-k)!(k-1)!(n-k-1)!}\cdot\frac{k!(k-1)!(n-k)!(n-k-1)!}{2^{k-1}2^{n-k-1}}=\frac{n!(n-2)!}{2^{n-2}}$$ Thus, $$L_n=\frac{1}{2}\cdot\frac{n!(n-2)!}{2^{n-2}}\cdot(n-1)=\frac{n!(n-1)!}{2^{n-1}}$$ and the induction is complete.

The answers are $r=n-1$ and there are $\frac{n!(n-1)!}{2^{n-1}}$ labellings. Take a complete graph coloring interpretation. Call each number a color. Part (a) is known before. In fact, we will prove the following claim. Claim: Suppose that we color edges of $K_n$ with $n$ colors. Then there exists a "rainbow" triangle. (i.e. triangle whose edges have different colors.) Proof 1 (Induction). The base case $n=3$ is trivial. Now we prove $P(n)$ assuming $P(n-1)$. Pick a vertex $a$ and delete it. Suppose that we lose two colors. Then there exists vertices $b,c$ which $ab$ and $ac$ have the two color that we lose. Clearly $bc$ must have color different from $ab, ac$ so $\triangle abc$ is rainbow, contradiction. Thus we lose at most one color. By induction hypothesis, we are done. $\blacksquare$ Proof 2 (Extremal). There exists a rainbow cycle as we can pick $n$ edges with distinct color which must form a cycle. Take a minimal rainbow cycle $x_1x_2\hdots x_n$. We claim that $n=3$. Suppose not, then clearly either $x_1x_2x_3$ or $x_1x_3x_4\hdots x_n$ must be rainbow. Hence we get smaller rainbow cycle, contradiction. Hence we are done. $\blacksquare$ Now we move on to a harder part (b). First, we rearrange the inductive argument above which will give a structure for us to work on. For a vertex $v$, call a color $i$ $v$-original if deleting $v$ result in no edges with label $i$. We claim that Claim: For each vertex $a$, there exists exactly one $a$-original color. Proof: First, an original number must exists as if there are none, then deleting $a$ give a working coloring on $n-1$ vertices using $n-1$ distinct colors, contradiction. Now we prove that it is unique. Suppose that $i,j$ are $a$-original color. Then there exists vertices $b,c$ which $ab,ac$ have colors $i,j$ respectively. Clearly $bc$ cannot have color $i$ or $j$ (or it will violate originality). Hence $\triangle abc$ is rainbow, contradiction. $\blacksquare$ Now we are ready to present the main idea. Consider the following two claims. Claim: There is no subgraph of $k$ vertices with at most $k-2$ distinct colors. Proof: Start from that subgraph and keep adding vertex back to the original $K_n$. From the above claim, adding back one vertex gives exactly one new color. Therefore, eventually, we get exactly $n-2$ colors which is contradiction. $\blacksquare$ Claim: There exists exactly one edge colored $1$. Proof: Suppose that there are two edges colored one. We split into two cases. If $ab,ac$ are colored one, then obviously $bc$ cannot be colored properly. If $ab,cd$ are colored one, then it's easy to see that $ac,bd,ad,bc$ all have the same color, which is contradiction to above claim. Both cases leads to contradiction. $\blacksquare$ Now we are ready to do the recursion. Let $a_n$ denote the answer. Consider arbitrary $K_{n-1}$-coloring that works. We construct $K_n$-coloring as follows. Add all color on the $K_{n-1}$ by $1$. Pick a vertex $v$ on the $K_{n-1}$. There are $n-1$ ways to do this. Now consider a (to be colored) $K_n$. We pick one vertex, say $u$ and color the rest $n-1$ vertices according to the original $K_{n-1}$. There are $n$ ways to do this. For any vertices $x\ne u,v$, it's easy to see that $xu$ and $xv$ must be given the same color. Give color $1$ to $uv$. Reversing this procedure gives two corresponding $K_{n-1}$-coloring (depending on the ordering of $u,v$). Thus $$2a_n = n(n-1)a_{n-1} \stackrel{\text{induction}}{\implies} a_n = \frac{n!(n-1)!}{2^{n-1}}$$ hence we are done.

Solved with Th3Numb3rThr33. The answers are $r=n-1$ and $\dfrac{n!(n-1)!}{2^{n-1}}$. We will prove these inductively. The base cases are clear. Solution to part (a). Say a family is a set of vertices such that the edge between any two vertices in the family is less than $r$. We say a family is egotistic if it is not a subset of another family. Note that if any vertex $v$ is connected to a vertex $u$ of a family, if $\overline{vu}$ is labeled less than $r$, then for all vertices $w$ of the egotistic family, $\overline{vw}$ cannot be labeled $r$; hence the family union $v$ is also a family, and hence the family is not egotistic. Thus we may split the vertices into $k$ egotistic families $F_1$, $\ldots$, $F_k$, where $|F_1|+\cdots+|F_k|=n$, and any two vertices from distinct egotistic families are connected by an edge with label $r$. (Here, $|F|$ is the number of vertices of $F$.) By the inductive hypothesis, family $F_i$ may have at most $|F_i|-1$ distinct labels. Hence the number of distinct labels in $K_n$ is at most $$1+\sum_{i=1}^k(|F_i|-1)=\left(\sum_{i=1}^k|F_i|\right)-(k-1)\le n-1,$$ as desired. Solution to part (b). Let $b_n$ be the answer. By part (a), for equality to hold, the edges of $K_n$ with label $n-1$ must form a complete bipartite graph. If the bipartite graph splits $K_n$ into graphs of size $i$ and $n-i$, we may choose the vertex sets in $\tbinom ni$ ways, and then we may split the colors in $\tbinom{n-2}{i-1}$ ways. Hence $$\begin{align*} b_n&=\frac12\sum_{i=1}^{n-1}\binom ni\binom{n-2}{i-1}b_ib_{n-i}.\\ &\stackrel{\text{I-H}}=\frac12\sum_{i=1}^{n-1}\frac{n!(n-2)!i!(i-1)!(n-i)!(n-i-1)!}{i!(n-i)!(i-1)!(n-i-1)!2^{i-1}2^{n-i-1}}\\ &=\frac12\sum_{i=1}^{n-1}\frac{n!(n-2)!}{2^{n-2}}\\ &=\frac{n!(n-1)!}{2^{n-1}}, \end{align*}$$ and we are done.

Solved with cosmicgenius. Part a). We claim that the maximal value of $r$ is $n-1$. The construction is easy. Choose a vertex $V_1$ and choose all $n-1$ edges from that vertex to be $n-1$. Then, we know the $\tbinom{n}{2} - (n-1) = \tbinom{n-1}{2}$ unassigned edges form $K_{n-1}$, and we just repeat. It is easy to see that this does indeed work. Our construction actually motivates our solution to part a), which we will do with strong induction. Our base cases of $n = 3, 4$ are easy; clearly, the $r$-values for them are $2$ and $3$, respectively. For the inductive step, suppose that for all $i < k$, the complete graph $K_i$ has maximal $r$ value $i-1$. Claim: For all $n$, $K_n$ can be partitioned into two disjoint complete graphs $K_i, K_j$ such that all edges connecting a vertex from $K_i$ and a vertex from $K_j$ are labeled $r_n$. Proof: We actually construct; By problem statement, there exists an edge $AB$ of $K_n$ for which $AB$ is labeled $r_n$. Furthermore, we also know that all edges having one of either $A$ or $B$ but not both as a vertex must also be labeled $r_n$. Now, consider sets $S_1$ and $S_2$ of vertices $V$ for which $VA$ is labeled $r_n$ iff $V \in S_1$ and $VB$ is labeled $r$ iff $V \in S_2$. Clearly $S_1, S_2$ must be disjoint; if not, then there exists a triangle with all three edges labeled $r_n$. Now, let $T_1 = \{B\} \cup S_1$ and $T_2 = \{A\} \cup S_2$, which must be disjoint. If we just let $\{T_1, T_2\} = \{K_i, K_j\}$ then we are done. $\square$ Back to part a). Note that $r_k \leq r_i + r_j + 1$ where there is an inequality sign due to possible overlaps of edges in $K_i, K_j$ having the same label, and/or edges in $K_i, K_j$ having label $r_k$. By the inductive hypothesis, since $i, j < k$, $\{r_i, r_j\} = \{i-1, j-1\}$ hence $$r_k \leq i-1 + j-1 + 1 = k-1$$ as desired, completing our induction. $\blacksquare$ Part b). We may assume the result in part a), that $r_n = n-1$. Now we just need all the assumed inequalities in the previous part to hold as equality. The edges in $K_i, K_j$ (the sub-complete graphs of $K_n$) must not have labeling $r_n = n-1$ and there must not exist edges $E_1 \in K_i, E_2 \in K_j$ for which $E_1, E_2$ have the same label. Let $S(n)$ denote the answer for $n$. We can sum based on $|K_i|$ (then $|K_j|$ is determined). Suppose $|K_i| = k$. Then there are $\tbinom{n}{k}$ ways to choose $K_i$, and $K_j$ is just the rest. There is one way to choose the labeling of the edges connecting one vertex from each of $K_i, K_j$, which are to be labeled $r_n = n-1$. Among the remaining $(n-1) - 1 = n-2$ possible labels, there are $\tbinom{n-2}{k-1}$ ways to choose what labels we will use in $K_i$, and the remaining labels will be used in $K_j$. Then, there are $S(k)$ and $S(n-k)$ ways to sort out $K_i$ and $K_j$ given the edge labels they'll be using. Hence, we arrive at the recurrence $$S(n) = \frac12\sum_{k=1}^{n-1} \binom{n}{k}\binom{n-2}{k-1}S(k)S(n-k)$$ which can be easily simplified with the substitution $T(m) = \tfrac{s(m)}{m!(m-1)!}$ which gives the new recursion $$T(n) = \frac{1}{2(n-1)}\sum_{k=1}^{n-1} T(k)T(n-k)$$ where $T(1) = 1$. Induction on this thing is easier; We see that $T(n) = \tfrac{1}{2^{n-1}}$ for all positive integers $n$. Hence, our closed form for $S(n)$ is $$S(n) = \boxed{\frac{n!(n-1)!}{2^{n-1}}}$$ completing part b) and therefore the problem. $\blacksquare$

Solved with dantaxyz. The key is to focus on the edges labeled $r$. Let $G_r$ be the subgraph of $r$-edges. Let $G'=K_n\setminus G_r$ be the remaining graph when we remove all the $r$-edges. Claim 1: $G_r$ is bipartite. Proof: Note that every triple of vertices in $G_r$ has either 0 or 2 edges between them. There are no triangles in $G_r$. We claim there is no cycle of length $\ge 5$, which would prove that there are no odd cycles, finishing. Suppose there is, and consider the minimal odd cycle of $G_r$ (which has length $\ge 5$); label the vertices in it $v_i$. Consider the triple $(v_1,v_2,v_4)$. Since the cycle is minimal, there is no edge $v_1v_4$ or $v_2v_4$; this would induce either a smaller odd cycle or a triangle. Hence $(v_1,v_2,v_4)$ has exactly 1 edge in it, contradiction. Therefore, there are no odd cycles in $G_r$. $\square$ Claim 2: $G'$ is the disjoint union of 2 cliques: $K_a,K_{n-a}$, for some $1\le a \le n-1$. Proof: Note that every triple of vertices in $G'$ has exactly 1 or 3 edges. Consider a connected component of $G'$, and two arbitrary vertices $u,v$ in it. Suppose $uv$ is not an edge, then consider the minimal path $u\to w_1\to w_2\cdots\to v$ (possibly $w_2=v$). Since the path is minimal, there is no edge $uw_2$. So in the triple $(u,w_1,w_2)$, there are exactly 2 edges, contradiction. Therefore, $uv$ is an edge for any $u,v$ in the connected component, which means that any connected component of $G'$ is complete. But since $G_r$ was bipartite, its complement in a complete graph, $G'$, can have at most 2 connected components. Therefore, $G'$ is the union of two disjoint cliques, as claimed. $\square$ Part (a). Note that by Claim 2, it follows that $G_r$ is actually the complete bipartite graph $K_{a,n-a}$. Let $r(n)$ be the maximal $r$ in $K_n$. We claim $r(n)=n-1$. This is constructed inductively: choose a vertex and label all edges that contain it with $n-1$, and then induct down onto the $K_{n-1}$. We induct on $n$, $n=3$ trivial. By induction, we can use at most $a-1$ colors for $K_a$ and $n-a-1$ for $K_{n-a}$, and we use 1 label for $G_r$, for a total of $(a-1)+(n-a-1)+1=n-1$, finishing the induction. Part (b). We count the number of ways, using the structure we found. Let $f(n)$ be the answer for $K_n$. There are $\tbinom{n}{a}$ ways to pick the $K_a$. There are $n-2$ colors not including $r(n)=n-1$, and we assign $a-1$ of them to $K_a$, hence there are $\tbinom{n-2}{a-1}$ ways. The other colors go to $K_{n-a}$. But $a,n-a$ are symmetric. Overall, we have $$f(n) = \frac12 \sum_{a=1}^{n-1} \binom{n}{a} \binom{n-2}{a-1} f(a)f(n-a).$$ Substituting $g(n) = \tfrac{f(n)}{n!(n-1)!}$, we get $$2(n-1)g(n) = \sum_{a=1}^{n-1} g(a)g(n-a).$$ Notice that $g(n)=\tfrac{1}{2^{n-1}}$ satisfies this. Therefore, $f(n) = \tfrac{n!(n-1)!}{2^{n-1}}$ works, and is the answer.

Solved with me, myself, and I. The answer is $r=n-1$. The maximum can be achieved as follows; label the vertices $1,\dots,n$ and for any edge $(u,v)$ with corresponding labels $(i,j)$, label it $\max(i,j)-1$. This provides a construction. We will extract the number of equality cases later on through the induction step. Now, we induct to show that $n-1$ is the maximum. Note the result is trivial for the base cases of $n=1,2$. Induction Step: Take a labelling of edges for $K_n$ with $r$ different labels. Clearly, there exists an edge labeled $r$ with vertices $(u,v)$. Let $U$ be the set of vertices $w$ such that $(u,w)$ is not labelled $r$, including $u$. Define $V$ similarly. We claim that a) there are no edges between elements of $U$ labelled with $r$ and b) every edge between an element of $U$ and an element of $V$ is labelled $r$. In fact, (a) will follow from (b). First, observe that every element of $U$, $w$, must satisfy the property that $(v,w)$ is labelled $r$; if $w\ne u$, this is immediate by considering triangle $uvw$ and otherwise this follows by definition. A similar property holds for $V$. Now, consider vertices $w\in U,x\in V$. We claim $(w,x)$ is labelled $r$, which will show (b). If $w=u$ or $x=v$, we are done. Otherwise, consider triangle $uwx$. Now, consider two vertices of $U$, $w$ and $y$. Consider $vwy$ to see that the edge $(w,y)$ is not labelled $r$. As both $U$ and $V$ are nonempty, we now apply the inductive hypothesis to see that $K_n$ has been colored with at most $1+|U|-1+|V|-1=n-1$ colors, as desired. Now, we extract the number of equality cases. Let $f$ denote the number of equality cases and observe $f(1)=f(2)=1$. For any fixed $|U|$, there are $\binom{n}{|U|}$ ways to choose $U$, hence we extract $$f(n)=\frac{1}{2}\sum_{|U|=1}^{n-1} \binom{n}{|U|} \binom{n-2}{|U|-1}f(|U|)f(n-|U|)$$ by counting and halving to account for this sum double-counting symmetric possibilities. After applying the mathematical technique of searching for a sequence in OEIS and computing $f$ up to $f(6)$, we guess that $$f(n)=\frac{n!(n-1)!}{2^{n-1}}.$$ We now prove that this $f$ satisfies this recursion. It suffices to show $$\frac{n!(n-1)!}{2^{n-2}} = \sum_{i=1}^{n-1} \binom{n}{i}\binom{n-2}{i-1} \frac{i!(i-1)!}{2^{i-1}}\frac{(n-i)!(n-i-1)!}{2^{n-i-1}}.$$ After multiplying through by $2^{n-2}$, we see it suffices to show $$n!(n-1)! = \sum_{i=1}^{n-1} \frac{n!}{i!(n-i)!} \frac{(n-2)!}{(i-1)!(n-i-1)!} i!(i-1)!(n-i)!(n-i-1)! = \sum_{i=1}^{n-1} n!(n-2)!,$$ which is trivially true, so $f$ is what we claimed it was.

Weird, doesn't seem like anyone has posted this solution yet. We first claim that $r \le n-1$ by induction on $n$. Base case $n=3$ is clear. For the inductive step, consider all edges with minimal labels. Clearly these form disjoint cliques, and further if $v_1, \ldots, v_k$ are the vertices in such a clique, then for all $w \neq v_1, \ldots, v_k$, the labels on edges $wv_1, wv_2, \ldots, v_k$ are equal. Thus we may contract the vertices in each clique into a single vertex, leaving a graph on at most $n-1$ vertices colored with $r-1$ colors. By the inductive hypothesis, this implies $r-1 \le n-2 \implies r \le n-1$. For the second part, looking at our proof for the first part, we see it is tight only when there is precisely one edge with a minimal label at each step. If there are $i$ vertices, there are $\binom{i}{2}$ choices for this edge, For $n=3$ the answer is $3$, so the answer will be $$3\prod_{i = 4}^{n}\binom{i}{2} = 3\times \frac{n!(n-1)!}{2^{n-3} \times 12} = \frac{n!(n-1)!}{2^{n-1}}$$

Duck goes quack The maximal number of colours is $n -1$. We will prove this by inducktion. For our base case of $n = 3$, it's a triangle, and we can't have more than $3$ colours because it violates the second condition, so the maximal number of colours is $2$ which proves our base case. Now, assume for all $i < n$ the maximal number of colours is $i-1$; we will prove that for $K_{n}$ the number of colors is $n-1$. WLOG, let $u$ be a vertex such that one of it's edges is coloured with $r$ (maximal colour), and let $A$ be the set of vertices such that for each vertex $v\in A$, we have $uv$ is coloured with $r$. Let $B$ be the set of all other vertices besides $u$. Then, every edge between $U$ and $V$ must be coloured with $r$, because otherwise, if some edge $a\in A, b\in B$ where $ab\neq r$, since $ub\neq r$, those two colours must be the same and less than $r$ (due to maximality), contradicting our condition. Now, all the edges between vertices in $A$ can be coloured with at most $a-1$ colours, and similarly all the edges between vertices in $B$ can be coloured with at most $b-1$ colours. Next, if there existed more than one vertex $v$ such that $v\in B$ and $uv$ is not coloured with a colour found between the edges of set $B$, then let those two vertices be $v_{1}, v_{2}$, and consider $uv_{1}v_{2}$. It contains $3$ colours, a contradiction. Thus, the edges from $u$ to $B$ can contain at most one "new" colour, so the maximal number of colours is $a-1 + b-1 + 1 + 1 = n-1$. Finally, this is achievable through the following construction: Let $B$ be the empty set, so all edges from $u$ are coloured with $r$, and then we have a $K_{n-1}$ graph; colour this with $n-2$ colours via our inducktive hypothesis. This completes our inducktion. To find the number of labellings, let $f(n)$ denote the number of such labelings. It is clear that the construction we provided in the inducktive hypothesis categorizes all such constructions, since at least one edge must have the maximal edge, and everything else is determined. Then, if we let $A$ and $B$ be the two sets, with $u$ the same as the inducktive hypothesis, we have $\binom{n-1}{|A|}$ ways to choose the set $A$ (then set $B$ is determined), a total of $f(|A|)$ ways to colour the edges in set $A$, a total of $f(|B| + 1)$ ways to colour the edges in $B\cup u$ (since we also need to colour the edges from $u$ to $B$), and also $\binom{n-2}{a-1}$ ways to choose the colours we use for the edges of set $A$ (Then the colours for set $B$ are determined). Since there are $n$ possible choices of $u$, we have to multiply this by $n$, but since every vertex must contain an edge coloured with $n-1$, each labelling is overcounted $n$ times, so we must also divide by $n$. We can now formulate a summation for $f(n)$ based on $|A|$: $$f(n) = \sum_{a = 1}^{n-1}\binom{n-1}{a}\binom{n-2}{a-1}f(a)f(n-a)$$ with $f(1) = 1, f(2) = 1$. I claim $f(n) = \frac{n!(n-1)!}{2^{n-1}}$. We can prove this via inducktion. Our base case is $n = 1$, where we have $f(1) = 1 = \frac{1!0!}{1} = 1$. For our inducktive hypothesis, assume for all $a < n$ we have $f(a) = \frac{a!(a-1)!}{2^{a-1}}$. Then, $$f(n) = \sum_{a = 1}^{n-1}\binom{n-1}{a}\binom{n-2}{a-1}f(a)f(n-a)$$ $$= \sum_{a=1}^{n-1} \frac{(n-1)!}{a!(n-1-a)!}\cdot \frac{(n-2)!}{(a-1)!(n-1-a)!} \cdot \frac{a!(a-1)!}{2^{a-1}}\cdot \frac{(n-a)!(n-1-a)!}{2^{n-1-a}}$$ $$=\sum_{a=1}^{n-1}\frac{(n-1)!(n-2)!}{2^{n-2}} (n-a) = \frac{(n-1)!(n-2)!}{2^{n-2}} \sum_{a = 1}^{n-1}$$ $$= \frac{(n-1)!(n-2)!}{2^{n-2}}\cdot \frac{n(n-1)}{2} = \frac{n!(n-1)!}{2^{n-1}}$$ Our inducktion is complete, which proves the answer is $\frac{n!(n-1)!}{2^{n-1}}$

quack goes duck We claim the maximal value of $r$ is $r=n-1$. To prove this is maximal, numerate the vertices. Let $S_i$ be the number of distinct numbers in the edges of the first $i$ points. AFTSOC that we may end with $r=n$, then $S_1=0,S_n = n$. Thus, there exists some point $j$ such that $S_{j+1}\geq S_j+2$. Thus, there exists two points $A,B$ such that $P_{j+1}A$ and $P_{j+1}B$ are labelled with new numbers, which are also different from $AB$'s label, which is a contradiction so we have shown $r=n-1$ is maximal. We now count the number of labellings that achieve this. To do this we claim that Claim: Any graph of blue edges where each triangle must have either 0 or 2 blue edges must be of the form $K_{a,b}$ where $a+b=n$ Proof: We do this with induction. Note that the edges with value $n-1$ are the same as blue edges. For the base case, $n=2$ is solved because there must be an edge which is of the form $K_{1,1}$. This is our base case. For the inductive step, let $A,B$ be the two bipartite sections of the $K_n$'s coloring. Then, when we add a point $P$, note that for each $x\in A, y\in B$, there is an edge from $P$ to exactly one of $x,y$. Clearly, the only way this is satisfied is if $P$ is connected to all of either $A$ or $B$. So we're done. $\square$ By applying this claim, we have that the labels of value $n-1$ must be of the form $K_{a,n-a}$. The remaining subgraphs are also structurally identical to the original problem, so they each have at most $a-1$ and $n-a-1$ colors at max. This is a total of $(1)+(a-1)+(n-a-1)=n-1$. This is equality, so both $K_a$ and $K_{n-a}$ must be equality. Now, if we let $T_n$ be the number of ways to color a $K_n$ with $n-1$ colors, then we have $$T_n = \frac12 \sum_{i=1}^{n-1} \binom{n}{i} \cdot \binom{n-2}{i-1} T_i\cdot T_{n-i}$$ Claim: For all $n$, $$T_n = \frac{n!(n-1)!}{2^{n-1}}$$ Proof: We use strong induction. The base cases are $T_1=1, T_2=1$. For the inductive step, note that $$T_n = \frac12 \sum_{i=1}^{n-1} \frac{n!}{i!(n-1)!}\frac{(n-2)!}{(i-1)!(n-i-1)!}\frac{i!(i-1)!}{2^{i-1}}\frac{(n-i)!(n-i-1)!}{2^{n-i-1}}$$ $$= \frac{1}{2^{1+i-1+n-i-1}} \cdot \sum_{i=1}^{n-1} n! \cdot (n-2)! = \frac{n!(n-1)!}{2^{n-1}}$$ and we are done.$\blacksquare$

The maximal answer is $r=n-1$, and there are $\frac{n!(n-1)!}{2^{n-1}}$ possible labellings. To construct the maximum, first label the vertices $1,\ldots,n$, and then for an edge between $a$ and $b$ label it $\max(a,b)-1$. We now do parts (a) and (b) more or less concurrently, using strong induction (with base cases manually done). Let the labeled graph be $G$. Consider an edge $\overline{vw}$ which is labeled with $r$. Then for any $u \neq v,w$, exactly one of $\overline{uv}$ and $\overline{uw}$ is labeled with $r$ as well: if the first one holds, call $u$ \say{type 1}, and call it \say{type 2} otherwise. Now suppose $a,b$ are type 1 and type 2 respectively. Since $\triangle abv$ has an edge with label $r$ (namely $\overline{av}$), it follows that one of $\overline{ab}$ and $\overline{bv}$ also has label $r$. But $\overline{bv}$ doesn't have label $r$ by definition, so it must be $\overline{ab}$. Thus, the structure of $G$ is as such: the type 1 vertices and $u$ form $A$, the type 2 vertices and $v$ form $B$, such that $A \cup B=G$ and every edge within $A$ and $B$ is less than $r$. Further, every edge between $A$ and $B$ has label $r$ (including $\overline{vw}$, etc.). Suppose $|A|=x$ and $|B|=y$, so $x+y=n$ (note $x,y>0$, but they can equal $1$). By inductive hypothesis, we can use at most $x-1$ labels for $A$ and $y-1$ labels for $B$, so adding $r$, it follows that there are at most $n-1$ labels for $G$, proving part (a). We use the same setup for part (b). Note that equality only holds for part (a) if $A$ and $B$ don't share colors. Note that once we've chosen $A$ and $B$, the actual identities of vertices $v$ and $w$ doesn't matter. Thus, if we suppose that $|A|=k$, we have $\binom{n}{k}$ ways of choosing $A$ (determining $B$). Once we do this, there are $(n-1)-1$ (subtracting $r$) labels we can possibly use for $A$, of which we have to pick $k-1$, so there are $\binom{n-2}{k-1}$ ways to do this. Since $A$ and $B$ are indistinguishable though, we must divide by two. Thus, if $f(n)$ denotes the answer, we have the recursion $$f(n)=\frac{1}{2}\sum_{k=1}^{n-1} \binom{n}{k}\binom{n-2}{k-1}f(k)f(n-k).$$ By using strong inductive hypothesis (since $k,n-k<n$), this is equivalent to $$\begin{align*} f(n)&=\frac{1}{2}\sum_{k=1}^{n-1} \frac{n!}{k!(n-k)!}\cdot \frac{(n-2)!}{(k-1)!(n-k-1)!}\cdot \frac{k!(k-1)!}{2^{k-1}}\cdot \frac{(n-k)!(n-k-1)!}{2^{n-k-1}}\\ &=\sum_{k=1}^{n-1} \frac{n!(n-2)!}{2^{n-1}}=\frac{n!(n-2)!(n-1)}{2^{n-1}}=\frac{n!(n-1)!}{2^{n-1}} \end{align*}$$ as desired. $\blacksquare$

Absolutely amazing problem. The maximal value of $r$ is $n-1$, achieveable by a variety of constructions. Consider $r$ differently labelled edges; since no cycle of all distinct edges can exist in the graph (by induction), we find that all connected components formed by these edges must be trees. Therefore at least $r+1$ different nodes are in the graph, implying $r\le n-1$. Claim: By only considering edges labelled with $n-1$, we get a complete bipartite graph. Proof: Consider some vertex $v$ where it uses the label $n-1$ in one of the edges, and consider also the set $S$ of vertices which are connected to $v$ by such an edge. Clearly $S$ is one of the desired groups in the bipartite graph, so the claim is proven. Now we are almost done. Note by recursion we have $$2f(n)=\sum_{i=1}^{n-1}\binom{n}{i}\binom{n-2}{i-1}f(i)f(n-i)$$ where $f(n)$ is the answer for $n$. Now I claim that $f(n)=\displaystyle{\frac{n!(n-1)!}{2^{n-1}}}$. Since $f(1)=f(2)=1$ we can just induct; since each term in the summation is equal a simple calculation suffices. $\blacksquare$

The maximal $r$ for which the labelling is possible is $n-1$. We will show this using induction: clearly, when $n=3$, we can use two colors and we cannot use three. Therefore, the maximal $r$ is $2$. Suppose the maximal $r$ for $n=k$ is $k-1$. Then, let us add a point to make a $k+1$-gon. Clearly, we can achieve $r=k$ by simply making every single edge with this new point as an endpoint be labeled $k$. Assume for the sake of contradiction that we can label with $k+1$. Then, two edges with the new point as an endpoint must be labeled different. However, the edge that completes the triangle will be different from both, absurd. We will show that the subgraph of maximum labels is a complete bipartite graph encompassing every vertex: First, we will show that it is bipartite. Suppose it has an odd cycle. Pick any edge from $P$ to $Q$, then select the path from $P$ to $Q$ along the cycle that has even length. Then, we can easily show that this segment is less than or equal to $n-2$. Thus, every segment other than the cycle that connects two points from the cycle has a smaller label, absurd. Next, let the two components of the bipartite graph be $A$ and $B$. Let $P$ be from $A$ and $Q$ from $B$ such that $PQ$ has a small label. Then, if $R$ is from $A$ then $PR$ and $PQ$ both have labels smaller than $n-1$, so $QR$ also has a label smaller than $n-1$. Thus, there is no use even including $Q$ in the bipartition, so the graph is complete. Finally, assume that there are vertices that aren't included in the bipartition. That means that no edge emanating from these vertices may have label $n-1$. Clearly, this is false: let $P$ be one of these vertices and $Q$ and $R$ be on opposites sides of the bipartition. Then, $PQ$ or $QR$ must be at least $n-1$ since $QR$ is. Induction finishes.

Label the vertices of $K_n$ as $v_1, v_2, \ldots, v_n$. Part (a). The maximal $r$ is $n-1$, achievable by labeling for each $a \le n$ the edge $v_a \sim v_b$ with $a$ for all $b<a$. Now consider any configuration. We will show by strong induction that $r \le n-1$, where the base case $n=3$ is clear. Let $S$ be the set of the vertices that are an endpoint of the edges with label less than $r$. Consider the graph $G_S$ induced by $S$. Suppose that there exist vertices $x$ and $y$ of a single connected component of $G_S$ with $x \not\sim y$. Consider the path $\mathcal{P}=(x, f(x), f(f(x)), \ldots, y)$ of minimal length from $x$ to $y$. Then realize that the triplet $(x, f(x), f(f(x)))$ has exactly 2 edges, which is impossible per the labelling condition. Thus all connected components of $G_S$ are complete. Claim: $G_S$ has at most two connected components. Proof. We follow a proof similar to how we showed that $G_S$ is the disjoint union of multiple cliques. We will show that $K_n \setminus G_S$ has no cycles of length at least $5$, which is enough. Assume for contradiction that a cycle $\mathcal{C}=(x, f(x), f(f(x)), \ldots)$ of length at least $5$ exists. Then the triplet $(x, f(x), f^3(x))$ has exactly one edge, which is impossible by the labelling condition. The claim implies that $G_S=K_a \sqcup K_b$ for $a, b \ge 1$ such that $a+b=n$. By inductive hypothesis, at most $(a-1)+(b-1)=n-1$ distinct labels are used, so the inductive step is complete. Part (b). Let $a_n$ be the answer. The key is to do casework on the sets $\{a, b\}$ such that $G_S = K_a \sqcup K_b$. By the claim from part (a), these are all sets $\{a, b\}$ with $a, b \ge 1$ and $a+b=n$. WLOG $a \le b$. Then, we can split the vertices in $\tbinom{n}{a}$ ways and the labels in $\tbinom{n-2}{a-1}$ ways. This gives rise to the recurrence $$a_n = \frac{1}{2} \cdot \sum_{i=1}^{n-1}\binom{n}{i} \binom{n-2}{i-1}a_ia_{n-i}.$$ We can solve this using say, a generating function, and find that $a_n = \tfrac{n!(n-1)!}{2^{n-1}}$, which is the final answer.

We will show that the maximum $r$ is $n-1$ and there are $\frac{n!(n-1)!}{2^{n-1}}$ labelings. We will show this by induction. The base case $n=3$ is trivial. For the inductive step, first consider the graph excluding all edges labeled with $r.$ We can see that in this new graph, if $A$ is connected to $B$ and $B$ is connected to $C,$ then $A$ is also connected to $C.$ Thus, we can see that every connected component must be a complete graph, since if some points $A$ and $B$ are connected, then there must be some path $A-P_1-P_2-\dots-P_k-B,$ but by induction we can show that there is an edge between $A$ and $P_i$ for any $1 \le i \le k,$ so we get that there is an edge between $A$ and $B.$ If these connected components have $a_1,a_2,\dots,a_i$ vertices, then by our inductive assumption their edges are labeled using at most $a_1-1,a_2-1,\dots,a_i-1$ labels, since if we only have one connected component, then the label $r$ is never used, which is a contradiction. Thus, they use $a_1+a_2+\dots+a_i-i=n-i$ labels. This is maximized when $i=2,$ and adding in the label $r$ gives $n-1$ as the maximum number of labels. Next, let $f(n)$ be the number of maximal labelings. We have that each maximal labeling can be constructed by splitting the vertices of the graph into two groups and then labeling the edges of the subgraphs. If one of the subgraphs has $k$ vertices, then we can choose the $k$ points in $\tbinom{n}{k}$ ways, choose the labels used by each subgraph in $\tbinom{n-2}{k-1}$ ways, and label the two subgraphs in $f(k)f(n-k)$ ways. Now, if we vary this across all $k$ with $1 \le k \le n-1,$ we can see that each coloring is counted exactly twice, so we get $$2f(n)=\sum_{k=1}^{n-1} \binom{n}{k} \binom{n-2}{k-1} f(k)f(n-k).$$ But by our inductive hypothesis, this is equal to $$\sum_{k=1}^{n-1} \frac{n!}{k!(n-k)!} \cdot \frac{(n-2)!}{(k-1)!(n-k-1)!} \cdot \frac{k!(k-1)!}{2^{k-1}} \cdot \frac{(n-k)!(n-k-1)!}{2^{n-k-1}}=\sum_{k=1}^{n-1} \frac{n!(n-2)!}{2^{n-2}}=\frac{n!(n-1)!}{2^{n-2}},$$ so $f(n)=\frac{n!(n-1)!}{2^{n-1}},$ completing the proof.

We claim that the answer is $n-1$ and $\frac{1}{2^{n-1}}n!(n-1)!$. Let $A$ be the graph of with all edges labeled with $r$. Claim 1: $A$ is a complete bipartite graph of all $n$ vertices. Proof We claim that there are no odd cycles in $A$. FTSOC, let $a_{0},a_{1}, \cdots, a_{2n}$ be an odd cycle in $A$. Note that $a_{0}a_{3}$ must be an edge labeled $r$ by considering triangle $a_{0}a_{3}a_{1}$. Note that this creates an odd cycle of $a_{0},a_{3}, a_{4},\cdots, a_{2n}$. We can repeat this process until we're down to a triangle and we have a contradiction because we can't have a triangle with all three edges labeled $r$. We can just see that $A$ is complete by considering different triangles. We prove by strong induction that the maximum is $n-1$. Let $S_{1}$ and $S_{2}$ be the two disjoint graphs when we get rid of $A$. Note that because of the induction, the sum of the maximums of $S_{1}$ and $S_{2}$ is $n-2$ and we can achieve both maximums by simply having both sets have different numbers. Then, we have the $r$ itself which gives us $n-1$, thus completing the proof. Let $a_{n}$ be the number of ways to label to achieve the maximal labels. We do casework on the size of $S_{1}$. If the size of $S_{1}$ is $k$, then, we have $$\binom{n}{k}\binom{n-2}{k-1}a_{n-k}a_{k}$$ because there are $\binom{n}{k}$ ways to choose the vertices, $\binom{n-2}{k-1}$ ways to choose the labels for $S_{1}$, and $a_{n-k}a_{k}$ to label both $S_{1}$ and $S_{2}$. Now, we just sum it up and divide by $2$ because of overcounting. Thus, we get $$a_{n} = \frac{1}{2}\displaystyle\sum^{n-1}_{k=1}{\binom{n}{k}\binom{n-2}{k-1}a_{n-k}a_{k}}$$ If we let $a_{n} = \frac{1}{2^{n-1}}n!(n-1)!$, then it satisfies this recursion.

F*** (this says flip) i just spent 3 hours trying to solve the problem not knowing that two edges equal had to be greater than the third, BRUH. anyways this is a very nice problem, and i got a hint to bipartite but how does one bipartite skull maximal r is n-1, there are $c_n=\frac{n!(n-1)!}{2^{n-1}}$ ways to color. For maximality let the max be $a_n$ so $a_2=1,a_n\ge n$ FTSOC so $\exists k:a_{k+1}\ge a_k+2\implies\exists i,j:v_{k+1}v_i\ne v_{k+1}v_j\ne v_iv_j$, contradiction (the $\ne$ means not the same labeled number). Let $K_n$ be made up of two sets A,B, and a vertex v, where A is the set of vertices s.t. the edges between each of them and v is r, and $B=K_n\setminus A$. Observe that all edges between A and B are r (otherwise consider a such abv triangle, $a\in A,b\in B$, contradiction). It follows that if we let f(n) be the number of colorings of $K_n$, we have $$f(n) = \sum_{|A| = 1}^{n-1}\binom{n-1}{|A|}\binom{n-2}{|A|-1}f(|A|)f(n-|A|)\text{ (choosing set A, its colors, coloring A, coloring }B\cup v).$$ By induction with f(1)=1,f(2)=1, we have $$f(n) = \sum_{a = 1}^{n-1}\binom{n-1}{a}\binom{n-2}{a-1}f(a)f(n-a)= \sum_{a=1}^{n-1} \frac{(n-1)!}{a!(n-1-a)!}\frac{(n-2)!}{(a-1)!(n-1-a)!} \frac{a!(a-1)!}{2^{a-1}}\frac{(n-a)!(n-1-a)!}{2^{n-1-a}}=\sum_{a=1}^{n-1}\frac{(n-1)!(n-2)!}{2^{n-2}} (n-a)= \frac{(n-1)!(n-2)!}{2^{n-2}}\frac{n(n-1)}{2} = \frac{n!(n-1)!}{2^{n-1}},$$ which proves the inductive step. (Note that sure, in the explicit formula of f(n), there were n ways to select v, but we also need to divide by n since in any coloring only 1 in n of them have n-1th color)

The answer is $\boxed{n-1}$. We will prove this by strong induction; base cases $n=1,2,3$ are trivial, so assume that the statements for $1,2,\dots,n-1$ are true. Consider the largest color $r$. Since there is an edge with that color, every triangle with that edge must have exactly one other edge of that color. Thus if the edge has vertices $A$ and $B$, then we can split the other vertices into sets $S$ and $T$ such that $A$ is connected to each vertex in $S$, $B$ is connected to each vertex in $T$, but $A$ is not connected to any vertex in $T$ and $B$ is not connected to any vertex in $S$. But then for $C\in S$ and $D\in T$, triangle $ACD$ needs two edges colored $r$. $AC$ is one of them but $AD$ is not, so $CD$ must be colored $r$. Therefore, everything in $S$ is connected to everything in $T$, so the set of edges colored $r$ has a subgraph that is a complete bipartite graph with parts" $S\cup\{B\}$ and $T\cup\{A\}$. Clearly adding any more edges to the complete bipartite graph would make a monochromatic triangle, so indeed, the edges colored $r$ form exactly a complete bipartite graph. Now we can use the inductive hypothesis on the two parts" of the graph, which will give $n-2$ colors in total. Adding in the color $r$, our answer is $n-1$ as desired. $\blacksquare$ Now we find the number of labellings. We want to find the sequence $a_i$ such that $a_1=1$, $a_2=1$, $a_3=3$, and $$a_n=\frac12\sum_{k=1}^{n-1} \binom nk \binom{n-2}{k-1} a_k a_{n-k}.$$ Now I claim that $$a_n=\prod_{k=2}^{n}\binom k2=\boxed{2^{1-n}\cdot n!(n-1)!}.$$ This works for $n\le 3$, and otherwise, $$\begin{align*} a_n =& \frac12\sum_{k=1}^{n-1} \binom nk \binom{n-2}{k-1} 2^{1-k}\cdot k!(k-1)!\cdot 2^{1-n+k}\cdot (n-k)!(n-k-1)! \\ =& 2^{1-n}\sum_{k=1}^{n-1} n!\cdot (n-2)! \\ =& 2^{1-n}\cdot n!(n-1)!, \end{align*}$$ as desired. $\blacksquare$

Part a) R=N-1

We begin with considering the following claim: Claim: We can split the graph into 2 parts, namely $A,B$ and every edge joining $X$ from $Y$ must be labeled with a number $r$. Proof. Let $AB$ be an arbitrary edge that has a label $r$. Then for all points $P$, one of the edges $PA$ or $PB$ must be labeled $r$. If $PA$ is $r$, then paint $P$ red and color $P$ blue otherwise. Finally, paint $A$ blue and paint $B$ red. Then every edge joining red and blue vertices must be labeled with $r$. $\blacksquare$ By claim, there is at most $|X| - 1 + |Y| - 1 + 1 = n - 1$ different label. Now we'll prove by induction that there are exactly $\frac{n!(n-1)!}{2^{n-1}}$ ways to label the edges of our graph. $n=1, n=2$ cases are trivial, so we may assume $n \ge 3$. Let $a_n$ be the number of ways to label the edges. By claim, we can divide the vertices of the graph into 2 parts and the edges connecting between them must be labeled $n-1$. Assume that one of the parts has $s$ vertices. Then there are $\binom{n-2}{s-1}$ ways to choose $s-1$ color and $\binom{n}{s}$ ways to pick $s$ vertices and $a_sa_{n-2-s}$ ways to put colors. Summing them, we see that $a_n = \frac{1}{2}\sum_{s=1}^{n-1} \binom{n}{s}\binom{n-2}{s-1}a_sa_{n-2-s} = \frac{1}{2} \sum_{s=1}^{n-1} \frac{1}{n-1} \frac{n!(n-1)!}{2^{n-2}} = \frac{n!(n-1)!}{2^{n-1}}$, as desired. $\blacksquare$

Consider the largest number, $r.$ Then look at a singular edge with value $r.$ All other $n-2$ points must also have an edge with value $r$ to one of the endpoints of this edge. Same with every other edge with value $r.$ Thus, we have that the edges of value $r$ form a complete bipartite graph, as otherwise there would be a triangle with all edges of value $r.$ Then we can look at both parts of the bipartite graph and note that we can consider them as their own complete graph. Then this once again has a maximum value, however $<r,$ and then splits into two parts again. This occurs until all complete graphs are $K_1.$ This happens $n-1$ times because $1+(n-1)\cdot 1=n.$ Thus, the maximum of $r$ is $n-1.$ Now I present a way to represent what we're counting. First, choose $n,$ maybe like $5.$ Then, we show a complete bipartite graph by connecting the number of points in each part with a dash. For example, $2-3$ would be a complete bipartite graph with $2$ vertices in one part and $3$ in the other. After doing this multiple times, where the only numbers left are $1,$ we see that it may turn into something like $((1-1)-(1-(1-1))).$ Now, instead of parentheses, draw "circles" around the point or set of points that the parentheses cover. Two circles inside another circle then form a complete bipartite graph with oneanother. Note that there are generally $2n-1$ circles. Now we count the number of ways we can draw the circles about set of $n$ vertices. After drawing the first $n$ circles around each vertice, then continue to circle with the rule of you can only draw another circle that contains $2$ other circles. These $2$ other circles may also contain circles. Label each circle, starting from $1.$ Each new circle gets a value $1$ higher. Then, let the value of the edges in the complete bipartite graph be the value of the circle. This ensures that we have the highest $r=n-1.$ Note that after we choose $2$ circles from $a$ circles and circle the two, we end up with $a-1$ circles available to circle. Thus, our answer is $$\prod_{t=2}^{n} \binom{t}{2}=\boxed{\frac{n!(n-1)!}{2^{n-1}}}.$$

im half asleep

Graph theory yayyy We prove maximal value for $r$ is $n-1$. Consider vertex $V$. Let $VA_1,\cdots VA_k$ all are colored with $r$ and remaining $VA_{k+1}, \cdots , VA_n$ are others. Observe that as $VA_iA_j$ for $1\leq i \leq k$ and $k+1\leq j \leq n$, we should have $A_iA_j$ edge color as $r$ for condintion $(1)$. Hence observe if $S_1$ is set of $A_1,\cdots A_k$ and $S_2$ is $V,A_{k+1},\cdots A_{n}$. Then there exits edge with color $r$ from each vertex of $S_1$ to each vertex of $S_2$. If we assume by induction that both set can colord with $|S_1|-1+|S_2|-1+1$ color, which is $n-1$. Hence we use $n-1$ color to color $n$ vertex graph. Now observe from any vertex we can take some amount $k$, asign some colors $k-1$ to it. Then Do same things for remaining $n-k$. If $A_n$ is number of way to color then we have $$A_n = \sum_{i=1}^{n-1} \binom{n-1}{i}\cdot \binom{n-2}{i-1} \cdot A_i \cdot A_{n-i}$$ We prove by induction that $A_n = \frac{n! (n-1)!}{2^{n-1}}$ $$\begin{align*} A_n & = \sum_{i=1}^{n-1} \binom{n-1}{i}\cdot \binom{n-2}{i-1} \cdot A_i \cdot A_{n-i} \\ &= \sum_{i=1}^{n-1} \frac{(n-1)!}{i!(n-i-1)!} \cdot \frac{(n-2)!}{(i-1)!(n-i-1)!} \cdot \frac{i!(i-1)!}{2^{i-1}} \cdot \frac{((n-i)!(n-i-1)!)}{2^{n-i}} \\ & = \frac{(n-1)!(n-2)!}{2^{n-2}} \sum_{i=1}^{n-1} (n-i) \\ &= \frac{n!(n-1)!}{2^{n-1}} \end{align*}$$

great problem but had to peek at (b) to solve that generating function

We claim $r=n-1$ is the needed answer. Proof: First we prove $r \leq n-1$ First delete all edges labelled $1$ except one then for label $2$ and so on till $r$ this has atleast $r$ edges This gives u a new graph $T$ Claim: $T$ does not contain any cycles. Proof: Use induction on number of edges of the cycle. Say we have a cycle $V_{1} \to V_2 \to ..... \to V_k$ observe label of $V_1V_{3}$ is larger label between $V_{1}V_{2}$ and $V_{2}V_{3}$ in the orginal graph and distinct from rest edges so we can use induction on the smaller cycle $V_{1} \to V_{3} ..... \to V_{k}$ so done. so $T$ is a tree with max $n$ vertices hence $r \leq n-1$ Construction: Call the vertices $V_1,V_2,...,V_n$ the label between $V_{i},V_{j}$ is $\max\{i,j\}-1$ Now for the number of such labellings say its $b_{n}$ Claim: There exists exactly one edge having label $n-1$ Proof: IF there are two we can delete a vertex from one of the edges and in the remaining $K_{n-1}$ graph also We placed each label from ${1,2,...n-1}$ which we know is not possible. There are $\binom{n}{2}$ ways to choose $n-1$ edge once we choose that edge delete any vertex from that edge and from the reamining $n-1$ vertices we have $b_{n-1}$ ways once these two things are chosen rest of the edges labels are already fixed so $b_{n}=\binom{n}{2} b_{n-1}$ now we can easily compute