function
IMO Shortlist
graph theory
combinatorics
Extremal combinatorics

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:

[b]1.[/b] Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label.

[b]2.[/b] 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.

[b](a)[/b] Find the maximal $r$ for which such a labelling is possible.

[b](b)[/b] [i]Harder version (IMO Shortlist 2005):[/i] For this maximal value of $r$, how many such labellings are there?

[hide="Easier version (5th German TST 2006) - contains answer to the harder version"]
[i]Easier version (5th German TST 2006):[/i] Show that, for this maximal value of $r$, there are exactly $\frac{n!\left(n-1\right)!}{2^{n-1}}$ possible labellings.[/hide]

[i]Proposed by Federico Ardila, Colombia[/i]

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) \equal{} \sum_{n \geq 1} \frac {f(n)x^n}{n!(n \minus{} 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 [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=123690[/url].)

[hide]
For (a), it follows easily by induction that the maximal $ r$ is $ n\minus{}1$.

For (b), note that it is impossible by (a) for a $ n\minus{}1$-labeling of an $ n$-gon to have more than one $ 1$. Suppose it did. Let $ AB$ be one of these edges. Clearly no other edge connected to $ A$ is labeled $ 1$, and for every vertex $ C$, $ AC\equal{}BC$. Then, remove vertex $ A$. Clearly, each label $ {1, 2, ... , n\minus{}1}$ still remains on some edge, and the labeling remains good. This contradicts (a).

Thus there is a unique edge labeled $ 1$ for each $ n\minus{}1$-labeling of $ n$. Now, choose this edge $ AB$ in $ \binom{n}{2}$ ways and collapse $ AB$ into a single vertex $ A'$. Label $ A'C$ the label that $ AC$ and $ BC$ were both labeled. Next decrease every label of the graph by $ 1$. Clearly we have an $ \binom{n}{2}$-to-1 mapping from the $ n\minus{}1$-labelings of $ n$ to the $ n\minus{}2$-labelings of $ n\minus{}1$. By induction the answer is $ \frac{n!(n\minus{}1)!}{2^{n\minus{}1}}$.[/hide]

[quote="m.candales"]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[/quote]
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 [b]JBL[/b] 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.$

[b]a)[/b] 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]b)[/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 [b]a).[/b]

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}}}.$

[hide = Brute force gen func]
[hide = (a)]
Observe that these conditions have little to do with the actual values of the labels and rather with the number of labels and relative size of the labels. I claim that at most $n-1$ labels can be used, by induction on $n$.
For $n=3$ this is obvious, and vacuously for $n=2$ we can have only $1$ label.

Now suppose that the maximum is $n-1$ for all $n<N$. In a regular $N$-gon, take a vertex $V$ and consider the labels on the $N-1$ edges incident to $V$. Suppose that $k$ distinct labels appear ($k\le N-1$) and that the groups of vertices corresponding to these labels are $A_1, A_2, \dots A_k$. We can see that any edges incident to vertices of $2$ different groups have a well-defined label that appeared as a label on an edge incident to $V$, so it remains to consider the edges within each $A_i$. We further observe that any triangle consisting of an edge in $A_i$ corresponding with a vertex in $A_j$ must satisfy condition $2$, so the only triangles we need to consider have all three vertices in a particular $A_i$. However by induction an $A_i$ satisfying condition $2$ can have at most $|A_i|-1$ labels, and summing over all the groups we see that the total number of labels is at most $$k +\sum_{i=1}^k (|A_i|-1) = k+N-1-k = N-1$$ as desired. (The inequality comes from possible repetitions among the labels within groups.)

The construction for $N-1$ is simple: let all the edges from one vertex be labeled $N-1$, and in the $K_{N-1}$ that remains apply the same construction inductively.
[/hide]
[hide = (b)]
We use the same structure as in part a, but instead of considering the labels first, we pick the groups of vertices $A_1, A_2, \dots A_k$ and only then assign the labels.

First we define some notation: for a partition $p$ of $n-1$, let the terms of $p$ be $b_1, b_2, \dots b_m$ (WLOG $b_1\le b_2\le \cdots \le b_m$). Let the function $$s(p) := \prod _{j=1}^{n-1} (\# b_i =j)!$$
In other words, $s(p)$ is some measure of how many terms of the partition are equal. Finally, let $f(n)$ denote the desired number of labelings of the $n$-gon.

For a fixed partition $p$, it is not hard to see that there are exactly
$$\frac{(n-1)!}{s(p) \prod_{i=1}^k (b_i)!}$$
ways to pick the $k$ groups of vertices attached to $V$ (this is the multinomial theorem). Once the groups are chosen, we need to choose $b_i$ labels for group $A_i$ - one for the edges joining $V$ to $A_i$ and $b_i-1$ for edges within $A_i$. All these groups of labels will be distinct by the equality case of the inequality from the inductive step of part a. Again by the multinomial theorem there are exactly
$$\frac{(n-1)!}{\prod_{i=1}^k (b_i)!}$$ ways to do this. (We do not need to consider $s(p)$ this time because now we need to distinguish between labels of two groups of the same size.) Once the group of labels has been chosen, the largest label in that group must be attached to the edges between $V$ and the vertices in the group. There are $f(b_i)$ ways to label the remaining edges in the group, so overall we find
$$f(n) = \sum_{p(n-1)} \frac{((n-1)!)^2}{s(p)} \prod_{i=1}^k \frac{f(b_i)}{(b_i!)^2}$$
We just have to show that this sum is equal to $\frac{(n-1)! n!}{2^{n-1}}$.

By induction, we get
$$f(n) = \sum_{p(n-1)} \frac{((n-1)!)^2}{s(p)} \prod_{i=1}^k \frac{1}{2^{b_i-1}b_i}$$
$$=\sum_{p(n-1)}\frac{((n-1)!)^2}{s(p)2^{n-1}} \prod_{i=1}^k \frac{2}{b_i}$$
So now it will suffice to show
$$\sum_{p(n-1)} \frac{1}{s(p)} \prod_{i=1}^k \frac{2}{b_i} = n$$
We rewrite the sum on the left as
$$g_{n-1} = \sum_{a_1+2a_2+\cdots + (n-1)a_{n-1} = n-1} \prod_{i=1}^{n-1}\frac{2^{a_i}}{i^{a_i}\cdot a_i!}$$
Now we turn this problem into one about generating functions. We want to show
$$g(x) = \sum_{j=0}^{\infty} g_j x^j = \sum_{j=0}^{\infty} (j+1)x^j$$
$$\iff g(x) = \frac{1}{(1-x)^2}$$
Observe that $g$ is given by the generating function
$$g(x) = \left(1 + 2x + \frac{(2x)^2}{2!} + \cdots\right) \left(1 + x^2 + \frac{x^4}{2!} + \cdots \right)\left(1 + \frac{2}{3}x^3 + \cdots \right)\cdots$$
$$ = \prod_{i=1}^\infty \sum_{j=0}^\infty \frac{\left(\frac{2}{i}x^i\right)^j}{j!}$$
$$ = \prod_{i=1}^\infty e^{\frac{2}{i}x^i}$$
$$ = e^{\sum_{i=1}^\infty \frac{2}{i}x^i}$$
So taking logs, we want to show
$$\sum_{i=1}^\infty \frac{2}{i} x^i = 2 \ln\left(\frac{1}{1-x}\right)$$
But this is equivalent to the series expansion for $\ln \left(\frac{1}{1-x}\right)$, so now we are done.
[/hide]
[/hide]

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 [b]rigid[/b] 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.)
[quote=Pentakratie]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:

