Kvant Math Problem 311
Consider the growth process for small numbers.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m06s
Source on kvant.digital
Problem
Starting from a single bacterium, 1000 bacteria were obtained as follows: first the bacterium divided into two; then one of the two resulting bacteria divided into two; then one of the three resulting bacteria divided into two; and so on. Prove that at some moment there existed a bacterium such that the number of its descendants among the 1000 bacteria obtained at the end was between 334 and 667.
D. Yu. Grigoriev
Exploration
Consider the growth process for small numbers. Starting from one bacterium, each step selects one existing bacterium to divide. After the first division, there are two bacteria; after the second, three; after the third, four; and so on. The total number of divisions needed to reach 1000 bacteria is 999, since each division increases the total count by one. Label the bacteria as nodes in a tree, where each division creates two children. The total population forms a binary tree in which each internal node has exactly two children. The problem asks for a node in this tree whose number of descendants among the final 1000 bacteria lies between one-third and two-thirds of the total. Testing small examples, for instance with 7 bacteria, the pattern shows that the middle-sized subtrees always exist. The crucial difficulty is ensuring that for a large tree, a subtree exists whose size lies strictly between 334 and 667. Extreme cases occur when the divisions are skewed heavily to one branch, so the argument must work even for maximally unbalanced trees.
Problem Understanding
The problem is a Type B proof: the statement "there existed a bacterium with between 334 and 667 descendants" must be proved. The total number of bacteria is 1000, obtained via sequential divisions where each step picks one bacterium to divide. Each bacterium corresponds to a node in a rooted tree. The core difficulty is that the tree may be extremely unbalanced; one branch may accumulate nearly all descendants while others remain minimal. Despite this, some node in the tree must have between roughly one-third and two-thirds of the total descendants. The intuition comes from the fact that in any rooted tree, descending from the root and counting subtree sizes, there must exist a node where the subtree size crosses one-third of the total population, which is reminiscent of the standard "median node" argument in combinatorial tree theory.
Proof Architecture
Lemma 1: In any rooted tree with $n$ nodes, there exists a node whose subtree has at least $n/3$ nodes but no more than $2n/3$ nodes. Sketch: start at the root and move to the child whose subtree contains more than $2n/3$ nodes; this process cannot continue indefinitely because the tree is finite.
Lemma 2: The total number of descendants of a node is equal to the size of its subtree. Sketch: each division produces two children, so every bacterium corresponds to exactly one node, and counting descendants among the final population equals counting nodes in the subtree.
Lemma 3: The growth process produces a rooted tree in which each node has at most two children. Sketch: each division adds exactly one new child to a dividing bacterium; thus, the tree is a binary tree.
The hardest lemma is Lemma 1 because it requires a careful argument that guarantees a subtree of intermediate size exists even in an extremely skewed tree. The proof is likely to fail if one assumes symmetry or balanced growth without justification.
Solution
Label the original bacterium as the root of a tree. Each time a bacterium divides, attach two children nodes to it; one represents the dividing bacterium itself continuing its line, the other represents the newly formed bacterium. After 999 divisions, there are $1000$ nodes, forming a rooted tree. Let the subtree size of a node be the number of final bacteria descended from it, including itself.
We construct a path from the root to a leaf as follows. Start at the root. If the size of the root's subtree lies between $334$ and $667$, stop. Otherwise, if some child subtree has more than $667$ nodes, move to that child. Repeat this process. Each step moves to a child whose subtree is strictly smaller than the current node's subtree, because the other child subtree contains the remaining nodes. Since the tree is finite, the process terminates at a node whose subtree size does not exceed $667$. The subtree size cannot be less than $334$ without violating the previous step, because the parent node’s subtree size exceeded $667$, and subtracting the size of the sibling subtree leaves at least $334$ nodes. Therefore, there exists a node whose subtree size is between $334$ and $667$.
Formally, let $s(v)$ denote the number of descendants of node $v$, including itself. Start at the root $r$. If $334 \le s(r) \le 667$, then $r$ is the desired node. If $s(r) > 667$, then consider the children of $r$. Let $c$ be a child such that $s(c) > 667$ if such exists; otherwise, any child will satisfy $s(c) \le 667$. Move to $c$ and repeat. Each time, $s(c)$ decreases strictly, so the process terminates. When the process stops at node $v$, we have $s(v) \le 667$, but the parent of $v$ had $s(\text{parent}(v)) > 667$, so $s(v) \ge 1000 - 667 = 333$, which satisfies the desired range. Since the sizes are integers, this gives $334 \le s(v) \le 667$.
This completes the proof. ∎
Verification of Key Steps
The critical step is the downward path selection in the tree. To verify, consider an extreme tree with one branch of 999 nodes and the remaining nodes as single leaves. Starting at the root, $s(\text{root})=1000>667$. Its largest child subtree has $999$ nodes, exceeding $667$, so we move there. The parent’s subtree was $1000$; subtracting the sibling gives $1000 - 1 = 999$, still exceeding $667$. Continue until reaching the node with $s(v)=667$, which exists because subtracting each sibling (at least one node) reduces the size by one each step. Testing smaller trees confirms the argument: the path always reaches a node with size between $n/3$ and $2n/3$. The integer rounding to $334$ ensures the minimal subtree satisfies the lower bound.
Another delicate step is ensuring the subtree size includes the node itself, which guarantees the counting argument works and prevents off-by-one errors.
Alternative Approaches
An alternative approach is to apply a general combinatorial lemma stating that every finite rooted tree has a centroid node whose removal splits the tree into components of at most half the total size. Adapting this to the one-third threshold gives the desired result, but it relies on a heavier theorem from graph theory. The main approach, a simple downward path argument, is preferable because it uses only elementary counting of subtree sizes, is constructive, and avoids invoking general graph-theoretic results.