Bariz - Problem

Problem

Source: 2020 Taiwan TST Round 2 Independent Study 3-2

Tags: combinatorics, Taiwan

USJL

23.05.2020 07:38

There are $n$ cities in a country, where $n>1$. There are railroads connecting some of the cities so that you can travel between any two cities through a series of railroads (railroads run in both direction.) In addition, in this country, it is impossible to travel from a city, through a series of distinct cities, and return back to the original city. We define the degree of a city as the number of cities directly connected to it by a single segment of railroad. For a city $A$ that is directly connected to $x$ cities, with $y$ of those cities having a smaller degree than city $A$, the significance of city $A$ is defined as $\frac{y}{x}$. Find the smallest positive real number $t$ so that, for any $n>1$, the sum of the significance of all cities is less than $tn$, no matter how the railroads are paved. Proposed by houkai

Generic_Username

27.05.2020 07:28

Is there an answer to this question? I've achieved 3/8 but it seems like that could be improved.

Pathological

27.05.2020 07:40

Hard problem! We claim that the answer is indeed $\boxed{\frac38}.$ We will first consider an arrangement of cities and railroads that allows us to prove that $t \ge \frac38.$ Start by selecting a large positive integer $N$, and connect cities $c_1, c_2, \cdots, c_N$ with $N-1$ railroads so as to form a path $c_1 c_2 \cdots c_N.$ Now, for even $1 \le i \le N$, create two cities $d_i$ and $e_i$, connect $c_i$ and $d_i$ with a railroad, and connect $d_i$ and $e_i$ with a railroad. it's easy to verify that this construction forces $t \ge \frac 38.$ We will now turn to the harder task of proving $t \le \frac 38.$ Translate the problem into graph theory in the obvious manner. Suppose that there are $n$ vertices for some $n > 1.$ Let $d(u)$ denote the degree of any vertex $u$. Call any vertex tangy if its degree is strictly greater than $3.$ For an edge $e = uv$ of any graph, we will define $f(e)$ to be $0$ if $d(u) = d(v)$ and $\frac{1}{\max(d(u), d(v))}$ otherwise. It's not hard to see from double counting that the sum of the significances of the vertices is precisely equal to $\sum f(e)$, where the sum is over all edges. Therefore, it suffices to show that $\sum f(e) < \frac{3n}{8}$, which is exactly what we shall show. The following is the critical claim. Claim. For any edge $e = uv$, $f(e) \le \frac14 \left(\frac1x + \frac1y + \frac12 \right),$ where $x = d(u)$ and $y = d(v).$ Proof. If $x = y$ the above is immediate, so suppose that $x, y$ are distinct from now on. Furthermore, assume WLOG that $x > y.$ If $x < 4$ the above is easy to verify by hand. Now suppose that $x \ge 4.$ Then notice that $f(e) = \frac1x = \frac14 \left(\frac1x + \frac1x + \frac2x \right) \le \frac14 \left(\frac1x + \frac1y + \frac12 \right),$ where we used the facts that $\frac1x \le \frac1y$ and $\frac2x \le \frac12.$ $\blacksquare$ From the Claim, we obtain that: $$\sum f(e) \le \frac14 \sum_{\textit{edge uv}} \left( \frac{1}{d(u)} + \frac{1}{d(v)} + \frac12 \right) = \frac18 (n-1) + \frac{n}{4} < \frac38 n,$$ as desired. $\square$ (P.S. I tried induction for about two hours and felt that many of my approaches "barely failed," so would be interested in an inductive solution)

USJL

27.05.2020 19:23

Pathological wrote: (P.S. I tried induction for about two hours and felt that many of my approaches "barely failed," so would be interested in an inductive solution) Nice one! I have heard that there is an inductive proof, but I don't know the details. I personally solved it by solving an LP optimization :p So something like your solution but maybe uglier. At least that way I don't need to think XD

houkai

29.05.2020 18:57

This problem was proposed by me, and I have two solutions (not as clean as yours though) One of the solution is to notice that if we fix a root of the tree, we could simply replace all the siblings by one of the "best" child, so the degree of the nodes at a certain depth is a constant only related to the depth, and we can translate the statement into an inequality, which can be proved by induction.

Number1048576

05.05.2023 21:08

solution.

For each $i$, let $x_i$ be the number of edges leaving a vertex of degree $i$ such that the other vertex it is connected to has degree less than $i$, let $y_i$ be the number of edges leaving a vertex of degree $i$ such that the other vertex it is connected to has degree greater than $i$, and let $z_i$ be the number of edges such that both ends of the edge have degree $i$. Note that the number of vertices with degree $i$ is equal to $\frac{x_i+y_i+2z_i}{i}$, as the total number of edges, as each vertex of degree $i$ has $i$ edges connected to it by definition, but we need to count the $z_i$ twice as they are connected to two vertices of degree $i$ to achieve $i$ times the number of vertices with degree $i$. Therefore, $n = \sum_i \frac{x_i+y_i+2z_i}{i}$. Therefore, we are trying to maximise the value $\frac{\sum_{i \geq 3} \frac{x_i}{i}}{n = \sum_{i \geq 3} \frac{x_i+y_i+2z_i}{i}}$. Now we can prove that the number of vertices of degree $1$ is equal to $S = 2 + \sum_{i \geq 3} (i-2)d_i$, where $d_i$ is the number of vertices with degree $i$ by induction. The following lemma will also be useful: For real numbers $a,b,x,y$, with $a,b > 0$, $\frac{a}{b} \geq \frac{a+x}{b+y} \iff \frac{a}{b} \geq \frac{x}{y}$ when $x,y>0$, and the opposite when $x,y < 0$ and $a+x$, $b+y>0$ (the proof is just multiplying out the fractions). Now, note that if there is a vertex $A$ of degree $1$ connected to a vertex $B$ of degree greater than $2$, then we can add a vertex $C$ of degree $2$ in between $A$ and $B$, as the value of the numerator increases by $1$ and the value of the denominator increases by $\frac{1}{2}$ (and it is easy to show that $t < \frac{1}{2}$). Therefore we can re-write the quantity we are trying to maximise as follows: $\frac{[\sum_{i \geq 3} \frac{x_i}{i}] + \sum_{i \geq 2}\frac{(i-2)(x_i+y_i+2z_i)}{i}}{\sum_{i \geq 3} \frac{x_i+y_i+2z_i}{i} + \sum_{i \geq 2}\frac{(2(i-2))(x_i+y_i+2z_i)}{i} + \frac{y_2}{2} + 4}$. We can then consider the set of pairs of degrees of vertices connected by an edge, and note that if $(a,b)$ is in the set, with $a>b+1$, we can swap $(a,b)$ for $(b+1,b)$ which will decrease the sum, that if $(a,a)$ is in the set then we can remove it from the set, and that we can swap $(b+1,b)$ for $(b,b-1)$ if $b \geq 3$ (we need that $t \geq \frac{1}{3}$, but the construction detailed in Pathological's post proves this). Therefore, we can assume that the edges in the graph connect only vertices of degrees $3$ and $2$ or $2$ and $1$. Then the quantity we are trying to maximise turns into $\frac{\frac{x_3}{3}+\frac{x_3}{6}}{x_3+\frac{y_2}{2} + 4}$. Note that the minimum value of $y_2$ in terms of $x_3$ is $2(\frac{x_3}{3}-1)$, so we need to maximise $\frac{x_3}{2(4\frac{x_3}{3}+3)} = \frac{x_3}{\frac{8x_3}{3} + 6}$, which is maximised when $x_3$ goes to $\infty$, in which case the limit is $\frac{3}{8}$, as required.