[b]1.[/b] Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label.

[b]2.[/b] 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.

[b](a)[/b] Find the maximal $r$ for which such a labelling is possible.

[b](b)[/b] [i]Harder version (IMO Shortlist 2005):[/i] For this maximal value of $r$, how many such labellings are there?

[i]Proposed by Federico Ardila, Colombia[/i][/quote]

The regular $n$-gon phrasing is not required since we are working on a $K_n$. Call a colouring of type (2) to be [i]popular[/i]. 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)):

[b]Lemma.[/b] 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)$.

[b]Claim:[/b] $G$ is complete bipartite.
[b]Proof:[/b] 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 [i]color[/i]. Part (a) is known before. In fact, we will prove the following claim.

[color=#f00][b]Claim:[/b][/color] 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.)

[i]Proof 1 (Induction).[/i] 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$

[i]Proof 2 (Extremal).[/i] 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$-[i]original[/i] if deleting $v$ result in no edges with label $i$. We claim that

[color=#f00][b]Claim:[/b] [/color]For each vertex $a$, there exists exactly one $a$-original color.

[i]Proof:[/i] 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.

[color=#f00][b]Claim:[/b] [/color]There is no subgraph of $k$ vertices with at most $k-2$ distinct colors.

[i]Proof:[/i] 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$

[color=#f00][b]Claim:[/b][/color] There exists exactly one edge colored $1$.

[i]Proof:[/i] Suppose that there are two edges colored one. We split into two cases.
[list]
[*]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.
[/list]
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.
[list]
[*]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$.
[/list]
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 [b]Th3Numb3rThr33[/b]. The answers are $r=n-1$ and $\dfrac{n!(n-1)!}{2^{n-1}}$. We will prove these inductively. The base cases are clear.

[color=blue][b]Solution to part (a).[/b][/color]     Say a [i]family[/i] 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 [i]egotistic[/i] 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.

[color=blue][b]Solution to part (b).[/b][/color]     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 [b]cosmicgenius[/b].

[color=#f00][b]Part a).[/b][/color] 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$.

[color=#00f][b]Claim: [/b][/color]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$.

[color=#00f][b]Proof: [/b][/color]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$

[color=#f00][b]Part b).[/b][/color] 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 [b]dantaxyz[/b].

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.

[color=#ff9a00][b]Claim 1:[/b][/color] $G_r$ is bipartite.

[color=#ff9a00][i]Proof:[/i][/color] 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$

[color=#ff9a00][b]Claim 2:[/b][/color] $G'$ is the disjoint union of 2 cliques: $K_a,K_{n-a}$, for some $1\le a \le n-1$.

[color=#ff9a00][i]Proof:[/i][/color] 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$
------------------------------------------------------------------------------------------------------------------
[b][color=#00f]Part (a).[/color] [/b]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.
-----------------------------------------------------------------------------------------------------------------
[b][color=#00f]Part (b).[/color] [/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.

[hide=Remarks] The key was to look at the $r$-edges. Note that in any set of 3 vertices, either 0 or 2 of them are $r$-edges. We can exploit this condition by considering minimal paths and cycles with $r$-edges. The key was to realize that the $r$-edges split the $K_n$ into 2 smaller complete graphs. Once we had this structure figured out, the induction and computation was not hard.[/hide]

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

[color=#073763]Claim: [/color]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$

[color=#073763]Proof: [/color]
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} \]

[color=#073763]Claim: [/color] For all $n$,
\[T_n = \frac{n!(n-1)!}{2^{n-1}}\]

[color=#073763]Proof: [/color] 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$

[hide = pretty short solution]
Okay, so focus on the minimum weight edge. It has weight $1$, clearly. Now focus on the vertices forming this edge, call them $u, v$. Consider any other node $w$. A simple checking reveals that the weight of $uw$ and $vw$ is equal. This simple observation reveals that $u, v$ can be treated as copies of each other. Thus we can "contract" the graph by superimposing $u, v$ onto each other. This preserves all the conditions and it is easy to see any such structure also covers all possibilities. A simple induction can easily prove that the maximal value of $r$ is $n-1$. (induct down using the "contraction" and subtracting 1 from the other edge weights, if there are more than $1$ weight edge, equality can't hold)
Now let $f(n)$ denote the count of such graph labellings over $K_n$. Now from the "contraction" observation, it is clear we need only pick an edge and assign it a weight of $1$ and then contract down to recursion. This gives $f(n) = {n \choose 2} f(n-1)$ and thus \[ \boxed{f(n) = \frac{n! (n-1)!}{2^{n-1}}}\]
[/hide]

[hide=Solution]
Let $x_n$ be the number of ways to achieve the maximum value of $r$ with $x_2=1$. We claim that the maximum value of $r$ is $n-1$ and $x_n=\frac{n!(n-1)!}{2^{n-1}}$. We will prove this by induction.

Base Case: $n=3$
Then, we have that at least two of the edges must be equal, so $r\leq2$. The only possibilities for $r=2$ are making two edges labeled with $2$ and one edge labeled with $1$, so $x_3=3=\frac{3!2!}{2^2}$.

Inductive Step:
Consider the set of edges that are not labeled with the largest number. Then, it must be made up of complete graphs. Suppose that there are $i$ connected components with $a_j$ vertices in the $j$th connected component. Then, by the inductive hypothesis, at most $a_j-1$ colors can be used, so there are at most $1+\sum_{k=1}^i(a_j-1)=1-i+\sum_{k=1}^ia_j$ colors. If $i=1$, then we must have that $a_1\leq n-1$, so $1-i+a_1\leq n-1$. Equality holds when $a_1=n-1$, so this gives $nx_{n-1}$ possibilities. If $i\geq2$, then since $\sum_{k=1}^ia_j\leq n$, we must have $1-i+\sum_{k=1}^ia_j\leq n-1$. Therefore, at most $n-1$ colors can be used. Equality holds when $i=2$ and $a_1+a_2=n$. This gives $\sum_{k=2}^{n-2}\binom nk\binom{n-3}{k-2}x_kx_{n-k}$, so we must have
$$x_n=\frac{n!(n-2)!}{2^{n-2}}+\sum_{k=2}^{n-2}\frac{n!}{k!(n-k)!}\frac{(n-3)!}{(k-2)!(n-k-1)!}\frac{k!(k-1)!}{2^{k-1}}\frac{(n-k)!(n-k-1)!}{2^{n-k-1}}.$$ This is equal to \begin{align*}
\frac{n!(n-2)!}{2^{n-2}}+\sum_{k=2}^{n-2}\frac{n!(n-3)!(k-1)}{2^{n-2}}&=\frac{n!(n-2)!}{2^{n-2}}+\frac{n!(n-3)!}{2^{n-2}}\frac{(n-2)(n-3)}2\\
&=\frac{n!(n-2)!}{2^{n-1}}(2+(n-3))\\
&=\frac{n!(n-1)!}{2^{n-1}}.
\end{align*}

Therefore, this means that the minimum value of $r$ is $\boxed{n-1}$ and this can be achieved $x_n=\boxed{\frac{n!(n-1)!}{2^{n-1}}}$ ways.

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$.

[b]Claim:[/b] By only considering edges labelled with $n-1$, we get a complete bipartite graph.
[b]Proof:[/b] 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$

[hide=oops]the first three sentences aren't even necessary

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.

[hide=Solution] a) We will show that $r \leq n-1$. Suppose otherwise and take $n$ edges of distinct colors; this implies the existence of a "colorful" cycle. Take the smallest one; it can't be a triangle due to the restriction in the statement. Hence, we can take any three consecutive vertices $abc$ on this cycle and notice that we can remove $b$ since the edge $ac$ has the same color as $ab$ or $bc$, which doesn't appear again among the other edges of the cycle, contradiction. Hence $r \leq n-1$.

b) Let $f(n)$ be the answer; consider a valid labeling with $n-1$ colors. Notice that if an edge $ab$ is with label $1$, then for any other $c$, the edges $ca, cb$ are of the same label, so we can merge $a, b$ into one vertex. Do this for every edge of label $1$; suppose that the new graph has at most $n-2$ vertices and the color $1$ doesn't appear anymore. Hence, there are at most $n-3$ colors in the labeling of this graph, as we proved in a). Hence the total number of colors in the original graph is at most $n-2$, contradiction. This means that there is exactly one edge of label $1$. Then, by doing the merging above for this edge, we obtain $f(n)=\binom{n} {2}f(n-1)$, because there are $\binom{n} {2}$ choices for the edge of label $1$. Hence, by induction, the answer is $\frac{n!(n-1)!}{2^{n-1}}$ and we are done.

$\textbf{Remark.}$ The proof of a) uses a similar idea as in RMM 2020/3 (of course, this idea is just a small part of the RMM problem).

Label the vertices of $K_n$ as $v_1, v_2, \ldots, v_n$.

[color=#00f][b]Part (a).[/b][/color] 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.

[color=#f00][b]Claim:[/b][/color] $G_S$ has at most two connected components.
[I]Proof.[/I] 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.
:yoda:

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.

[color=#00f][b]Part (b).[/b][/color] 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$. \\

[b][color=#00f]Claim 1:[/color][/b]
$A$ is a complete bipartite graph of all $n$ vertices.
[i]Proof[/i]
    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
[hide=Hint]
Assume by induction it is true for N vertices.


real analysis
inequalities
Functional Analysis
advanced fields
advanced fields unsolved

I can't prove this exercises, so if you can do it, please post it.

" Prove that $ f_{N}\to 0$ weakly in $ L^{2}(\minus{}\pi,\pi)$, where $ f_{N}(t) \equal{}\frac{1}{N}\sum_{n\equal{}1}^{N^{2}}e^{int}$ "

any help I'll really appreciate.

Adriana

Ps: This exercises is in Functional Analysis , Rudin (as you know a very "nice" book)

Go right to the definition of weak convergence: when tested by an arbitrary linear functional, which in the case of a Hilbert space is when tested by inner product with an arbitrary fixed element.

Let $ g(t) \equal{}\sum_{n \equal{}\minus{}\infty}^{\infty}\widehat{g}(n)e^{int}.$

Note that $ \|g\|^{2}\equal{}\sum_{n \equal{}\minus{}\infty}^{\infty}|\widehat{g}(n)|^{2}<\infty.$

We must show that $ \left\langle g,f_{N}\right\rangle \equal{}\frac{1}{N}\sum_{n \equal{} 1}^{N^{2}}\widehat{g}(n)$ goes to zero as $ N\to\infty.$

Now: given $ \epsilon > 0,$ find $ m$ so that $ \sum_{n \equal{} m\plus{}1}^{\infty}|\widehat{g}(n)|^{2}<\epsilon^{2}.$

For $ N$ such that $ N^{2}> m,$

$ \left|\frac{1}{N}\sum_{n \equal{} 1}^{N^{2}}\widehat{g}(n)\right|\le\frac{1}{N}\sum_{n \equal{} 1}^{m}|\widehat{g}(n)|\plus{}\frac{1}{N}\sum_{n \equal{} m\plus{}1}^{N^{2}}|\widehat{g}(n)|$

The first term on the right is $ \frac{1}{N}$ times a fixed finite sum and goes to zero as $ N\to\infty.$ We use the Cauchy-Schwartz inequality on the second term:

$ \frac{1}{N}\sum_{n \equal{} m\plus{}1}^{N^{2}}|\widehat{g}(n)|\le\frac{1}{N}\sqrt{N^{2}\minus{}m}\left[\sum_{n \equal{} m\plus{}1}^{N^{2}}|\widehat{g}(n)|^{2}\right]^{\frac{1}{2}}$

$ \le\frac{N}{N}\left[\sum_{n \equal{} m\plus{}1}^{\infty}|\widehat{g}(n)|^{2}\right]^{\frac{1}{2}}<\epsilon.$

Hence $ \limsup_{N\to\infty}\left|\frac{1}{N}\sum_{n \equal{} 1}^{N^{2}}\widehat{g}(n)\right| <\epsilon,$

which means that the limit is zero.

Note that we might as well have been working in $ \ell^{2}$ the whole time - everything was given from the beginning in terms of a particular orthonormal basis.


[hide="Answer"]$\triangle AHC$ is a 30-60-90 triangle, so we have $AC=2x$, $AM=CM=AH=x$, $HC=x\sqrt{3}$. Because $AH=AM$, $\triangle AHM$ is isosceles, and $\angle HAM=60^\circ$, so $\triangle AHM$ is equilateral. Therefore, $HM=x$. Finally, we draw the altitude from $M$ to $HC$, which must split $HC$ in half because $\triangle MHC$ is isosceles. Therefore, we see that both triangles must be 30-60-90 triangles, so $\angle MHC=30^\circ\Rightarrow \boxed{C}$.[/hide]


Suppose $n$ lines in plane are such that no two are parallel and no three are concurrent. For each two lines their angle is a real number in $[0,\frac{\pi}2]$. Find the largest value of the sum of the $\binom n2$ angles between line.
[i]By Aliakbar Daemi[/i]

[quote="Hawk Tiger"]Actually,If we denote by $\angle(l_{1},l_{2})$ the angle between $l_{1},l_{2}$,and $0\leq \angle(l_{1},l_{2})<\frac{\pi }{2}$
and $\measuredangle(l_{1},l_{2})$ the measured angle between $l_{1},l_{2}$($0\le\measuredangle(l_{1},l_{2})<\pi$)
then$\measuredangle(l_{1},l_{2})\leq \angle(l_{1},l_{2})$
IF the n lines are $l_{1},...l_{n}$
THen
For$n=2m+1$
\[\sum_{1\leq i<j\leq 2m+1}{\angle(l_{i},l_{j})}\le \sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi \]
for $n=2m$
\[\sum_{1\leq i<j\leq 2m,}{\angle(l_{i},l_{j})}=\sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\angle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\angle(l_{j},l_{i})}+\sum_{1\leq i\leq m,j=i+m}{\angle(l_{i},l_{j})}\le \sum_{1\leq i<j\leq 2m,j-i\leq m-1}{\measuredangle(l_{i},l_{j})}+\sum_{1\leq i<j\leq 2m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}+m\frac{\pi}{2}=\frac{m^{2}}{2}\pi \]
I left the detailed(i.e.how to prove $\sum_{1<i<j\leq m,j-i\leq m}{\measuredangle(l_{i},l_{j})}+\sum_{1<i<j\leq m,j-i\geq m+1}{\measuredangle(l_{j},l_{i})}=\frac{m(m+1)}{2}\pi$ and the other one)
to the reader.I am busy today.........[/quote]
I forgot to post that lines $l_{1},...l_{n}$ is in order.(My english is bad,I mean that there exist line $l$ such that $\measuredangle(l_{i},l)\leq \measuredangle(l_{i+1},l)$,for any i)

Note translating a line does not effect its angle with some other line. Basically, all that matters is the direction of lines. Hence we may WLOG assume that all lines are concurrent at some point ($O$ say). Let $S$ be the set of those $n$ lines.

[b][color=#f00]Key Claim: [/color][/b] The maximum sum is attained when two of the lines are perpendicular.

[i]Proof: [/i] Consider any random line $\ell \in S$ and $m$ be the line passing through $O$ and perpendicular to $\ell$ (which we assume is not currently in $S$). We WLOG assume all lines lie on the same side of $\ell$ (say all of them lie above $\ell$). Let $\ell_1,\ell_2,\ldots,\ell_{n-1}$ be the $n-1$ lines (other than $\ell$). Now other than $\ell$, there are lines on left and right side of $m$. WLOG, the left side has $\ge$ lines than right side. On the left side, let $\ell_i$ be the line next to $m$. Observe replacing $\ell_i$ by $m$ does not decrease the sum of angles, proving our Claim. $\square$

Now observe if two lines $a,b$ are perpendicular, then for any line $x$ we have
$$ \angle (a,x) + \angle (b,x) = \frac{\pi}{2} $$
So if $f(n)$ denotes the max sum in the question, then using our Claim we obtain the reccursion
$$ f(n) = f(n-2) + (n-1) \cdot \frac{\pi}{2} ~~ \forall ~ n \ge 3$$
Now it is easy to note that $f(1) = 0$ and $f(2) = \frac{\pi}{2}$. Hence,
\begin{align*}
f(2k+1) &= f(1) + \frac{\pi}{2} \left(2k + (2k-2) + \cdots + 2 \right) = \frac{\pi}{2} \cdot  k(k+1) \\
f(2k+2) &= f(2) + \frac{\pi}{2} \left((2k+1) + (2k-1) + \cdots +3 \right) = \frac{\pi}{2} \left((2k+1) + (2k-1) + \cdots + 1 \right) = \frac{\pi}{2} \cdot (k+1)^2
\end{align*}
This completes the proof. $\blacksquare$


The figure shown is the union of a circle and two semicircles of diameters of $ a$ and $ b$, all of whose centers are collinear. The ratio of the area of the shaded region to that of the unshaded region is

$ \displaystyle \textbf{(A)}\ \sqrt {\frac {a}{b}} \qquad \textbf{(B)}\ \ \frac {a}{b} \qquad \textbf{(C)}\ \ \frac {a^2}{b^2} \qquad \textbf{(D)}\ \ \frac {a \plus{} b}{2b} \qquad \textbf{(E)}\ \ \frac {a^2 \plus{} 2ab}{b^2 \plus{} 2ab}$
[asy]unitsize(2cm);
defaultpen(fontsize(10pt)+linewidth(.8pt));

fill(Arc((1/3,0),2/3,0,180)--reverse(Arc((-2/3,0),1/3,180,360))--reverse(Arc((0,0),1,0,180))--cycle,mediumgray);
draw(unitcircle);
draw(Arc((-2/3,0),1/3,360,180));
draw(Arc((1/3,0),2/3,0,180));

label("$a$",(-2/3,0));
label("$b$",(1/3,0));
draw((-2/3+1/15,0)--(-1/3,0),EndArrow(4));
draw((-2/3-1/15,0)--(-1,0),EndArrow(4));
draw((1/3+1/15,0)--(1,0),EndArrow(4));
draw((1/3-1/15,0)--(-1/3,0),EndArrow(4));[/asy]

[hide]
Answer: B
In the problem, a clear semicircle with radius b cuts into the shaded region in the upper half of the circle, and a shaded semicircle with radius a cuts into the clear region in the circle's bottom half. These semicircles' areas would therefore cancel out. Therefore, we must take the differences of the areas of the semicircles (for our purposes we will assume that b>a):
pi(b/2)^2/2-pi(a/2)^2/2 = (pi)b^2/8-(pi)a^2/8 = (pi/8)(b^2-a^2)
We must now add/subtract the difference to the area of each half of the large circle to find the shaded/clear area. Since we assumed that the area of semicircle b is greater than that of semicircle a, we must subtract the difference from the area of the large half-circle to determine the shaded area, which contains semicircle a:
shaded area = (pi/8)(a^2+2ab+b^2)-(pi/8)(b^2-a^2) = (pi/8)(2a^2+2ab)
Conversely, we must add the difference to the area of the large half-circle in order to find the clear area, which contains semicircle b:
clear area = (pi/8)(a^2+2ab+b^2)+(pi/8)(b^2-a^2) = (pi/8)(2b^2+2ab)
Therefore, the ratio of the shaded area to the clear area is the following:
(2a^2+2ab)/(2b^2+2ab) = (a^2+ab)/(b^2+ab) = [a(a+b)]/[b(a+b)] = [b]a/b[/b][/hide]

[hide="Answer"]$A_{shaded}=\frac{\pi (a+b)^2}{2}+\frac{\pi a^2}{2}-\frac{\pi b^2}{2}=\pi (a^2+ab)$
$A_{unshaded}=\frac{\pi (a+b)^2}{2}+\frac{\pi b^2}{2}-\frac{\pi a^2}{2}=\pi (b^2+ab)$
$\frac{A_{shaded}}{A_{unshaded}}=\frac{a^2+ab}{b^2+ab}=\frac{a}{b}\Rightarrow \boxed{B}$[/hide]

It doesn't seem like ya'll are accounting for the area that lies outside of the circle with diameter a+b.
If you are, please explain how you controlled for that.

There is no area that lies outside of the circle. Both of the smaller circles are internally tangent to the larger circle. They can't possibly have any area outside it.

[hide]The entire circle has radius $\frac{a+b}{2}$. The area of the shaded region is the area of the big semicircle minus the area of semicircle b, plus semicircle a's area. The area of the white is the big semicircle minus semicircle b plus semicircle a.

Shaded: $\frac{(\frac{a+b}{2})^2}{2}\pi-\frac{(\frac{b}{2})^2}{2}\pi+\frac{(\frac{a}{2})^2}{2}\pi=\frac{a(a+b)}{4}\pi$.

White: $\frac{(\frac{a+b}{2})^2}{2}\pi-\frac{(\frac{a}{2})^2}{2}\pi+\frac{(\frac{b}{2})^2}{2}\pi=\frac{b(a+b)}{4}\pi$.

Ratio: $\frac{\frac{a(a+b)}{4}\pi}{\frac{b(a+b)}{4}\pi}=\frac{a(a+b)}{b(a+b)}=\frac{a}{b}$.
[/hide]

[quote="JesusFreak197"]Oops, I didn't even realize I was using the diameter instead of the radius. :roll: Oh well, it still works. :P[/quote]

I was thinking that your solution was so easy... until I realized that there was a mistake (but since you always calculated the area from the diameter, the change wasn't visible).

the reason that the smaller circles cannot lie outside the larger circles like that is because they have a smaller radius of curvature... if you think about it too, when you move along the larger circle, the smaller circle pulls in faster than the larger circle...i also believe you can show this with power of a point...not sure though


ratio
projective geometry
geometry unsolved
geometry

two triangles $ABC$ and $DEF$ are such that $AD$ , $BE$, $CF$ are concurrent at $O$.let $DE, AB$ intersect at $Z$ ,$AC,DF$ intersect at $Y$ and $BC,FE$ intersect at $X$ prove that $A\{XYZO\}=D\{XYZO\}$ without using desargues theorem.

I think that, by the notation $A\{XYZO\},$ you mean the double ratio (=cross ratio) of the pencil $A.XYZO,$ which let us to change in to $(A.XYZO).$

So, if this is correct, we can solve your problem as follows:

We denote the points $S\equiv AD\cap EF$ and $T\equiv AD\cap BC.$

Because of the pencil $A.XYZO$ is intersected from the segment line $BC,$ we have that $(A.XYZO) = (X,C,B,T)$ $,(1)$

The segment line $EF,$ intersects the pencil $D.XYZO$ and so, we have $(D.XYZO) = (X,F,E,S)$ $,(2)$

The segment lines $BC,$ $EF,$ intersect the pencil $O.XCBA$ and so, we have that $(X,C,B,T) = (X,F,E,S)$ $,(3)$

From $(1),$ $(2),$ $(3)$ $\Longrightarrow$ $(A.XYZO) = (D.XYZO)$ $,(4)$ and the proof is completed.

Kostas Vittas.

PS. From $(4),$ we conclude that the points $X,$ $Y,$ $Z,$ are collinear (because of the pencils $A.XYZO,$ $D.XYZO,$ have the segment line $AD,$ as their common ray) and so, we have a proof ( well known I think) of the Desarques's theorem, based on the double ratio theory.


Compute the following:

$ \lim_{r \to 0}\frac {1 \minus{} \frac {1}{(1 \plus{} \frac {r}{k})^{ nk}}}{r}$

As a side note, this formula has some financial implications (it is not in the exact same form, but it is similar), such as computing prices of bonds given certain yields to maturity. $ n$ represents the number of years until maturity, $ k$ represents the frequency of payment per year (i.e. if $ k \equal{} 2$, one receives payments every 6 months) and $ r$ represents the yield to maturity percentage. In this case, the limit is evaluating what the price of the bond would be if $ r \equal{} 0$.

Hint:
[hide]Binomial Expansion[/hide]

First I simplified the expression

Lim [(1 + r/k)^-nk - 1]/[ r(1 + r/k)^-nk]

then using l´hospitale´s

it simplified to lim 1/r which doesn't exist...

Are you sure that the limit was supposed to approach 0?

I apologize - I made a mistake with the signs. The new expression should now be correct (hopefully  :D).

l'Hopital's rule does make this problem fairly straightforward I suppose, but I would think it makes it a bit more messy and not as elegant. If you solve it using that rule, also consider the hint I gave for another approach.

[quote="pkothari13"]Compute the following:

$ \lim_{r \to 0}\frac {1 \minus{} \frac {1}{(1 \plus{} \frac {r}{k})^{ nk}}}{r}$

As a side note, this formula has some financial implications (it is not in the exact same form, but it is similar), such as computing prices of bonds given certain yields to maturity. $ n$ represents the number of years until maturity, $ k$ represents the frequency of payment per year (i.e. if $ k \equal{} 2$, one receives payments every 6 months) and $ r$ represents the yield to maturity percentage. In this case, the limit is evaluating what the price of the bond would be if $ r \equal{} 0$.

Hint:
[hide]Taylor series[/hide][/quote]

Taylor series goes into the calculus forum not around here....

Sorry about that - I guess while technically it is a Taylor Series, this should be under the realm of Intermediate Topics because it is a [b]binomial [/b]expansion. That gives most of the problem away lol, but oh well.


I came up with this new problem when I try to select icons on my desktop. I myself isn't a nice combinatorician, so can anybody help me to solve this?

For a $ n\times n$ table, find the maximum number $ a$ of cells that can be coloured such that the following is satisfied:
For all $ 0\leq x\leq a$, there always exist a rectangular region in the $ n\times n$ table, that contains $ x$ coloured cells.

I should add one more point here, a rectangular region means a region of reatangular shape, with sides parallel to either one edge of the $ n\times n$ table.

Also, a region of zero size is also considered to be a reactangular region.


In how many ways can we pick three different numbers out of the group

1,2,3,..., 100

such that the largest number is larger than the product of the two smaller ones? (The order in which we pick the numbers does not matter.)

I'm confused, please help...thanks! :lol:

I present two approaches, one can work them out in detail.

Approach 1: Let $ x<y<z$ be the three numbers. Set $ x\equal{}i\le 9$, then we can find a $ y_{max}$ such that $ xy_{max}<100$ so that $ y$ can take any value from the set $ \{i\plus{}1,\dots ,y_{max}\}$.For  every value corresponding to $ y$-set we have a $ z$-set so that $ z$ can take any values greater then that. Here is an example:

For $ x\equal{}3$,
$ y$-set=$ \{4,5,\dots ,33\}$

This gives the corresponding $ z$-set,
$ \{12,15, \dots ,99\}$ (observe the Arithmetic sequence !)

We have $ (100\minus{}12)\plus{}(100\minus{}15)\plus{}\dots \plus{}(100\minus{}99)\equal{}(100\minus{}12)30\plus{}3(\sum 29)$

Continuing this way, you can get a closed form.

Approach 2: Place the numbers in columns of 10 each (increasing as you go up or right). We do the following operation: Select a number from the the lowest row and the left most column, and see where they meet. Since, they meet at their product we can choose any number greater than the product. Let them be $ a$ and $ b$  respectively.Then, the third number can be chosen in $ 100\minus{}ab$ ways. Further, it it not difficult to handle $ a\equal{}b$ and $ a<b$.


Is there a specific name of the first part of this inequality?

$\sqrt{\frac{a_1^2+a_2^2+...a_n^2}{n}} \geq \frac{a_1+a_2+...+a_n}{n} \geq ({a_1a_2...a_n})^\frac{1}{n} \geq \frac{n}{1/{a_1}+1/{a_2}...+1/{a_n}}$

It's called quadratic mean or root mean square (QM or RMS)

So the inequality is fully called:

QM-AM-GM-HM or RMS-AM-GM-HM

Although, we do have other parts. Generally:

$\displaystyle\sqrt[m]{\frac{a_1^m+a_2^m+\ldots+a_n^m}{n}} \geq \sqrt[m-1]{\frac{a_1^{m-1}+a_2^{m-1}+\ldots+a_n^{m-1}}{n}}$

Plugging in $m=2$ we get:

$\sqrt{\frac{a_1^2+a_2^2+...a_n^2}{n}} \geq \frac{a_1+a_2+...+a_n}{n}$ which is the QM-AM part.

[quote="10000th User"]I call it RMS for Root Mean Square. I've heard of Power Mean but I'm not sure if that is the same as RMS...[/quote]

I think Power Mean is $\sqrt[x]{\frac{a_1^x+a_2^x+\ldots+a_n^x} {n}} \geq \sqrt[y]{\frac{a_1^y+a_2^y+\ldots+a_n^y} {n}}$ for all $x>y$ and equality occurs when $a_1=a_2=\ldots=a_n$.

$\text {RMS-AM-GM-HM}$

$\sqrt{\frac{a_1^2+a_2^2+\ldots+a_n^2} {n}} \geq {\frac{a_1+a_2+\ldots+a_n} {n}} \geq \sqrt[n]{a_1 \cdot a_2 \cdot \ldots \cdot a_n} \geq {\frac{n} {\frac{1} {a_1}+\frac{1} {a_2}+\ldots+\frac{1} {a_n}}}$

Note that RMS-AM is just power mean with $x=2$ and $y=1$.

While I'm at it, does anyone know what RMS (or power mean) is used for in real life?

Wow, they sure raised the standard for getting started... you now have to know the power-mean inequality?... and RMS-AM-GM-HM...

[url=http://mathcircle.berkeley.edu/BMC6/ps0506/inequalities.pdf]This[/url] says it's the Power Mean Inequality. :D

Does anyone have proofs for these that don't use Lagrange Multipliers?


geometry
3D geometry
icosahedron
USAMTS
geometry unsolved

Faces ABC and XY Z of a regular icosahedron are parallel, with the vertices labeled
such that AX, BY , and CZ are concurrent. Let S be the solid with faces ABC, AY Z,
BXZ, CXY , XBC, Y AC, ZAB, and XY Z. If AB = 6, what is the volume of S?

[b]( GHAAQ)[/b]

This is a current [url=http://www.usamts.org/]USAMTS[/url] problem.


A teacher asks his pupil to find the greates angle of a triangle with sides 21, 41 and 50. The pupil "solves" the problem as follows :

[i]Let C be the vertex that corresponds with the greatest angle.
Then sin(<C) = 50/41 = 1,21951...
1 corresponds to sin 90 and 0,21951 corresponds to sin 1240'48".
Hence <C = 90 + 1240'48" = 10240'48". [/i]
Of course this method is ridiculous ... but ... (surprise) :
THE ANSWER IS CORRECT !

(1) Explain why this method has to give the correct answer, although (mathematically) it does not make sense.
(2) Find out whether there exist other triangles, not similar to the given triangle, for which this method works. Is it possible to describe all triangles for which this method works ?

Same 'Freaky problem' as on Artofproblemsolving, huh? :D  :D


superior algebra
superior algebra solved

let $G$ be a group of order $n$ and let $p$ be an odd prime .suppose thereexist distinct elements$ x_1,x_2,...,x_p\in G$ such that $x_1x_2=x_2x_3=\dots=x_{p-1}x_p=x_px_1$.prove that $2p||G|$.

Define $k=x_1 x_2$, and let be $m:=ord (k)$.

Now by definition we get $\prod_{i=1}^m x_{2i-1}x_{2i}=k^m=e=k^m=\prod_{i=1}^m x_{2i}x_{2i+1}$ where all coefficients are considered modulo $p$.
Then by considering $\prod_{i=1}^m x_{2i-1}x_{2i} \cdot x_{2m+1} = x_1 \cdot \prod_{i=1}^m x_{2i}x_{2i+1}$ you get $x_1=x_{2m+1} \implies 2m \equiv 0 \mod p \implies m=ps$.

Let be $q:=\prod_{i=1}^p x_i$, then we have that $q^2=k^p$, so $(q^s)^2=e$. Now if we assume that $q^s=e$ we get that $x_1 k^{\frac{ps-1}{2}} = e =  k^{\frac{ps-1}{2}} x_p $ which immediatly gives the contradiction $x_1=x_p$. So there is an element of order $2$ and together with that we know about $m$, we get by Lagrange that $2p | n$.

Here's what I did (just a sketch):

We show (it's really easy; just playing around with the relations in an obvious manner) that $(x_2x_1)^p=(x_1x_2)^p=(x_1x_2\ldots x_p)^2=(x_2x_3\ldots x_px_1)^2$.

If $2\not|\ |G|$, then $x\mapsto x^2$ is injective, and we get $x_1x_2\ldots x_p=x_2x_3\ldots x_px_1$, and from here we quickly get a contradiction.

If $p\not|\ |G|$, then $x\mapsto x^p$ is injective, so $x_1x_2=x_2x_1$, and the contradiction is even more obvious here (we use the fact that the $x_i$ are distinct).


probability
expected value
number theory proposed
number theory

This was also given to us last week.
Prove that If A={a_1,a_2,...,a_n} is subset of natural numbers.
Prove that A has a free-sum subset that $|A| \geq \frac n3$
Sum-free set is a set that $a+b=c$ has no answers in $A$

Very similar to a problem from USA TST. And as far as I know, this problem was created by Erdos, as a beautiful example of the probabilistic method.

here is the solution I know about this one.consider a prime nuber p=3k+2 such that p is greater than $max \{\ x\in  A \}\$now $C=\{\ k+1,k+2,...,2k+1 \}\$.so$\frac{|C|}{p-1}> \frac 13$.now if we observe $1\leq x<p$which x is chosen at random.then assume that $d_i$ is remainder $x.b_i$ (mod p)so u can conclude that $P(d_i\in C)=\frac{|C|}{p-1}.\frac13$ .accordinggto probablitistic methodeach $d_i$ at least for $\frac 13$ of x ,belongs to C.so if we choose random x,then greater than $\frac n3$of $d_i$ belongs to C.and it is trivial that C is sum free.so we are done.

Harazi, what is the probabilistic method?
I've been searching for a soln to that problem a lot, but with no succes!

What sam-n did is the probabilistic method, I think. I've never used it in problem solving, but as far as I know, this is what it means: if you're trying to maximize a set with certain properties, then sometimes it's extremely convenient to choose such a set randomly, and show that this works.

sam-n chose $x$ randomly, so each $d_i$ is in the desired set $C$ with probability $>\frac 13$. This means that when you choose $x$ randomly, the expected number of $d_i$ which are in $C$ is $>\frac n3$, and this is what we need.

I read an article which said that in order for this to work, the constraints on the sets should enforce a somewhat uniform distribution, as is the case here.

Anyway, I don't know that much on the subject. [url=http://encyclopedia.thefreedictionary.com/Probabilistic%20method]Here[/url]'s a link to (sort of) a definition.

Sorry, perhaps I'm just a little too dumb for this forum, but I don't understand sam-n's solution, for I don't know, what $b_i$ means. As far as I can see, it is not defined anywhere. And is A supposed to be a set of consecutive positive integers or can the $a_i$ be chosen arbitrarily from the set of natural numbers (provided that there are no repetitions, i.e. there are no two numbers $a_i, a_j \in A, \, i \ne j$ with $a_i=a_j$)?

My guess is (actually, I'm pretty sure) that $b_i=a_i$, and $a_i$ need not be consecutive, just distinct (well, that's included in the definition of a set).

Yes, I didn't read sam-n's post while posting my previous mesage, sorry.
As fas as I understand, sam_n says for $p=3k+1$ the probability of
 $a_i d$ $mod$ $p$
to lie
in $k+1 \cdots 2k$ is $\frac{1}{3}$ for any fixed $d$.
If we let d rund through any of $1..p-1$ we select the set $B_d$ to be all $a_i$ with
$a_i d \in \{k+1 \cdots 2k\}$.
Now since $d$ runsthrough $ALL$ residues (the uniformity harazi was speaking)
one of $B_d$ will have at least the expected cardinality which is $\frac{n}{3}$.
Hence we choose $B_d$ to be our set.
Thanks, Sam_n!


does anyone have the result for this competition?

[quote="11th dimension"]Ya, Don Mills owned!   :gleam:[/quote]

do you have the  result that you can post it here though?

Those are machine marked, and only teachers have it.  The hand marked results are not out yet.  last year's results came out much faster.  I wonder what the markers are doing...?
:play_ball:

the [url=http://www.ecf.utoronto.ca/apsc/davinci/2005_exam/results.html]result[/url] is out

[quote="11th dimension"][quote="d.lam.86"]You know what I just noticed? They put Don Mills Collegiate in NORTH YORK, Ontario. I wonder if that's a mistake because I've always consider DMCI as in the area of Don Mills. They also put Lin Fei in grade 11 and I heard a while back when he was arguing about how his age/grade always seems to be posted wrong. LOL, it must suck being in such a position (in my opinion, ofcourse).[/quote]

Lol, after you get used to it, it feels fine.
Also, Peng who got first in Da Vinci (congrats by the way  :first: ) he is in grade 11 and they put him as gr 12 winner.  And for me, who should have won the gr 10, they put me as gr 11 winner (again.....).
In conclusion, the results are so messed up.[/quote]

They should get editors. I'd love to be an editor; I practically editted my school yearbook in record time. I've got keen eyes at spelling mistakes, punctuation errors, etc. Maybe I should put that on my résumé: "keen eyes"!  :rotfl:

crap... that looks like a really cool contest.  I'd have done well, since I do electronics, physics, and chemistry...

What's the answer to the one with the 2 cylinders rolling down the ramps?  Is the hollow O-shaped one slower than the filled-in circle?

its rigged for people that live in toronto - at the science center, everyone visits that display where they actually have a metal ring and a wooden cylinderblock.


In the cube pictured, $ M$ and $ N$ are trisection points of $ \overline{AB}$, $ P$ and $ Q$ are trisection points of $ \overline{EF}$, and each edge is 3 units in length. What is the number of units, rounded to the nearest tenth, in the perimeter of $ \bigtriangleup MNQ$?
[asy]
import olympiad; size(200); import geometry; import graph; import three; import graph3; import solids;

draw((0,1,1)--(1,1,1)--(1,1,0)--(0,1,0)--(0,1,1)--cycle, linewidth(2pt));

draw((0,1,1)--(1,1,1)--(1,1,0)--(0,1,0)--(0,1,1)--cycle, linewidth(2pt));

draw((0,0,1)--(0,1,1)--(1,1,1)--(1,0,1)--(0,0,1)--cycle,linewidth(2pt));

draw((1,0,1)--(1,0,0)--(1,1,0)--(1,1,1)--(1,0,1)--cycle,linewidth(2pt));

draw((1,0,1)--(1,1,0)--(0,1,1)--(1,0,1)--cycle,linewidth(2pt));

triple P = (1,1/3,0); triple Q = (1,2/3,0); triple M = (2/3,0,1); triple N = (1/3,0,1);

dot(Label("$P$",align=SW),P); dot(Label("$Q$",align=SW),Q); dot(Label("$M$",align=NW),M); dot(Label("$N$",align=NW),N);

label("$A$", (0,0,1), N); label("$B$",(1,0,1),N); label("$E$",(1,0,0),W); label("$F$",(1,1,0),E); draw(M--Q--N); label("$3$",((1,1,1)--(1,1,0)),E);
[/asy]

MN = 1
MQ = sqrt(1^2+3^2+2^2)=sqrt(14)
NQ = sqrt(2^2+3^2+2^2)=sqrt(17)

then just add them up.

8.8647630123916019354051585882906...

so answer is [b]8.9[/b]

seeing that this is a target round I believe this should have a no-calc answer, but this can be done by just estimating

Actually, on target round the use of calculators is permitted.

For MQ, you find MB and BQ, then use the Pythagorean theorem. For NQ, you find NB and BQ, then use the Pythagorean theorem. If you want me to post a solution, just tell me.


linear algebra
matrix
vector
complex numbers
linear algebra unsolved

Let $ A$ a $ n \times n$ matrix and $ C$ a $ m \times n$ matrix.

We say vector $ x \in \mathbb{R}^n$ is $ x \geq 0$ iff $ x_i \geq 0$ $ \forall i \in \{1,2,...,n\}$.

Define $ S(C)\equal{}\{x \in \mathbb{R}^n | Cx \geq 0 \}$.

We say that a $ n \times n$ matrix $ P$ is positive definite over $ S(C)$ iff $ x^TPx > 0$ $ \forall x \in S(C)\minus{}\{0\}$.

Problem:
give a necessary and sufficient condition on $ A$ so that $ \exists$ a simmetric and positive definite matrix $ P$ s.t. $ A^TP \plus{} PA$ is negative definite over $ S(C)$.

Hints:

1 - An only necessary condition is that $ A$ hasn't eigenvectors in $ S(C)$ that correspond to positive eigenvalues (if the eigenvalue is complex, the positiveness is referred to its real part).

2 - If $ S(C) \equiv \mathbb{R}^n$, then we have a solution of $ A^TP \plus{} PA$ iff all eigenvalues of $ A$ are negative (again negativeness is referred to real part if the eigenvalue is complex).


counting
distinguishability
function
combinatorics theorems
combinatorics

Why are there $\binom{n+k-1}{k-1}$ ways to select $n$ objects from $k$ types?

aright wouldn't it be there are n + 2 places to place k - 1 partitions? that would separate it into k types? Maybe your right tho

That's not quite the right statement for that formula  $ {n \plus{} k \minus{} 1 \choose k \minus{} 1}$ describes the number of ways to place $ n$ indistinguishable objects [i]into[/i] $ k$ distinguishable categories.  The result can be understood as follows:  we can separate indistinguishable objects into distinguishable categories by placing dividers between the objects.  We need $ k\minus{}1$ dividers to do this, and once we have put them in we have $ n \plus{} k \minus{} 1$ symbols, some of which are dividers and some of which are objects.  The number of ways to arrange them all is clearly $ {n \plus{} k \minus{} 1 \choose k \minus{} 1}$.

See also a solution by generating functions [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=184510]here[/url].

Ah i understand- thanks t0ra.
So if there are 8 types of dogs and we want to choose 19 it would be 26C7?


inequalities
linear algebra
matrix
function
quadratics
linear algebra unsolved

Let $A,B\in S_n(R)$ be 2 symmetric positive definite matrix and $\alpha \in (0,1)$.Show that:
$det(\alpha A+(1-\alpha)B)\geq(det(A))^{\alpha}(det(B))^{1-\alpha}$.

Since $A,B$ are positive definite symmetric, there exists matrix $P$ such that $P^*AP=diag(\lambda_1,...,\lambda_n)=D$ and $P^*BP=I$. Thus
$det(\alpha A +(1-\alpha)B)=det(B)det(P^*(\alpha A +(1-\alpha)B)P))=det(B) \prod_{i=1}^n \left (\alpha\lambda_i+1-\alpha \right)$ (*).
Now the convexity comes in the inequality $\alpha \lambda+1-\alpha \geq \lambda^{\alpha}$, because the function $f(t)=\lambda^t$ is convex and $f(\alpha x+(1-\alpha)y) \leq \alpha f(x)+(1-\alpha)f(y)$ and taking $x=1,y=0$ we get the required inequality $\alpha \lambda+1-\alpha \geq \lambda^{\alpha}$ for $0<\alpha<1$ and $\lambda>0$. Using this inequality and (*) we obtain that $det(\alpha A +(1-\alpha)B) \geq det(B)det(D)^{\alpha}=det(B)det(A)^{\alpha}det(B)^{-\alpha}=det(A)^{\alpha}det(B)^{1-\alpha}$.

i think the matrix $P$ in this case isn't orthogonal my method is to consider the positive symetric matrix $C$ such that $A=C^2$ and let $Z=C^{-1}$ thus we have $det(\alpha A+(1-\alpha) B)=det(A) det(\alpha I+(1-\alpha)ZBZ)$
and we have $ZBZ$ is symetric positive the conclusion follows thanx to the convexity of $t\to t^{\alpha}$ as you have proved :).

[quote="hpe"][quote="eugene"]Since $A,B$ are positive definite symmetric, there exists matrix $P$ such that $P^*AP=diag(\lambda_1,...,\lambda_n)=D$ and $P^*BP=I$.  [/quote] Not in general. Only if $AB=BA$. However, your argument shows that we may assume that $A$ is diagonal.[/quote]
Not. What i said that if $A,B$ are hermitian(symmetric) and $A$ is positive definite then there exists a matrix $P$(not necessary unitary) such that $P^*AP=I$ and $P^*BT$-diagonal
Proof: It is known that positive definite quadratic form is congruent with identity matrix, so there is $Y$ such that $Y^*AY=I$.Now the matrix $C=Y^*BY$ is hermitian and there exists unitary matrix $U$ such that $U^*CU$ is diagonal.Now we can just take $P=YU$.

Or maybe there is a bug because of the basic  field $\mathbb{R}$?

you're right eugene  :blush: actually it seems that i was so sleepy that i didn't noticed that $det(B)det(P^*P)=1$

[quote="eugene"]What i said that if $A,B$ are hermitian(symmetric) and $A$ is positive definite then there exists a matrix $P$(not necessary unitary) ...[/quote]You're right, Eugene  :oops: