Sean $a_1$, $a_2$, $\dots$, $a_{2^{k+1}}$ numeros reales positivos tales que para
cada $i$, $i < a_i \leq i+1$. Considera para cada $i$, la caja de base cuadrada de
$1 \times 1$ y de altura $\frac{1}{a_i}$.
Muestra que con estas $2^{k+1}$ cajas es
posible llenar al menos $k+1$ cajas rectangulares de base $1 \times 1$ y altura
$\frac{1}{2}$.
Muestra que con las $2^{k+1}$ cajas no es posible llenar $k+1$ cubos de lado $1$.
miércoles, 23 de febrero de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
10 comentarios:
Con "llenar" se refieren a que si agarro una caja de 1/3 de alto y otra de 1/6 de alto, se llena justamente? o pueden pasarse por algo? además, deben llenarse por separado no? es decir, si sobra de una no podemos darle el sobrante a otra o si?
en la primera es demostrar que existe una particion de las cajas en k+1 conjuntos tales que cada conjunto de la particion tiene volumen mayor a 1/2. O sea partir el conjunto {1/a_i} en k+1 conjuntos con cada uno suma mayor o igual a 1/2?? y en la segunda es que no se puede hacer esa particion pero que cada conjunto sume al menos 1??
Bueno si es como digo, entonces para la primera parte para la r-esima caja tomamos $a_i$ para i entre $2^{r-1}$ y $2^r-1$ luego como $a_i\le i+1$
entonces $1/a_i\ge \frac{1}{i+1}$ entonces todas esas fracciones son mayores o iguales a
$\frac{1}{2^r}$ y son $2^{r-1}$ fracciones, entonces su suma es mayor a un medio, y si nos fijamos esos rangos hacen una particion de los $a_i$ y son k+1 rangos, y su suma es mayor o igual a 1/2 para cada conjunto. y ya llenan cada caja de 1X1X1/2
para lo segundo basta ver que la suma de los reciprocos de $a_i$ es menor a k+1. Pero $i<a_i$ entonces $\frac{1}{a_i}<\frac{1}{i}$ luego igual partimos las i's en los mismos rangos que para el primer inciso. pero ahora los $a_i$ de las i en ese rango son menores a $\frac{1}{2^{r-1}}$ y son $2^{r-1}$ numeros, entonces su suma es menor a 1 y son k+1 rangos, entonces la suma total de los numeros $a_i$ es menor a k+1, que ya vimos que es suficiente. (De hecho probe que 1/1+1/2+...+1/2^(k+1)<k+1.
Veamos que para este problema, diremos que $a_{i}=i+1-b_{i}$ dónde $1>b_{i}\geq 0$ para toda $i$. Ahora veamos que lo que queremos hacer es encontrar $k+1$ conjuntos de valores de $a_{i}$'s de manera que todos los valores en el subconjunto cumplan que la suma de sus inversos multiplicativos son mayores a $\frac{1}{2}$. Como el inverso multiplicativo de éstos decrece conforme su valor incrementa, los valores de sus inversos multiplicativos son los más pequeños (viendo el caso extremo que nos dificulta más las cosas) cuando $b_{i}=0$ para toda $i$, por lo tanto consideraremos $a_{i}=i+1$ para toda $i$.
Con este nuevo contexto, podemos ver que tenemos las siguinetes alturas: $\frac{1}{2}$, $\frac{1}{3}$,..., $\frac{1}{i}$,..., $\frac{1}{2^{k+1}+1}$. Para probar el problema, probemos por inducción que sirve hasta cierto $2^{n}$ y veamos que funciona para $2^{n+1}$ y no sólo eso, sino que siempre nos queda libre el último término de la lista. Nuestro caso base es $n=1$ en el cual es claro que el primero se pasa de $\frac{1}{2}$ y por lo mismo el segundo nos queda libre. Ahora sí supongamos que funciona hasta cierto $2^{n}$ y veamos que también funcionará para $2^{n+1}$. Por nuestra hipótesis, si logramos sumar al menos $\frac{1}{2}$ con los valores del $2^{n}$avo hasta el penúltimo, acabaremos, y pues esto significa que debemos probar que $\frac{1}{2^{n}+1}+ \frac{1}{2^{n+2}+...+ \frac{1}{2^{n+1}} \geq \frac{1}{2}$, y como cada término de la izquierda es mayor estricto al último (excepto el último, que es igual a sí mismo), que es $\frac{1}{a_{2^{n+1}-1}}$ que como quedamos es mayor o igual a $\frac{1}{2^{n+1}}$ y como son $2^{n}$ términos, podemos ver que $\frac{1}{2^{n}+1}+\frac{1}{2^{n+2}+...+\frac{1}{2^{n+1}}> 2^{n}\frac{1}{2^{n+1}}$ y éste último es $\frac{1}{2}$ entonces, acabamos nuestra inducción, por lo que siempre se puede hacer.
Ahora veamos que si se pudiera realizar la segunda parte, entonces significa que si sumásemos todos los números, nos debería dar por lo menos $k+1$, y suponiendo que se puede evitar los desperdicios o 'sobras' entonces se podría hacer lo que se nos pide. Veamos que esto no se puede para $k\geq 2$. Primero veamos la siguiente desigualdad que obtenemos de los datos del problema: $\Sigma_{i=1}^{2^{k+1}} \frac{1}{a_{i}}<\Sigma_{i=1}^{2^{k+1}} \frac{1}{i}$. Si probamos que la segunda parte es menor a $k+1$ acabaremos, lo cual sale usando inducción con nuestro caso base de $k=2$ en donde es verdad puesto que suman $2+\frac{201}{280}$. Ahora supongamos que funciona hasta cierto $2^{n}$ veamos que para el siguiente también, para esto veamos que basta probar que $\Sigma_{i=2^{n}+1}^{2^{n+1}} \frac{1}{i}<1$ y por la hipótesis de inducción acabaríamos, pero pues de manera similar a lo que hicimos en el inciso anterior, cada uno es menor al primero (excepto el primero que es igual a sí mismo) y son $2^{n}$ números, entonces $\Sigma_{i=2^{n}+1}^{2^{n+1}} \frac{1}{i}<\frac{2^{n}}{2^{n}+1}<1$ así que ya está probado. Ahora veamos que si $k=0$ pues sí funciona el segundo inciso en algunos casos, mientras que si $k=1$ no funciona porque como los valores deben estar separados en dos conjuntos, y como $\frac{1}{a_{1}}<1$ entonces, $\frac{1}{a_{1}}$ está con algun otro número y de ahí vemos que los otros dos números no pueden sumar 1 en ningún caso, ya que lo idóneo sería que quedaran $\frac{1}{a_{2}}$ y $\frac{1}{a_{3}}$ juntos, pero sus máximos valores son respectivamente menores a $\frac{1}{2}$ y $\frac{1}{3}$ y la suma es menor a $\frac{5}{6}$ y no se puede, por lo que no se puede a menos que $k=0$ donde en algunos caso se puede y en otros no.
Para Jorge Chuck: no tienen que llenarse justamente, se pueden pasar. Las cajas no se pueden partir, asi que los sobrantes no se pueden usar.
Para Flavio: muy bien tu solucion. De hecho, lo que esta atras del problema es la divergencia de la serie armonica
Jorge Chuck, tu solucion esta muy larga, necesito tiempo para revisarla con cuidado
Para la primera parte haré lo siguiente:
Demostraré primero que: $a_{1}\leq2\Rightarrow\frac{1}{2}\leq\frac{1}{a_{1}}$; luego vemos que $a_{2},a_{3}\leq4\Rightarrow\frac{1}{4}\leq\frac{1}{a_{2}},\frac{1}{a_{3}}\Rightarrow\frac{2}{4}\leq\frac{1}{a_{2}}+\frac{1}{q_{3}}$, entonces funciona para el primer caso. Suponemos que para cierto k, $2^{k}-1$ es suficiente para llenar k cajas, entonces demostraré que $2^{k+1}-1$ es suficiente para llenar k+1 cajas. Para ello, veremos que con las cajas $a_{2^{k}},a_{2^{k}+1},...,a_{2^{k+1}-1}$ se puede llenar; para ello notamos que cada una de ellas contiene un número mayor o igual a $\frac{1}{2^{k+1}}$, y como son $2^{k}$ elementos, entonces la suma de todo ellos será mayor o igual a 1/2, con lo que queda demostrada la primera parte.
Para la segunda parte emplearé una idea similar.
Notamos que para k=1 no funciona, ya que: $\frac{1}{a_{1}}<1$, $\frac{1}{a_{2}},\frac{1}{a_{3}}<\frac{1}{2}$, y $\frac{1}{a_{4}}<\frac{1}{4}$. Entonces, observamos que en la caja que tenga a $a_{1}$ tendrá que haber otra caja ($a_{r}$) y las demás tendrán que sumar k, lo cual demostraré que no se puede. p.d. $(\sum_{i=2}^{2^{k}}\frac{1}{a_{i}})-\frac{1}{a_{r}}<k$, y para que lo que hay al lado derecho se mayorice, $r=2^{k}$. Entonces demostraré que $(\sum_{i=2}^{2^{k}-1}\frac{1}{a_{i}})<k$, y observamos ahora que $\frac{1}{a_{2^{s}}},\frac{1}{a_{(2^{s}+1)}},...,\frac{1}{a_{(2^{s+1}-1)}}<\frac{1}{2^{s}}\Rightarrow\sum_{i=2^{s}}^{2^{s+1}-1}\frac{1}{a_{i}}<\frac{2^{s}}{2^{s}}=1$, y si variamos s de 1 hasta k-1, tendremos lo que queremos, que $(\sum_{i=2}^{2^{k}-1}\frac{1}{a_{i}})<k$, por lo tanto no se puede construir de tal manera que se cumpla lo que pide el problema.
a) Llamemos "cajas unitarias" a aquéllas con base $1 \times 1$. En primer lugar, veamos que $\frac{1}{a_i}\geq\frac{1}{i+1}$ para toda $i$. Es claro que la caja unitaria de altura $a_1$ puede llenar una caja unitaria de altura $\frac{1}{2}$. Ahora, demostraremos que cualquier caja unitaria de altura $\frac{1}{2}$ se puede llenar con la suma de las cajas unitarias de alturas $\frac{1}{2^{k}+1}$,$\frac{1}{2^{k}+2}$,...,$\frac{1}{2^{k+1}}$ para toda $k$. Para k=1 es obvio que se cumple. Ahora, para $k>1$, por desigualdad media armónica-aritmética tenemos que:
$\frac{2^k}{\frac{1}{2^{k}+1}+\frac{1}{2^{k}+2}+...+\frac{1}{2^{k+1}}}\leq\frac{2^{k}+1+2^{k}+2+...+2^{k+1}}{2^{k}}=\frac{2(2^{k+1}+2^{k}+1)}{2^{k}}$ $\Rightarrow\sum_{i=2^{k}+1}^{2^{k+1}}\frac{1}{i}\geq\frac{2^{2k-1}}{2^{k+1}+2^{k}+1}$, y $\frac{2^{2k-1}}{2^{k+1}+2^{k}+1}\geq\frac{1}{2}\Leftrightarrow 2^{2k}\geq 2^{k+1}+2^{k}+1$, pero $2^{2k}>2^{k+1}+2^{k}\Leftrightarrow 2^{k}>3$,lo cual es cierto ya que $k>1$. Es fácil ver por qué con esto ya acabamos la primera parte.
b) Cabe aclarar que para $k=0,1$ no cumple el problema. Es fácil ver que $k=2$ sí cumple. Ahora, tenemos que $\frac{1}{a_i}<\frac{1}{i}$ y también que $\frac{1}{2^{n}+1}+\frac{1}{2^{n}+2}+...+\frac{1}{2^{n+1}}<\frac{1}{2^{n}+1}+\frac{1}{2^{n}+1}+...+\frac{1}{2^{n}+1}=\frac{2^{n}}{2^{n}+1}<1$. Como desde $k=2$ se cumple, usando lo que acabamos de obtener es fácil ver que todo $k>2$ cumplirá.
Publicar un comentario