0
$\begingroup$

How can I calculate the value of given node level, for example:

please invert the level

(let's use this image I found on Google Images and invert the level: starting at bottom 0..1..2..3..4)

Knowing that each node pays to the parent of the parent, let's call "grandfather". except by the nodes which has as parent the root node, these doesn't pay!

When all my children of children nodes (let's call grandsons) pays then I pay for my "grandfather".

Assuming that each reference to "pay" is in value of 7USD, how can i calculate the value/balance of each node based on their level ?

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose that the root is on level $n$. If $n=0$ or $n=1$, none of the nodes pays or receives anything, so each node has a balance of $0$. (To avoid clutter I omit the dollar sign.) If $n=2$, the $4$ nodes on level $0$ pay $7$ each and receive nothing, so they end up with a balance of $-7$; the $2$ nodes on level $1$ neither pay nor receive and have a balance of $0$; and the root node receives $4\cdot7=28$ and pays nothing, for a balance of $28$. Similarly, if $n=3$, the $8$ nodes on level $0$ and the $4$ nodes on level $1$ end up with a balance of $-7$ each, while the $2$ nodes on level $2$ and the root node end up with a balance of $28$ each.

Now assume that $n\ge 4$. Then each of the $2^n$ nodes on level $0$ and the $2^{n-1}$ nodes on level $1$ pays $7$ and receives nothing for a balance of $-7$. If $2\le\ell\le n-2$, each node on level $\ell$ receives $4\cdot7=28$ from its four grandchildren and pays $7$ to its grandparent, so it ends up with a balance of $21$. Finally, each node on levels $n$ and $n-1$ receives $4\cdot7=28$ from its grandchildren and pays nothing, ending with a balance of $28$.

As a quick partial check, note that there are $2^{n-\ell}$ nodes on level $\ell$, so for $n\ge 4$ the sum of the final balances of all nodes is

$$\begin{align*} -7\left(2^n+2^{n-1}\right)+21\sum_{\ell=2}^{n-2}2^{n-\ell}+28(2+1)&=-7\left(2^n+2^{n-1}\right)+21\sum_{k=2}^{n-2}2^k+3\cdot28\\ &=-21\cdot2^{n-1}+21\left(2^{n-1}-4\right)+4\cdot21\\ &=0\;, \end{align*}$$

just as it should be: there is no net flow of money into or out of the system.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .