mm actually the problem did appear in the Australian TST, Day 2 as Problem 3 (there are 4 problems on each of the 2 days). My favourite solution is the one where you perform operations on the shortlist which only make the inequality stronger, until you reduce it to a triviality and in fact you can prove something a little stronger ... i might write it out properly sometime later.

Darij, I don't think your wording is exactly equivalent to the original wording : I think that it is also possible for a vertex to have only one successor. However, it doesn't really affect the solution. I will call dynastic vertices blossoms. We will call a vertex a bud iff. it is a direct successor of a blossom but is not a blossom itself. Let $m$ be the number of blossoms. We prove the stronger bound \[n \ge (m+1)(k+1)+m. \] This is sufficient because $(m+1)(k+1)+m = m(k+2)+k+1 > m(k+2)$. We proceed by induction on $m$. For the base case, we have one blossom which must have two buds, each of which must have at least $k$ indirect successors. Now, if we have many blossoms, then there exists one blossom none of whose indirect successors are blossoms. We remove this blossom, one of its buds, and all indirect successors of that bud, and we make the remaining bud a direct successor of any vertex of which our blossom was a direct sucessor. All other blossoms remain blossoms; all other buds remain buds. We have decreased $n$ to some number $n'$ which is at least $k+2$ less than $n$; we have decreased the number of blossoms by one, and we have not changed $k$. The inductive hypothesis gives \[n-(k+2) \ge n' \ge m(k+1)+m-1, \] which is sufficient to prove what we wanted. This bound is sharp, for we can have equality when we have a sequence $A_{1}, \ldots, A_{m}$ of blossoms such that $A_{i+1}$ is a successor of $A_{i}$, and each bud has exactly $k$ indirect successors.

Boy Soprano II wrote: Darij, I don't think your wording is exactly equivalent to the original wording : I think that it is also possible for a vertex to have only one successor. I am not sure about this - there are different ways to read the problem. However, you are right in that in that it doesn't affect the solution. We can even allow vertices to have several (more than $2$) successors, as long as a "dynastic vertex" is redefined as a vertex which has at least two successors each of which has at least $k$ extended successors. Boy Soprano II wrote: I will call dynastic vertices blossoms. We will call a vertex a bud iff. it is a direct successor of a blossom but is not a blossom itself. Let $m$ be the number of blossoms. We prove the stronger bound \[n \ge (m+1)(k+1)+m. \] Note: This holds only if $m>0$. (This is a subtle point; the first of the two proposed solutions makes a minor mistake here.) Anyway, why I am posting this? Because there is a very cheap way to make the problem stronger: Generalized problem. Let $T$ be a forest. Let $k$ be a nonnegative integer. For every vertex $v$ of $T$, we denote by $s_v$ the number of successors of $v$ each of which has at least $k$ extended successors. (Here, the notion of an "extended successor" is defined as in the original problem; in particular, no vertex is considered its own extended successor.) A blossom of $T$ means a vertex $v$ of $T$ such that $s_v > 0$. Assume that $T$ has at least one blossom. Then, $T$ has at least $\left(k+1\right)+\sum_{v\text{ blossom of }T}\left(1+\left(s_v-1\right)\left(k+1\right)\right)$ vertices. The solution is the same as the one given by Boy Soprano II for the original problem, but this time we have to remove $s_v-1$ buds at the induction step.

We assume the graph is a tree. Call a dynastic vertex a "HUGE" vertex. Call the successors of huge vertices "big" vertices. Call the set of extended successors of big vertices a "family". We will assign $k+2$ distinct vertices to each huge vertex, and then we will finish. To do this, divide the tree into levels. Define $m$ so that level $m$ is the highest: it has only one vertex. Level $1$ is the lowest level, consisting only of leaves. Call level $i$, $L_i$. Call $H_i$ the set of huge vertices in level $1$, $2$, ..., $i$. I will demonstrate I can assign to a huge vertex $H \in H_j$ $k+2$ distinct vertices (that are extended successors of some big vertex that is a successor of $H$), for any $1 \le j \le m$, using induction. Applying this to $j=m$ we will finish. The base case: for a huge vertex, assign one of his successors and his family and the vertex itself to that vertex. Clearly we assigned at least $k+2$ vertex (remove vertices if needed). We cannot overlap vertices because huge vertices in this level cannot have huge extended successors (it is the lowest possible level for huge vertices). Now for the inductive step. Take the assignment for $H_{j-1}$. Consider a huge vertex $X$ in $L_j$. Consider the set of all his extended successors. If this set has no huge vertices, assign to $X$ himself, one of his successors and his family. If this set has huge vertices, take such a huge vertex $Y$ in the lowest level. To $Y$ we already assigned some vertices, and all of these vertices are extended successors of $Y$. So, to $X$ we assign himself, and the family of the other big vertex that is a successor of $Y$ (and this big vertex itself). So we are done.

First we can see that we only need to prove this for $1$ tree because if we do then summing up the maximum of dynastic vertexes for all trees(with $a_{1},a_{2},...,a_{s}$ vertexes) we get that the maximum is $\sum_{1\le i\le n} \frac {a_{i}}{k+1}=\frac {n}{k+2}$. So we only need to prove for one tree. First define the level of the tree $T$ as the largest path from the root of $T$ and denote the level of $T$ by $L(T)$. Denote by $N(T)$ the number of vertices in $T$. We will use a induction on $L(T)$. In fact we will say that there are at most $\frac {N(T)-k-1}{k+2}$ dynastic vertexes for $N(T)>k$ and there are $0$ for $N(T)\le k$. Base: $L(T)=0$ is trivial. Now consider that it's true for $L(T)\le s$ consider $L(T)=s+1$ now let $u,v$ be the $2$ successors of the root of $T$ denoted by $r$. Denote by $U$ the parts of the tree containing $u$ and it's successors. Analougosly define $V$. Note that $L(U),L(V)<L(T)$ so we may use induction on $U,V$ Proof: Note that if $N(T)\le k$ then clearly there are no dynastic vertices. If $N(T)\ge k+1$ then note that if $N(U)\le k$ then $r$ is not dynastic and if $N(V)\le k$ then there are $0\le \frac {N(T)-k-1}{k+2}$dynastic vertices and if $N(V)>k$ then there are at most $\frac {N(V)-k-1}{k+2}<\frac {N(T)-k-1}{k+2}$. We prove the desired result similarly for $N(V)\le k$. If $N(V),N(U)>k$ then there are at most (since $r$ is a dynastic vertex) $1+\frac {N(V)-k-1}{k+2}+\frac {N(U)-k-1}{k+2}=\frac {N(T)-k-1}{k+2}$ dynastic vertices. So we are done. end

Assume the forest is connected. The problem can be strengthened to $\frac{n-k-1}{k+2}$. We do this by induction on $n$. Suppose a graph had a dynastic vertex. Then by definition, the graph must have at least $1+2+2k=2k+3$ vertices. Moreover, for a graph with $2k+3$ vertices, there can be at most 1 dynastic vertex. Thus the problem statement is true for $n\le 2k+3$. For the inductive step, assume our graph had a dynastic vertex. Take a dynastic vertex such that none of its extended successors are dynastic - such a vertex clearly exists, as a dynastic vertex has at least $2k+2$ extended successors, and an extended successor of a vertex has less extended successors than the original vertex. Let this vertex be $V$. Let its successors be $A$ and $B$. Then $A$ and $B$ each have at least $k$ extended successors. Remove exactly $k+2$ of these extended successors. Note that $V$ may not be dynastic anymore. On the other hand, $V$ still has at least $2k+2-(k+2)=k$ extended successors. Thus, if $X$ is a dynastic vertex such that $V$ is an extended successor to $X$, after the operation, $X$ is still dynastic. Any successor to $V$ was not dynastic either, so no dynastic vertices are lost there either. Thus we remove at most $1$ dynastic vertex from our graph while removing $k+2$ vertices, implying there are at most $1+\frac{n-2k-3}{k+2}=\frac{n-k-1}{k+2}$ dynastic vertices in our graph by our inductive hypothesis, as desired.

darij grinberg wrote: Let $k$ be a nonnegative integer. A forest consists of rooted (i. e. oriented) trees. Each vertex of the forest is either a leaf or has two successors. A vertex $v$ is called an extended successor of a vertex $u$ if there is a chain of vertices $u_{0}=u$, $u_{1}$, $u_{2}$, ..., $u_{t-1}$, $u_{t}=v$ with $t>0$ such that the vertex $u_{i+1}$ is a successor of the vertex $u_{i}$ for every integer $i$ with $0\leq i\leq t-1$. A vertex is called dynastic if it has two successors and each of these successors has at least $k$ extended successors. Prove that if the forest has $n$ vertices, then there are at most $\frac{n}{k+2}$ dynastic vertices. Improvise the bound to $\tfrac{n-(k+1)}{k+2}$ and induct on $n \ge 1$; base cases $n \le 2k+3$ are trivial. We consider only the case when $G$ is a tree. For a dynastic vertex $w$; define the set of all its (extended) successors as its dynasty. This dynasty splits into two clans determined by the immediate successors of $w$. Further we see that several oriented trees append to the clan-members. Call these the relatives of $w$. Pick a dynastic vertex $v$ with the largest dynasty. Let $A$ and $B$ be the two clans originating from $v$ and $C$ be the relatives of $v$. Let $G'=A\cup B \cup C \cup \{v\}$. Observe that $H=G/G'$ consists of oriented trees $P_1, \dots, P_{\ell}$ that can be identified by vertices $v_1, \dots, v_{\ell}$ with directed edge $\overrightarrow{v_iv} \in E(G)$ for all $1 \le i \le \ell$. Notice that for any $u \in G'$, no extended successor of $u$ lies in outside $G'$. Indeed we see that the unique (non-oriented) path from $u$ to a vertex outside $G'$ passes through $v$. However the orientations till $u$ to $v$ differ from that of $\overrightarrow{v_iv}$ for all $1 \le i \le \ell$. Now no dynastic vertex in $H$ has an extended successor in $G'$ else the maximality of $v$'s dynasty is contradicted! Thus, $v_i$ is not a clan-member of any dynasty for all $1 \le i \le \ell$. Finally, we can apply IH to the sets $G'$, $P_1/\{v_1\}, \dots, P_{\ell}/\{v_{\ell}\}$ thus $G$ has no more dynastic vertices than $$\sum^{\ell}_{i=1} \frac{|P_i|-1-(k+1)}{k+2}+\frac{s-(k+1)}{k+2}=\frac{n-s-(k+2)\ell+s-(k+1)}{k+2}<\frac{n-(k+1)}{k+2}$$unless $\ell=0$ (i.e. $G'=G$). If that is the case; delete $v$ and apply IH to the two trees so obtained. The conclusion still holds. $\blacksquare$

It suffices to prove the result if $G$ is a tree. We prove the stronger bound \[ \frac{n - (k+1)}{k+2} \]by induction on $n$ with the base cases $n \le k+1$ being clear. Let $v$ be the dynastic vertex highest up in the tree, and let $T$ be the sub-tree rooted at $v$. Note that no vertex $w \notin T$ can be dynastic, otherwise any common ancestor of $v$ and $w$ would be dynastic too; thus discard vertices not in $T$. Now, the two children of $T$ induce two sub-trees $A$ and $B$. So the total number of dynastic vertices is at most \[ \frac{|A| - (k+1)}{k+2} + \frac{|B| - (k+1)}{k+2} + 1 = \frac{(|A|+|B|-1) - (k+1)}{k+2} \]as desired.

Call a forest with all vertices having $0$ or $2$ children a binary forest. Claim: A binary forest with $k$ leaves has at most $2k-1$ vertices. Proof: WLOG, we may assume that we have a tree, since summing over the connected components gives the general result. We proceed by induction on $k$. If $k=1$, then our tree consists of a single vertex, which clearly satisfies the condition. Suppose we're given a tree $\tau$ with $k$ leaves. Define the depth of a vertex to be its distance to the root. Consider a leaf $L$ with maximal depth, and let its parent be $P$. We see that $P$ has some other child $L'$, and since $L$ had maximal depth, $L'$ is also a leaf. Now, deleting $L$ and $L'$, we have a new tree $\tau'$ with $1$ fewer leaf (since $P$ becomes a leaf), and two fewer vertices, so the result follows by induction. $\blacksquare$ Given the forest $G$ on $n$ vertices, let $S$ be the set of vertices with at least $k$ descendants. We see that the induced subgraph for $S$ is a tree where each vertex has $0$, $1$, or $2$ children. We wish to show that the number of ``cherries'' in the induced subgraph of $S$ (things of the form $(P,\{A,B\})$ where $A$ and $B$ are the children of $P$) is at most $\frac{n}{k+2}$. To do this, create a graph $G'$ by taking the induced subgraph of $S$ and contracting all edges that are from a parent to an only child. The number of cherries in this graph is the same as the number of cherries in the induced subgraph of $S$, and furthermore, for each leaf of $G'$, we have at least $k$ new vertices of $G$ that are not in $S$ (in particular, this set of $k$ vertices is distinct for each leaf of $G'$). Letting $\ell$ be the number of leafs of $G'$, we then see that the total number of vertices in $G$ is at most $(2\ell-1)+k\ell$, so \[(2\ell-1)+k\ell\le n\implies\ell\le\frac{n}{k+2}.\]We have that the number of cherries in $G'$ is at most $(2\ell-1)-\ell\le\frac{n}{k+2}$ (each non-leaf contributes a cherry), so the number of cherries of the induced subgraph of $S$ is at most $\frac{n}{k+2}$, as desired. Remark Our proof shows that the estimate can be sharpened to \[\frac{n+1}{k+2}-1.\]

