For iteration $i=0$, there exists one node on $(0,0)$. For the next, and all subsequent iterations, nodes can be placed by the following rule. If there exists a node on $(a,b)$, then one can choose to remove that node and add nodes at points $(a+1,b)$ and $(a,b+1)$.
If diagonal $m$ be defined by $a+b+1=m$, generalize how many iterations are required for the first $n$ diagonals to contain no nodes. Further, find the maximum number of diagonals for which there exist no nodes in the diagonal or in lesser diagonals.
I found this problem in the Hungarian Problem Book IV. Currently, I am unable to compute by hand any diagonal $n\ge 3$, so I'm unable to find a pattern that way.
I was thinking it could be mapped onto some form of binary tree, and thus I would be able to find some Catalan number that would fit the pattern, but I wasn't able to do this either.
Thank you in advance for your help!
We can assign a node at location $(a,b)$ a weight of $2^{-(a+b)}$, so that every time we make a move, we replace a node by two nodes of half the weight, and total weight is preserved.
Then at step $i=0$, the total weight is $1$. The total weight of all possible nodes $(a,b)$ with $a \ge 0$ and $b\ge 0$ is $$\sum_{a=0}^\infty \sum_{b=0}^\infty 2^{-(a+b)} = \left(\sum_{a=0}^\infty 2^{-a}\right) \left(\sum_{b=0}^\infty 2^{-b}\right) = 2\cdot 2 =4.$$ The total possible weight along diagonals $1, 2, 3, 4$ can be computed as $1, 1, \frac34, \frac12$ (in general, the total weight along diagonal $m$ is $\frac{m}{2^{m-1}}$, beacuse there are $m$ nodes with weight $\frac1{2^{m-1}}$ each on that diagonal).
So, in particular, it is impossible to clear all four diagonals $1, 2, 3, 4$, because the entire infinite grid remaining has total weight $4 - 1 - 1 - \frac34 - \frac12 = \frac34$, which is less than the starting weight of $1$.
In fact, it is also impossible to clear the diagonals $1, 2, 3$, though we have to reason more carefully. The problem is that we can never have more than one node at a location $(a,0)$, for any $a$: the only way that such a node can be created destroys a node at location $(a-1,0)$. Similarly, we can never have one more node at a location $(0,b)$, for any $b$.
Although the total weight of all possible nodes $(a,b)$ with $a+b \ge 3$ (clearing diagonals $1,2,3$) is $\frac54 > 1$, we can actually only have one of the nodes $\{(3,0), (4,0), (5,0), \dots\}$. We might as well have node $(3,0)$, which has the greatest possible weight. This loses us a total of $2^{-4} + 2^{-5} + 2^{-6} + \dots = \frac18$ weight. Similarly, we lose $\frac18$ weight by noticing that if we have node $(0,3)$, we can't have nodes $(0,4), (0,5), (0,6), \dots$.
So actually, the maximum weight we can have on nodes $(a,b)$ with $a+b \ge 3$ is $1$ - and that requires infinitely many nodes. At any finite step, we can only have weight $<1$ on those nodes, and therefore there must still be nodes $(a,b)$ with $a+b<3$. Therefore, we can never clear the first three diagonals.