La comunidad de olímpicos, ex-olímpicos, entrenadores y seguidores de la Olimpiada en Chihuahua, wherever they are in the world.
Por supuesto cualquier olímpico mexicano (para que parar ahí, de todo el mundo pues), esta invitado a comentar.
sábado, 29 de septiembre de 2012
Problema del dia, Combinatoria (29 de septiembre)
Se dan 101 rectángulos de lados enteros menores o iguales a 100. Por demostrar que hay tres rectángulos A, B y C que cumplen que A cabe dentro de B y B cabe dentro de C.
Para que el triangulo $X$ no este dentro de $Y$ y vice versa, la base de $X$ debe de ser mayor a la de $Y$ y la altura de $Y$ mayor que la altura de $X$. La maxima cantidad de veces que podemos hacer esto es $50$ porque si empezamos con: $100(1)$ $99(2)$ $98(3)$ . . . $52(49)$ $51(50)$ solo lo podremos hacer 50 veces antes de que se comience a repetir. Entonces sabemos que la maxima cantidad de rectangulos que podemos hacer sin que uno este dentro del otro es de 50. Cuando llevemos 100, todos los rectangulos podran estar adentro de otro o tendran uno que este adentro. Entonces llevaremos 100 rectangulos, pero al hacer el numero 101, estaremos seguros de que ese estara adentro de uno de los primeros 50 o de los 2dos 50. Y sabemos que ese ya tiene otro rectangulo adentro o esta adentro de un rectangulo asi que habremos encontrado $A$, $B$ y $C$.
Para que un rectángulo A con dimensiones b y h contenga a otro con dimensiones c y j, se debe de cumplir que b>=c y h>=j. Luego, para que un rectángulo no contenga a otro no viceversa, se debe de cumplir que b>c,hj. Luego vemos que el máximo número de rectángulops que se puede formar sin que uno contenga al otro son 50 y son de la forma: 100(1) 99(2) 98(3) . . . 51(50) Ya que cualquier otra configuración nos daría un número menor de rectángulos. Luego nos fijamos en los siguientes 50, y como tampoco queremos que haya algún par de rectángulos tal que uno contenga al otro, éstos tendrán la misma configuración, con lo cual ya tenemos 50 parejas de rectángulos que se contienen. Por último tenemos un rectángulo que tendrá alguna de sus dimensiones igual a otro ya existente, por lo tanto alguno contendrá al otro, con lo cual aseguramos la existencia de A,B Y C.
tienes que si no quieres que tres rectangulos no esten dentro de cada uno entoces deben de tener diferente base y diferente altura y tienes que eso solo se puede con $50$ diferentes que son $100(1),99(2),98(3),...,53(48),52(49),51(50)$ y solo se pueden esos y tienes que ya a los $100$ va a ver almenos $2$ repetidos por casillas y a los $101$ va a ver minimo $3$ repetidos igual por casillas
primero me fijo en que para q un rectangulo contenga a otro de medidas $x*y$ las medidas del grande deven de ser un lado l tal que $l\ge x$ y otro lado j tal que $j\ge y$, la cantidad de rectangulos que podemos formar tales que ningun rectangulo contenga a otro que solo serian 50 : $1,100$ $2,99$ $3,98$ $\cdots$ $50,51$ y nos fijamos que cualquier otras dimensiones van a cumplir con lo que pusimos arriba y es lo que no qeremos entonces nos fijamos que si son 100 rectangulos por casillas uno se va a repetir al menos dos veses y como son 101 se va a cumplir en 3 rectangulos.
Primero me fijo que si hay dos rectangulos del mismo tamaño de altura o base uno va a caber dentro del otr por lo tanto elimino estos caso, y solo me quedand cuando las alturas y las bases no se re piten elprimero es de 100*1,99*2,......51*50 entonces hay 50 casos posibles pot=r casillas se que si hay 100 rectangulos van a ver minimo 2 que quepan dentro del otro pero ya que son 101 van a ver minimo 3 que cumplan.
Hacemos $(a_i,b_i)$ las dimensiones de cada rectángulo i. Tomamos las a's, como hay 100 posibles medidas y 101 a's alguna medida se repite, la de $a_i, a_j$ (SPDG: $b_i\ge b_j$) y el rectángulo i contiene al rectángulo j. Vemos que si hay otro rectángulo l con $a_l$ o $b_l$ igual a $a_i$, no importa la otra medida de los tres rectángulos uno va a contener a los otros dos y uno de esos va a contener al otro. Supongamos que no hay un rectángulo que cumpla eso. Vemos que si hay un rectángulo m tal que $a_m\ge a_i, b_m\ge b_i$ (o $b_m\ge a_i, a_m\ge b_i$) o $a_m\le a_j, b_m\le b_j$, o contiene a los dos o es contenido por el rectángulo j. Traté de llegar a una contradicción usando esto y suponiendo que no existen tres rectángulos que cumplan pero no llegué a nada...
Tenemos que a lo más debe haber 2 rectángulos, tal que uno contenga al otro, primero haremos la mayor cantidad de rectángulos tales que ninguno contenga a otro, esto sería haciendo rectángulos que satisfacen que cualesquiera 2 que tomemos, para que uno no contenga al otro, algun lado del rectángulo A sea mayor a los de B y el otro lado de A este entre el mayor y el menor lado de B, la mayor cantidad sería con las dimensiones: $1x100 , 2x99 , 3x98 , \cdots , 50x51$ de aquí que tendríamos 50 rectángulos, sean estos los rectángulos A, sin importar las dimensiones de los otros 50 rectángulos B que corresponden a cada A, sobrará uno, el cual cumplirá lo que dice el problema Q.E.D.
Vemos que para que $A$ no contenga a $B$ (llamemos $a_1$ , $a_2$ y $b_1$ , $b_2$ a las medidas de $A$ y $B$ respectivamente), se debe cumplir que $a_1>b_1$ y $a_2<b_2$ , y estos son los mayores casos posibles para que eso cumple: $1 , 100$ $2 , 99$ $\vdots$ $49 , 52$ $50 , 51$ Ahi son 50 rectangulos. Por casillas, si fueran $100$ , al menos uno se repetiria $2$ veces y con $101$ ya existirian rectangulos $A , B , C$ que cumplan.
si dos son del mismo tamaño uno cabe dentro del otro?
ResponderBorrarsi
ResponderBorrarhttp://www.facebook.com/photo.php?fbid=395834407154026&set=a.384382948299172.87730.100001824112299&type=1&theater
ResponderBorrarese acomodo cumple pero como me demuestras que yo genere un caso totalmente aleatorio que no cumpla?
BorrarPara que el triangulo $X$ no este dentro de $Y$ y vice versa, la base de $X$ debe de ser mayor a la de $Y$ y la altura de $Y$ mayor que la altura de $X$. La maxima cantidad de veces que podemos hacer esto es $50$ porque si empezamos con:
ResponderBorrar$100(1)$
$99(2)$
$98(3)$
.
.
.
$52(49)$
$51(50)$
solo lo podremos hacer 50 veces antes de que se comience a repetir. Entonces sabemos que la maxima cantidad de rectangulos que podemos hacer sin que uno este dentro del otro es de 50. Cuando llevemos 100, todos los rectangulos podran estar adentro de otro o tendran uno que este adentro. Entonces llevaremos 100 rectangulos, pero al hacer el numero 101, estaremos seguros de que ese estara adentro de uno de los primeros 50 o de los 2dos 50. Y sabemos que ese ya tiene otro rectangulo adentro o esta adentro de un rectangulo asi que habremos encontrado $A$, $B$ y $C$.
Para que un rectángulo A con dimensiones b y h contenga a otro con dimensiones c y j, se debe de cumplir que b>=c y h>=j. Luego, para que un rectángulo no contenga a otro no viceversa, se debe de cumplir que b>c,hj.
ResponderBorrarLuego vemos que el máximo número de rectángulops que se puede formar sin que uno contenga al otro son 50 y son de la forma:
100(1)
99(2)
98(3)
.
.
.
51(50)
Ya que cualquier otra configuración nos daría un número menor de rectángulos.
Luego nos fijamos en los siguientes 50, y como tampoco queremos que haya algún par de rectángulos tal que uno contenga al otro, éstos tendrán la misma configuración, con lo cual ya tenemos 50 parejas de rectángulos que se contienen.
Por último tenemos un rectángulo que tendrá alguna de sus dimensiones igual a otro ya existente, por lo tanto alguno contendrá al otro, con lo cual aseguramos la existencia de A,B Y C.
tienes que si no quieres que tres rectangulos no esten dentro de cada uno entoces deben de tener diferente base y diferente altura y tienes que eso solo se puede con $50$ diferentes que son $100(1),99(2),98(3),...,53(48),52(49),51(50)$ y solo se pueden esos y tienes que ya a los $100$ va a ver almenos $2$ repetidos por casillas y a los $101$ va a ver minimo $3$ repetidos igual por casillas
ResponderBorrarprimero me fijo en que para q un rectangulo contenga a otro de medidas $x*y$ las medidas del grande deven de ser un lado l tal que $l\ge x$ y otro lado j tal que $j\ge y$, la cantidad de rectangulos que podemos formar tales que ningun rectangulo contenga a otro que solo serian 50 :
ResponderBorrar$1,100$
$2,99$
$3,98$
$\cdots$
$50,51$
y nos fijamos que cualquier otras dimensiones van a cumplir con lo que pusimos arriba y es lo que no qeremos entonces nos fijamos que si son 100 rectangulos por casillas uno se va a repetir al menos dos veses y como son 101 se va a cumplir en 3 rectangulos.
Primero me fijo que si hay dos rectangulos del mismo tamaño de altura o base uno va a caber dentro del otr por lo tanto elimino estos caso, y solo me quedand cuando las alturas y las bases no se re piten elprimero es de 100*1,99*2,......51*50 entonces hay 50 casos posibles pot=r casillas se que si hay 100 rectangulos van a ver minimo 2 que quepan dentro del otro pero ya que son 101 van a ver minimo 3 que cumplan.
ResponderBorrarRumbo al nacional
ResponderBorrarHacemos $(a_i,b_i)$ las dimensiones de cada rectángulo i. Tomamos las a's, como hay 100 posibles medidas y 101 a's alguna medida se repite, la de $a_i, a_j$ (SPDG: $b_i\ge b_j$) y el rectángulo i contiene al rectángulo j. Vemos que si hay otro rectángulo l con $a_l$ o $b_l$ igual a $a_i$, no importa la otra medida de los tres rectángulos uno va a contener a los otros dos y uno de esos va a contener al otro. Supongamos que no hay un rectángulo que cumpla eso.
ResponderBorrarVemos que si hay un rectángulo m tal que $a_m\ge a_i, b_m\ge b_i$ (o $b_m\ge a_i, a_m\ge b_i$) o $a_m\le a_j, b_m\le b_j$, o contiene a los dos o es contenido por el rectángulo j.
Traté de llegar a una contradicción usando esto y suponiendo que no existen tres rectángulos que cumplan pero no llegué a nada...
Tenemos que a lo más debe haber 2 rectángulos, tal que uno contenga al otro, primero haremos la mayor cantidad de rectángulos tales que ninguno contenga a otro, esto sería haciendo rectángulos que satisfacen que cualesquiera 2 que tomemos, para que uno no contenga al otro, algun lado del rectángulo A sea mayor a los de B y el otro lado de A este entre el mayor y el menor lado de B, la mayor cantidad sería con las dimensiones: $1x100 , 2x99 , 3x98 , \cdots , 50x51$ de aquí que tendríamos 50 rectángulos, sean estos los rectángulos A, sin importar las dimensiones de los otros 50 rectángulos B que corresponden a cada A, sobrará uno, el cual cumplirá lo que dice el problema Q.E.D.
ResponderBorrarVemos que para que $A$ no contenga a $B$ (llamemos $a_1$ , $a_2$ y $b_1$ , $b_2$ a las medidas de $A$ y $B$ respectivamente), se debe cumplir que $a_1>b_1$ y $a_2<b_2$ , y estos son los mayores casos posibles para que eso cumple:
ResponderBorrar$1 , 100$
$2 , 99$
$\vdots$
$49 , 52$
$50 , 51$
Ahi son 50 rectangulos. Por casillas, si fueran $100$ , al menos uno se repetiria $2$ veces y con $101$ ya existirian rectangulos $A , B , C$ que cumplan.
http://www.facebook.com/photo.php?fbid=4695105379843&set=a.4586100454788.189149.1360331970&type=1&theater
ResponderBorrarhttp://www.facebook.com/photo.php?fbid=4695164781328&set=a.4586100454788.189149.1360331970&type=1&theater
Borrarla otra no se distinguia muy bien