# empty boxes puzzle

The problem is

N large empty boxes (assume they are of type:1) are initially placed on a table. An unknown number of boxes (type:1) are selected and in each of them K smaller boxes (type:2) are placed. Again an unknown number of type:2 boxes are selected and K boxes of type:3 are placed inside. This process is repeated T times. Now a box is assumed to be empty when it has no smaller boxes inside it. Finally after all the processes are complete let there be F empty boxes in total. Find the total number of boxes on the table(given N, K ,T and F).

There would be at least N + x1 * K + x2 * K + .... + X(2 * T + 1) * K + X(2 * T + 2) * K boxes,

where x1 is the boxes of type 1 in which K smaller boxes of type 2 were placed in trial 1, similarly x2 is the boxes of type 2 in which K smaller boxes of type 3 are placed and then similarly upto trial T.

I tried solving this but I get too many variables and cases such as placing a box inside an empty or non-empty box etc. So, how do I solve this?

Example: N = 11, K = 8, T = 2, F = 102 Answer: 115

Suppose we have $n$ boxes and we leave $f_1$ boxes empty and put $k$ boxes each in $n-f_1$ boxes and now we have $k(n-f_1)=k(-f_1+n)$ smaller boxes, now we leave empty $f_2$ boxes, so we have $k(k(n-f_1)-f_2)=k(-f_2+k(-f_1+n))$. After t such operations we will have $k(-f_t+k(-f_{t-1}+k(-f_{t-2}+k(...k(-f_1+n)))))$. So total empty boxes are: $$f=f_1+f_2+k(-f_t+k(-f_{t-1}+k(-f_{t-2}+k(...k(-f_1+n)))))\\=k^tn+f_1(1-k^t)+f_2(1-k^{t-1})+f_3(1-k^{t-2})+...f_t(1-k)\\=k^tn+(1-k)[f_1(1+k+k^2+...k^{t-1})+f_2(1+k+k^2+...k^{t-2})+...f_t(1)]\\ \frac{f-k^tn}{1-k}=\sum_{i=1}^tf_i\left(\sum_{j=0}^{t-i}k^j\right)$$ Now total boxes are: $$\small n+k(-f_1+n)+k(-f_2+k(-f_1+n))+...k(-f_t+k(-f_{t+1}+k(-f_{t+2}+k(...k(-f_1+n)))))\\\small=n(1+k+k^2+...k^t)-[f_1(k+k^2+...k^t)+f_2(k+k^2+...k^{t-1})+f_3(k+k^2+...k^{t-2})+...f_t(k^{t-(t-1)})]\\ =n\frac{k^{t+1}-1}{k-1}-\sum_{i=1}^tf_i\left(\sum_{j=1}^{t-i+1}k^j\right)\\ \small=n\frac{k^{t+1}-1}{k-1}+\frac k{k-1}(f-k^tn)\\ =\frac{nk^{t+1}-n+kf-k^{t+1}n}{k-1}\\ =\huge\boxed{ \frac{kf-n}{k-1}}$$

For example $n = 11, k = 8, t = 2, f = 102$ $$\large \frac{8*102-11}{8-1}=\frac{816-11}{7}=\frac{805}{7}=115$$

• One of my assumptions is that you could place a box in a non empty box too. Sir, I would like to know your assumptions about the question. – user3263245 Nov 29 '14 at 10:55
• @user3263245 Isn't that clear? You can place exactly $K$ boxes in a box, or none at all. – aaaaaaaaaaaa Nov 29 '14 at 11:18

Each time a box is filled with boxes the number of boxes grow by $K$, and the number of empty boxes grow by $K-1$. We define $P$ to be the number of times a box is filled with boxes, and $A$ to be the total number of boxes, now we have:

$$F=N+P(K-1)$$

$$A=N+PK$$

That is two equations with two unknowns, if we solve for $A$ by eliminating $P$ we get:

$$A=N+K\frac{F-N}{K-1}$$

This solution does not work for $K=1$, that case is of course unsolvable as the number of empty boxes does not grow with the number of boxes.

The trick is to identify the unnecessary information, in this case that it doesn't matter to the equation on what level a set of boxes is placed.

• @eBusiness-Sir, I had some questions and I have mailed it to your gmail id. Would you mind looking it? – user3263245 Nov 29 '14 at 20:28