The Dlanod saga continues

The short answer is that the feasible graphs (being connected and satisfying the budget constraint) are the Dynkin diagrams of the types $A_n,D_n,E_n, \tilde A_n, \tilde D_n$ and $\tilde E_n$ . For $n\geq 10$ , there are exactly 4 such diagrams, namely, $A_n,D_n, \tilde A_{n-1}$ and $\tilde D_{n-1}$ , but for $n=9$ we have, in addition, $\tilde E_8$ . Thus the largest possible number Dlanod might be thinking of is $\boxed{10}$ .

Dynkin diagrams play an important role in many branches of maths and physics, from Lie algebras to string theory.

While there are sophisticated conceptual ways to analyse Dynkin diagrams, it can also be done with very basic methods; nothing more than high-school algebra is required. Be prepared to complete some squares!

Since we have dealt with cycles before , we can now restrict our attention to (feasible) trees.

We will consider several cases, depending on the maximal order $M(T)$ of the vertices in the tree $T$ . Let's look at two extreme and simple cases first:

If $M(T)=2$ , then $T=A_n$ , a feasible tree.

If $M(T)\geq 5$ , with $ord(P)\geq 5$ , then we can populate hotel $P$ with 2 guests and 5 of its neighbours with 1 each, resulting in an overall loss of 1 Ruble. Thus there are no feasible trees $T$ with $M(T)\geq 5$ .

If $M(T)=4$ , with $ord(P)= 4$ , then we can populate hotel $P$ with 4 guests and its 4 neighbours with 2 each, breaking even. If there were an additional vertex $Q$ in the tree connected to one of $P's$ neighbours, we could populate $Q$ with 1 patron, for an overall loss of 1 Ruble. Thus the only feasible tree with $M(T)=4$ is $T=\tilde D_4$ .

So, it all comes down to trees $T$ with $M(T)=3$ . Assume there is more than one point in $T$ of order 3, two such points being $P$ and $Q$ . Then $T$ will contain a subtree of the form $\tilde D_n$ for $n\geq 5$ . Let's populate the 4 hotels in $\tilde D_n$ of order 1 with 2 patrons each, and the others with 4 each, breaking even. If there were an additional vertex $Q$ in the tree connected to one of the vertices in $\tilde D_n$ , we could populate $Q$ with 1 patron, for an overall loss of at least 1 Ruble. Thus $T=\tilde D_n$ . We leave it to the reader to verify that $\tilde D_n$ is indeed feasible, by completing squares.

We are left with the case where there is a single point $C$ in $T$ of order 3. We discussed this issue once before, years ago . Lazy guy that I am, let me simply recycle that solution, mutatis mutandis: There are 3 roads of various lengths emanating from $C$ . Let's say that these three roads involve $a,b$ and $c$ hotels, respectively, not counting the central hotel, $C$ . We may assume that $a\leq{b}\leq{c}$ .

If we complete the squares of our quadratic form, starting at the ends of the three roads and working our way towards the center, the coefficient of the central hotel ends up being $q=1-\frac{a}{2a+2}-\frac{b}{2b+2}-\frac{c}{2c+2}$ (we leave this as an exercise to the reader; obviously, it suffices to do the computation for one of the roads). The graph will be feasible if (and only if) this coefficient $q$ is non-negative.

If $a=b=1$ and $c$ is arbitrary, we get the feasible tree $D_n$ .

If $a=1$ and $b=2$ , we get feasible trees for $c=2,3,4,5$ , meaning that $T=E_6, E_7, E_8$ or $\tilde E_8$ .

If $a=1$ and $b\geq 3$ , then the only feasible tree is $a=1$ and $b=c=3$ , meaning that $T=\tilde E_7$

Finally, if $a\geq 2$ , then the only feasible tree is $a=b=c=2$ , meaning that $T=\tilde E_6$ .

This concludes our proof.