Call a connected component a tree. I claim that if a tree has $x$ dynastic vertices, the tree itself must have at least \[f(x) = (k+1)+x(k+2) \text{ nodes}\]This will clearly suffice to prove the $\frac{n}{k+2}$ bound. We proceed with induction on $x$. For the base case, $x=1$, in order to have a dynastic vertice we need 1 node, two immediate children, and each of those children have $k$ children, for a total of \[1+2+2\cdot k = 2k+1=f(1) \text{ nodes}\]For the inductive step, take some tree with $m+1$ dynastic vertices. Call $P$ the node from which all others are descended. Label it's children as $A$ and $B$. Claim 1: If either $A$ or $B$ have legacy $<k$, then we can throw out the P and the bad child which would decrease total \# of nodes but not the number of dynastic. Now, assume both $A$ and $B$ have $\geq k$ children. Assume that $A$'s family(including A) has $a$ dynastics, and $B$ has $m-a$ dynastics. For $a>0$, inductive hypothesis handles. However, when $a=0$, we use the earlier claim to bound below as $\geq k+1$ on A's side. Thus, the total number of nodes is at least \[1+f(a)+f(m-a) = 1 + 2\cdot (k+1) + (a+m-a)\cdot (k+2) = 2k+3 + m\cdot(k+2) = f(m+1)\]And we are done! $\blacksquare$

WLOG the forest $G$ is a tree, since otherwise we just sum the result over all trees. Let the root be $v$, and for any other vertex in the tree, let its $\textit{rank}$ be the shortest distance from it to $v$. Let $v_0$ be the dynastic vertex with lowest rank; it follows that all other dynastic vertices are descendants of $v_0$, else if there is another dynastic vertex $u$ for which $u$ is not a descendant of $v$, then the earliest common ancestor of $v_0$ and $u$ must clearly be dynastic, and it has lower rank than $v_0$, contradicting the minimality assumption of $v_0$'s rank. Let $T$ be the sub-tree of $G$ with root $v_0$. Since it is dynastic, it leads off to exactly two successors, $x$ and $y$, each of which are the roots of disjoint sub-trees $T_x$ and $T_y$ of $T$. At this point, it remains to induct, but straightforward induction does not work as the bound is not sharp enough. Through some fudging, we see that the bound of at most $\tfrac{n - (k+1)}{k+2}$ dynastic vertices is sharp, and we proceed to strong induct on this value;\begin{align*}\text{dynastic}(G) = \text{dynastic}(T) &= 1 + \text{dynastic}(T_x) + \text{dynastic}(T_y)\\&\leq 1 + \frac{|T_x| - (k+1)}{k+2} + \frac{|T_y| - (k+1)}{k+2}\\&= \frac{|T_x| + |T_y| - k}{k+2}\\&\leq \frac{|T| - (k+1)}{k+2}\end{align*}completing the general inductive step. The base cases are easy; for $|G| \leq k+1$, we cannot have dynastic vertices, so the result generally follows from induction.

Hardest C2 ever? Notice that proving the fact for a tree is sufficient. Let the family of a vertex be itself and all its descendants. Choose a dynastic vertex, cross it out, and color all the vertices in its family red. Then, color $k+2$ vertices of its family blue (so that a vertex that is colored red then colored blue is considered blue). Repeat this process until all dynastic vertices are chosen. We claim by induction on the number of crossed-out vertices that it is possible to color in such a way that no vertex is colored blue twice. We prove these two statements simultaneously: 1. It is possible to color in such a way that no vertex is colored blue twice. 2. After each step, each vertex that is not in the family of a crossed-out vertex has at least $k+2$ family members that are not blue. The case of one vertex being crossed out is trivial. Now, notice that statement 1 is routine by the inductive hypothesis. Choose a dynastic vertex that is not an ancestor of any dynastic vertex that is not crossed out. Now, look at its two children. Notice that one of these cannot be an ancestor of the vertex chosen in the previous step. By the inductive hypothesis, the chosen dynastic vertex still has $k+2$ family members that are not blue. Thus, our claim is proven. Since each dynastic vertex corresponds to $k+2$ different blue vertices, there must be at most $\frac{n}{k+2}$ dynastic vertices.

Suffices to prove for tree. Strong induct on a stronger bound of $\frac{n-(k+1)}{k+2}$. By extremal, take the root to be dynastic. Applying inductive hypothesis on the two children of the root yields the result.

First, we'll show the same result for a tree instead of a forest. This is sufficient because a forest is just composed with trees. We claim that there are at most $\tfrac{n-(k+1)}{k+2}$ dynastic vertices. The result is obviously true for $n\le 2k+2$. Let $n$ be the smallest positive integer such that there is a tree with more than $\tfrac{n-(k+1)}{k+2}$ dynastic vertices. Then, take the root and remove it. We have removed one dynastic vertex. Let there be $n_1$ and $n_2$ vertices in the resulting trees, then we have remaining \[\frac{n_1-(k+1)}{k+2}+\frac{n_2-(k+1)}{k+2}=\frac{n-2k-3}{k+2}\]and when we add back the one we removed, we are at $\tfrac{n-(k+1)}{k+2}$, absurd.

Very cool problem!

