Kvant Math Problem 1461

Verified: yes
Verdicts: PASS + PASS
Solve time: 20m43s
Source on kvant.digital

Problem

Professor Tarantoga, in an article about sepulkas, gave $n$ definitions of sepulation. The professor’s graduate students gradually proved that all these definitions are equivalent. Each graduate student defended a dissertation on the topic: “Sepulation in the sense of the $i$-th definition is sepulation in the sense of the $j$-th definition.” What is the maximum number of graduate students Tarantoga could have had if the dissertations were defended sequentially and the main result of each new dissertation did not follow from those defended earlier?

K. Mishachyov

Solution

Represent the $n$ definitions by vertices $1,\dots,n$. A dissertation of the form “definition $i$ implies definition $j$” is represented by a directed edge $i\to j$.

From previously defended dissertations one may deduce implications only by repeated use of transitivity. Hence a new dissertation $i\to j$ is admissible exactly when, before adding this edge, there is no directed path from $i$ to $j$ in the current graph.

We seek the largest possible number of admissible edges that can be added sequentially.

Let the dissertations be defended in some order, and let the last dissertation be the one after which all definitions become equivalent. Immediately before this last dissertation, the graph is not yet strongly connected.

Consider the strongly connected components of the graph at that moment. Contract each component to a single vertex. The resulting condensation graph is a directed acyclic graph.

For a directed acyclic graph $D$, let $R(D)$ denote its reachability relation on distinct vertices. Thus $(u,v)\in R(D)$ if and only if there is a directed path from $u$ to $v$ in $D$. Since $D$ is acyclic, at most one of $(u,v)$ and $(v,u)$ can belong to $R(D)$ for any pair of distinct vertices. If $D$ has $k$ vertices, then

$$|R(D)|\le \binom{k}{2}.$$

Now examine any dissertation defended before the last one. At that time the condensation graph is still acyclic. Suppose the dissertation adds an edge from a component $A$ to a component $B$.

Because the dissertation is not deducible from earlier ones, there is no path from $A$ to $B$ beforehand. After adding the edge, the ordered pair $(A,B)$ becomes reachable. Hence the number $|R(D)|$ increases by at least $1$.

Initially there are $n$ components and no reachability relations, so $|R(D)|=0$. Immediately before the final dissertation, the condensation graph has some number $k\ge 2$ of vertices, and therefore

$$|R(D)|\le \binom{k}{2}\le \binom{n}{2}.$$

Since each dissertation before the last increases $|R(D)|$ by at least $1$, the number of dissertations before the last one is at most

$$\binom{n}{2}.$$

Adding the final dissertation contributes one more. Consequently the total number of dissertations satisfies

$$m\le \binom{n}{2}+1.$$

It remains to show that this bound is attainable.

Take all implications $i\to j$ with $i<j$. There are exactly $\binom{n}{2}$ of them. Defend them in decreasing order of $j-i$.

Thus the first dissertations are

$$1\to n,\quad 1\to(n-1),\quad 2\to n,\quad \dots$$

and the last among these are

$$1\to2,\quad 2\to3,\quad \dots,\quad (n-1)\to n.$$

When the implication $i\to j$ is defended, every previously added implication has length strictly greater than $j-i$. Any directed path from $i$ to $j$ would have to pass through some intermediate vertex and would require an implication of smaller length than $j-i$, which has not yet been added. Hence $i\to j$ is not deducible at the moment it is defended.

After all $\binom{n}{2}$ such dissertations have been defended, the graph contains every edge $i\to j$ with $i<j$. The graph is a complete linear order and is not strongly connected. Finally defend the dissertation

$$n\to1.$$

This implication is not deducible, since there is still no path from $n$ to $1$. After adding it, every vertex can reach every other vertex, so all definitions become equivalent.

Thus we obtain

$$\binom{n}{2}+1$$

admissible dissertations.

Therefore the maximum possible number of graduate students is

$$\boxed{\binom{n}{2}+1}.$$