edited by
1,905 views
10 votes
10 votes

Consider a complete binary tree of height $n$, where each edge is one Ohm resistor. Suppose all the leaves of the tree are tied together. Approximately how much is the effective resistance from the root to this bunch of leaves for very large $n$?

  1. Exponential in $n$.
  2. Cubic in $n$.
  3. Linear in $n$.
  4. Logarithmic in $n$.
  5. Of the order square root of $n$.
edited by

1 Answer

Best answer
5 votes
5 votes
Sum of resistors when in series $r_{serial} = r_{1}+r_{2}$

Sum of resistors when in parallel, $\dfrac{1}{r_{parallel}}= \dfrac{1}{r1} + \dfrac{1}{r2}$
                                             
$\implies r_{parallel} = \dfrac{r_{1}\cdot r_{2}}{r_{1}+r_{2}}$

Every node siblings are in parallel and the sum of each level are in series and all node of the last level are tied so all are in series.

So, total sum of resistor $=$ root $ + $ total of level $2 \ + $ total of level $3 + \ldots + $ total of level $n-1 +$ total of level $n$ (in series)
$\begin{array}{cc}\textbf{ Level}&\textbf{Number of nodes}\\ \hline
1&1 (2^0)\\
2&2 (2^1)\\
3      &              4  (2^2)\\4                     &            8 (2^3)\\.\\.\\n-1                    &          2^{n-2}\\n                         &        2^{n-1}\\
\end{array}$

So, total sum of resistor $=$ root $+$ total of level $2 \ +$ total of level $3 + \dots.+$ total of level $n-1 + \ $ total of level $n$ (series)
$\qquad= 1 + \frac{r}{2} + \frac{r}{4} + \frac{r}{8} + \frac{r}{16} + \dots + \frac{r}{2^{n-2}} + (\underbrace{r + r + r + r + \dots +r}_{2^{n-1}  \ times}) $ (here $r = 1)$
$\qquad = 1 + \left\{ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n-2}}\right\}(\text{decreasing GP}) + {(\underbrace{1+1+1+\ldots+1}_{ 2^{n-1}  \ times})} $

$\qquad \approx (2^n)  \ \text{approx}$

Option $(A)$ is the correct choice.
selected by
Answer:

Related questions

4 votes
4 votes
2 answers
2
makhdoom ghaya asked Oct 30, 2015
1,019 views
Walking at $4/5$ is normal speed a man is $10$ minute too late. Find his usual time in minutes.$81$$64$$52$$40$It is not possible to determine the usual time from given d...