Finding maximum number of pencils with any child in the problem

Question

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?

Answer 1

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.$$

Answer 2

First, an explanation for the given answer:

1. $2^{n-1}$ children have at least one pencil. Take this one pencil from all these children. You have $2^{n-1}$ pencils now.
2. Earlier, $2^{n-2}$ children had at least two pencils, and now they have at least one pencil. Take this one pencil from these $2^{n-2}$ children. Now you have $2^{n-1}+2^{n-2}$ pencils.
3. Now, $2^{n-3}$ children have atleast one pencil (others don't have one). Take one pencil from these students, you have $2^{n-1}+2^{n-2}+2^{n-3}$ pencils now.

In the end, when you have taken all the pencils from the children, you will have $2^{n-1}+2^{n-2} +\ldots +2^{n-n}$ pencils, and this is given $511 = 2^9 - 1$.

So, $n=9$, and one child can have at most $9$ pencils (the no. of children with ten or more is $2^{n-1} = 2^{9-10}$, which is impossible).

A visualisation of the above for $n=4$ (with 511 replaced by 15). The first row represents the students, and each column represents how many pencils they have. From the second row onwards, each row represents the pencils you take.

1 2 3 4 5 6 7 8
* * * * * * * *
        * * * *
            * *
              *

Clearly, the first $2^{n-2}$ (1-4) children have one pencil. Then, the next $2^{n-3}$ (5 and 6) children have two pencils, the next $2^{n-4}$ (7) has 3 pencils, and the last child has 4 pencils.

Now, you can consider each round as taking pencils from one row.

---

A solution using your method:
Some manipulation yields the sum already discussed above, so I won't take that method. Your sum is $$\frac n2+\sum_{i=1}^n i ( 2^{n-i} - 2^{n-i-1})$$ (Note that you need to consider this factor of $n/2$ as you have subtracted $n/2$ in the last summand, instead of zero). $$= \frac n2 + \sum_{i=1}^n i \cdot 2^{n-i-1}$$ $$= \frac n2 + \sum_{i=1}^n (n-i+1) \cdot 2^{i-2}$$ $$=\frac n2 +0.5(n+1)\sum_{i=1}^n 2^{i-1} - 0.5\sum_{i=1}^ni2^{i-1} \tag{*}$$ $$= \frac n2 + 0.5(n2^{n} - n +2^{n} -1) - 0.5(n2^n -2^n+1)$$ $$= 2^n-1$$ Note that the last summand in (*) can recalculated by derivating $\sum_{i=1}^n x^i = \frac{x^{n+1}-x}{x-1}$ (I have seen other precalculus methods too on this site).

The rest is same, you equate $2^n-1 = 511$.

Answer 3

Vasu, if you are having trouble with what DS said, try this version, too long for a comment.

Imagine you had a bell and every time you ring it the children with the highest number of pencils each drop 1 pencil. On the first ring 1 drops. The next time 2 drop. Then 4. Then 8. The total pencils is a sum of that sequence of powers of two. And you can see within even just the first few terms that the sum of n terms is always 1 less than the nth power of 2. 512 is the 9th power of 2, so on the ninth bell ring you arrive at 511. On the 10th ring you hear silence, for all the pencils have been dropped.