In a group of children, each child has a certain number of pencils from $1$ to $n$. If the number of children who have i or more pencils is $2^{n-i}$, for $i=1,2,3, \ldots,n$ and the total number of pencils is $511$, find the maximum number of pencils with any child.
My attempt:-
Number of children with 1 pencil = $2^{n-1}-2^{n-2}=2^{n-2}$
Number of children with 2 pencils = $2^{n-2}-2^{n-3}=2^{n-3}$
.
.
.
Number of children with n pencils = 1
Now, total number of pencils = $1 \cdot 2^{n-2} + 2 \cdot 2^{n-3} +….+ (n \cdot 1) = 511$
I am not able to understand how to solve it from here.
As per the solution given by the author (screenshot):
The number of children with 1 or more pencils is $2^{n-1}$, (i.e. those children who have one or more pencils)
The number of children with 2 or more pencils is $2^{n-2}$ (i.e. those children who have 2 or more pencils) and so on.Thus the total number of pencils that the children have is
$$ 2^{n-1}+2^{n-2}+2^{n-3}+ \dots + 2^{n-n} = 2^{n-1} = 511 \implies n=9 $$
i.e., the maximum number of pencils with any child (n) is 9.
I am unable to understand how that that sum equals to the total number of pencils?
Best Answer
So, you found that there are
$2^{n-2}$ children with $1$ pencil,
$2^{n-3}$ children with $2$ pencils,
…
$2^1$ children with $n-2$ pencils,
$2^0$ children with $n-1$ pencils,
and $1$ kid with $n$ pencils.
The overall number of pencils is then $$1\cdot2^{n-2}+2\cdot2^{n-3}+…+(n-1)\cdot2^0+n.$$
Let us calculate this sum. We must add a lot of powers of $2$. Here is a trick how to visualize it in a convenient way. Arrange them in a triangle:
$$\begin{array}{ccccccc} 2^{n-2} & 2^{n-3}& 2^{n-4} & 2^{n-5} & … & 2^1&2^0 \\ & 2^{n-3}& 2^{n-4} & 2^{n-5} & … & 2^1& 2^0 \\ & & 2^{n-4} & 2^{n-5} & … & 2^1& 2^0 \\ & & & 2^{n-5} & … & 2^1& 2^0 \\ & & & & … & … & … \\ & & & & & 2^1 & 2^0\\ & & & & & & 2^0 \end{array}$$
It is easy to calculate the sum in each horizontal row (it’s just a sum of geometric progression: $2^{k}+…+2^2+2^1+2^0=2^k-1$):
$$\begin{array}{ccccccc|c} 2^{n-2} & 2^{n-3}& 2^{n-4} & 2^{n-5} & … & 2^1&2^0 & 2^{n-1}-1\\ & 2^{n-3}& 2^{n-4} & 2^{n-5} & … & 2^1& 2^0 & 2^{n-2}-1\\ & & 2^{n-4} & 2^{n-5} & … & 2^1& 2^0 & 2^{n-3}-1\\ & & & 2^{n-5} & … & 2^1& 2^0 & 2^{n-4}-1\\ & & & & … & … & … &…\\ & & & & & 2^1 & 2^0& 2^2-1\\ & & & & & & 2^0& 2^1-1 \end{array}$$
Now we summarize the last column. It is again the sum of a geometric progression, minus the number of horizontal rows which is equal to $n-1$: $$2^n-1-1-(n-1).$$
Since there are $511$ pencils, we have (don’t forget the $+n$): $$2^n-1-1-(n-1)+n=511$$
$$2^n=512.$$
Indeed, $$n=9.$$