3

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

user3263245
  • 33

2 Answers2

2

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.

aaaaaaaaaaaa
  • 459
  • @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
  • @user3263245 You should in general try to keep your questions within the relevant thread. You can edit clarifications into your question, and you can use comments to inquire further about specific answers. Also note that you can only mark one answer as accepted, you will have to chose the answer you think is best for that, if you later on mark another answer the first answer you marked will lose the mark. If your question has multiple good answers you can and should upvote all of them. – aaaaaaaaaaaa Nov 29 '14 at 22:49
0

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

RE60K
  • 17,716