rompecabezas de cajas vacías

Question

El problema es

En una mesa se colocan inicialmente N cajas grandes vacías (se supone que son de tipo:1). Se selecciona un número desconocido de cajas (tipo:1) y en cada una de ellas se colocan K cajas más pequeñas (tipo:2). De nuevo se selecciona un número desconocido de cajas de tipo:2 y se colocan en su interior K cajas de tipo:3. Este proceso se repite T veces. Ahora se supone que una caja está vacía cuando no tiene cajas más pequeñas en su interior. Finalmente, una vez completados todos los procesos, hay F cajas vacías en total. Encuentra el número total de cajas en la mesa (dados N, K ,T y F).

Habría al menos N + x1 * K + x2 * K + .... + X(2 * T + 1) * K + X(2 * T + 2) * K cajas,

donde x1 son las cajas del tipo 1 en las que se han colocado K cajas más pequeñas del tipo 2 en el ensayo 1, de forma similar x2 son las cajas del tipo 2 en las que se han colocado K cajas más pequeñas del tipo 3 y así hasta el ensayo T.

He intentado solucionarlo pero me salen demasiadas variables y casos como colocar una caja dentro de una caja vacía o no vacía, etc. Entonces, ¿cómo puedo resolver esto?

Ejemplo: N = 11, K = 8, T = 2, F = 102 Respuesta: 115

Answer 1

Cada vez que se llena una caja, el número de cajas crece en $K$ y el número de cajas vacías crece en $K-1$ . Definimos $P$ para ser el número de veces que una caja se llena de cajas, y $A$ para ser el número total de cajas, ahora tenemos:

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

$$A=N+PK$$

Son dos ecuaciones con dos incógnitas, si resolvemos para $A$ eliminando $P$ nos encontramos con que:

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

Esta solución no funciona para $K=1$ Este caso es, por supuesto, irresoluble, ya que el número de cajas vacías no crece con el número de cajas.

El truco está en identificar la información innecesaria, en este caso que no importa a la ecuación en qué nivel se coloca un conjunto de cajas.

Answer 2

Supongamos que tenemos $n$ cajas y dejamos $f_1$ cajas vacías y poner $k$ cajas cada una en $n-f_1$ cajas y ahora tenemos $k(n-f_1)=k(-f_1+n)$ cajas más pequeñas, ahora las dejamos vacías $f_2$ cajas, por lo que tenemos $k(k(n-f_1)-f_2)=k(-f_2+k(-f_1+n))$ . Después de t tales operaciones tendremos $k(-f_t+k(-f_{t-1}+k(-f_{t-2}+k(...k(-f_1+n)))))$ . Así que las cajas vacías totales son: $$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)$$ Ahora las cajas totales son: $$\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}}$$

---

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