Snip! Snip!

You're planting a tree, which sprouts 2 leaves on day 1. Each day, the tree branches out, doubling the number of leaves, but from day 2 on, you will trim one of the branches out, ceasing the leaves to grow on that branch. The number of leaves consequently runs as the day passes by as shown above.

On day 17, how many leaves will this tree have?


The answer is 65537.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

This tree branching of leaves is, in fact, an inverted version of Pascal's triangle, and with the condition of snipping one branch out everyday, the triangle will be adjusted as shown below:

As we can see, the number 1 on the far left can contribute only 1 new leaf to the right original Pascal's triangle due to the line is cut out (as the tree branch is trimmed). Therefore, from the first level, there are 1+1 leaves, and on the next level, the number of leaves will run as 2 n 1 2^{n-1} + 1 for any n t h n^{th} level (day n). For example, on day 3, there will be 2 3 1 2^{3-1} +1 = 4+1 = 5.

Hence, on day 17, there will be 2 17 1 2^{17-1} +1 = 65537 leaves.

Kishore S. Shenoy
Dec 19, 2015

Let S n S_n denote the number of leaves on n th ^\text{th} day.

We know, S n = 2 S n 1 1 S_n = 2S_{n-1}-1

Using Recurrence Relation, S n 2 S n 1 = 1 S n = c 2 n + 1 1 2 = c 2 n + 1 \begin{aligned}S_n-2S_{n-1}&=-1\\\Rightarrow S_n&=c2^n+\dfrac{-1}{1-2}\\&=c2^n+1\end{aligned}

Also, S 1 = 2 = c 2 1 + 1 c = 1 2 \begin{aligned}S_1 = 2 &= c\cdot2^1+1\\\Rightarrow c &= \frac12\end{aligned}

Thus on 17 th ^\text{th} day, number of leaves will be S 17 = 2 16 + 1 = 65537 \huge S_{17} = 2^{16}+1=65537

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...