Prove that in any binary tree with $n \geq 1$ nodes, there exists a node with at least $\frac{n}{3}$ and at most $\frac{(2n + 1)}{3}$ descendants

Question

Prove that in any binary tree with $n \geq 1$ nodes, there exists a node with at least $\frac{n}{3}$ and at most $\frac{(2n + 1)}{3}$ descendants.

I'm a beginner in graph theory and I've no idea how to approach this problem, so any help would be appreciated.

Answer 1

Suppose that no such node exists. Since the number of descendants of a node decreases as we go down in the graph, we must eventually hit a node that has $>\frac{2n+1}{3}$ descendants, but its children have $<\frac{n}{3}$ descendants each. That is, the children have at most $\left\lceil\frac{n}{3}\right\rceil-1$ descendants and the parent has at least $\left\lfloor\frac{2n+1}{3}\right\rfloor+1$ descendants.

Using the former number, the parent has at most $2\left(\left\lceil\frac{n}{3}\right\rceil-1\right)+1$ descendants. For this to make sense, we must have

$$2\left(\left\lceil\frac{n}{3}\right\rceil-1\right)+1\geq\left\lfloor\frac{2n+1}{3}\right\rfloor+1.$$

Try showing that this is impossible for any value of $n$.