Claim: Take a rooted binary tree where every non-leaf has two successors. Then the number $L$ of leaves is greater than the number $N$ of non-leaves; that is, $L\ge N+1$. Proof: Use induction. Evidently this is true in the case of a single node; in all other cases, the tree can be split into: The root. The left subtree, with $L_1$ leaves and $N_1$ non-leaves. The right subtree, with $L_2$ leaves and $N_2$ non-leaves. Then by the inductive hypothesis we have \[L=L_1+L_2\ge (N_1+N_2)+2=N+1.\]Claim proven. Corollary: Take a rooted binary tree. Let $L$ be the number of leaves, or nodes with $0$ successors. Let $A$ be the number of nodes with $1$ successor. Let $B$ be the number of nodes with $2$ successors. Then $L\ge B+1$. Proof: Simple. Just "smooth" or reduce the tree down to the original claim by deleting nodes with $1$ successor. Reduce the forest to a single tree. Then let $S$ be the set of dynastic vertices $v$ such that no vertex in the subtree of $v$ is dynastic. Consider the subtree $T$ where the set of leaves of $T$ is equivalent to $S$. Then, following the notation of the corollary, we notice: All dynastic vertex not in $S$ is located in $T$, and has two successors in $T$, except: Some dynastic vertices have a dynastic vertex in one subtree and at least $k+1$ non-dynastic vertices in the other subtree. Removing the latter subtree strengthens the problem; we lose one dynastic vertex and at least $k+1$ non-dynastic vertices. Hence assume none of the second case occur. Now we are done: the number of dynastic vertices is less than $2|S|$ and yet there are at least $(2k+2)|S|$ non-dynastic vertices (there are at least $2k+2$ for each vertex in $S$). Hence at most $\frac{1}{k+2}$ vertices are dynastic. $\blacksquare$

frick me i knew induction worked but was too far into this sol to do it oopsy poopsy

The problem becomes quite straightforward once we consider the dual formation. We instead prove the following statement: if $G$ is a graph that has $d$ dynastic vertices, then $G$ has at least $d(k+2)$ vertices. This can be done by induction on $d$. The base case is clear. For the inductive step, there exists a dynastic vertex $v \in G$ such that no descendants of $v$ are dynastic. There must be at least $2k+2$ descendants of $v$; I claim we can remove any $k+2$ of them to create a graph $G'$ with $d-1$ dynastic vertices. Indeed, $v$ is no longer dynastic, and any dynastic vertex $w$ for which $v$ is a descendant remains dynastic, as $v$ still has $k$ descendants. Thus, $G'$ has at least $(d-1)(k+2)$ vertices by the inductive hypothesis, so $G$ has at least $d(k+2)$ vertices.

We show the bound for one tree, the generalization to the forest is obvious. Let a dynastic leaf be a dynastic vertex with no dynastic children, and a dynastic half be a dynastic vertex with exactly one dynastic child. Let a good vertex be a non-dynastic vertex that has at least $k + 1$ vertices in its subtree, clearly we can find (2*number of dynastic leaves + number of dynastic halfs) good vertices, none of whom are in each others subtree, each one corresponds to $k +1$ distinct vertices in the graphl. We can create the following bound: number of dynastic vertices + (2*number of dynastic leaves + number of dynastic halfs )* (k + 1) <= n Thus if we were to show 2*number of dynastic leaves + number of dynastic halfs >= number of dynastic vertices, we could establish the further bound number of dynastic vertices + number of dynastic vertices*(k + 1) <= n which is exactly what we desire. Observe the the set of dynastic vertices can be partitioned into several trees, each of whom is a binary tree with some subtrees removed. We show this for each individual tree by demonstrating the property holds for a binary tree and showing it holds as we delete each vertex (then summing gives the property holds over all dynastic vertices). It obviously holds for a full binary tree as twice the number of leaves is greater than the size of the whole tree, then removing a leaf can either change reduces the number of leaves by 1, either changes a normal vertex to a half or a half to a leaf, both of which combined decrease the left side by one, and decreases the total number of vertices by one, decreasing the right side by one, so the inequality always holds.