1ª Killer Maraton - Foro fmat.cl

Portal Matemático

¿Qué es FMAT?

Foro fmat.cl > Sector Preparación Olimpiadas > Sector Olímpico > Otros > Problemas Propuestos

10 Páginas:

« < 8 9 10

Closed Topic

Start new topic

1ª Killer Maraton, Solo para valientes

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	Oct 24 2006, 09:47 PM Publicado: #91
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(Cesarator @ Oct 24 2006, 10:01 PM) chuuu, sorry, nuevo error de tipeo, confundi el ultimo paralelogramo. Aca va el problem killer: $TEX: <br />{\bf Problema 21 (bis)} Sean $A,B,C,D,E$ y $F$ seis puntos en el espacio. Asumir<br />que los cuadril\'ateros $ABDE$, $BCEF$ y $CDFA$ son paralelogramos. <br /><br />Demostrar que los puntos medios de los lados $AB, BC, CD, DE, EF$ y $FA$ son coplanares.<br />$ screen.width0.6) {this.resized=true; this.width=screen.width0.4; this.alt='Pincha Aqui para ver esta imagen en su tamaÃ±o original';}" onmouseover="if(this.resized) this.style.cursor='hand';" onclick="if(this.resized) {window.open('http://img57.imageshack.us/img57/2962/geo3dda0.png');}" /> $TEX: \noindent<br />Por los paralelogramos dados, tenemos que $AB=DE,BC=EF,CA=FD$ luego, $ABC\cong DEF$. A demas, como $AB//DE,BC//EF,CA//FD$ (por los mismos paralelogramos) tenemos que $ABC,DEF$ estan en planos paralelos. Similarmente para $BDF,EAC$ concluimos que son congrunetes y estan en planos paralelos. Notemos que la mediana de $ABC$ paralela a $AC$ es paralela con la mediana de $EFD$ paralela a $FD$ porque son paralelas a los lados $FD$, $AC$ de $BDF,EAC$ los cuales son paralelos. similarmente concluimos que la medianas dibujadas de $AFE,CDE;BCD, ABF$ son paralelas a los lados de $BDF;EAC$ respectivamente, pero como ya vimos que estos dos ultimos triangulos son paralelos, todas las medianas son paralelas a los planos que contienen los triangulos $BDF,EAC$. Finalemnte como estan unidas ciclicamente por sus extremos, son coplanares. Para probar esto ultimo, suponga que $m_1,m_1$ son dos medianas paralelas a los planos de $BDF,EAC$ que comparten el extremo $M$, si no fuesen coplanares, entonces por cada una pasa un plano distinto $P_1\ne P_2$ paralelo a los $BDF,EAC$, de donde deducimos que $M$ esta en ambos planos, pero $P_1//P_2$ asi que $P_1=P_2$, contradiccion, asi que $m_1,m_2$ son coplanares. Por lo tanto, como todas las medianas del dibujo son coplanares, sus extremos tambien, lo que prueba lo pedido.$ Mensaje modificado por Pasten el Oct 24 2006, 11:39 PM -------------------- Pasten, un buen muchacho en quien confiar.

Cesarator	Oct 24 2006, 10:21 PM Publicado: #92
Invitado	CITA(Pasten @ Oct 24 2006, 10:47 PM) screen.width0.6) {this.resized=true; this.width=screen.width0.4; this.alt='Pincha Aqui para ver esta imagen en su tamaÃ±o original';}" onmouseover="if(this.resized) this.style.cursor='hand';" onclick="if(this.resized) {window.open('http://img57.imageshack.us/img57/2962/geo3dda0.png');}" /> $TEX: ...como estan unidas dos a dos por sus extremos, son coplanares.$ Justificar + esta parte Mensaje modificado por Cesarator el Oct 24 2006, 11:04 PM

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	Oct 24 2006, 11:40 PM Publicado: #93
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	Ok, ya esta -------------------- Pasten, un buen muchacho en quien confiar.

Cesarator	Oct 25 2006, 07:43 AM Publicado: #94
Invitado	$TEX: <br />{\bf Problema 22}. Demostrar que para cada entero $n>1$, existe un entero positivo<br />$p$ tal que $p^3+17$ es divisible por $3^n$ pero no por $3^{n+1}$.<br />$

Luffy Ver Perfil del Miembro Ver los mensajes de este miembro	Oct 28 2006, 11:05 PM Publicado: #95
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 556 Registrado: 16-August 06 Desde: Rio de Janeiro Miembro Nº: 1.950 Nacionalidad: Colegio/Liceo: Universidad: Sexo:	CITA(Luffy @ Oct 22 2006, 06:25 PM) $TEX: $\boxed{P_{17}}$$ $TEX: $a_{n+1}=a_n^2-ka_n+k$$ $TEX: $a_{n+1}-k = a_n(a_n-k)$$ Luego, sea $TEX: $m \neq n$$ ; digamos que $TEX: $m=n+k$$ : $TEX: $a_{n+k}-k= a_{n+k-1}(a_{n+k-1}-k)=a_{n+k-1}a_{n+k-2}(a_{n+k-2}-k)=...=a_{n+k-1}\cdot\cdot\cdot a_n(a_n-k)$$ Luego: $TEX: $a_m-k \equiv 0$ (mod $a_n$)$ Luego como $TEX: $a_n \equiv 1$ (mod k) $\Rightarrow$ $a_n= kp+1$$ $TEX: $a_m \equiv k$ (mod $a_n$)$ $TEX: $-a_mp \equiv -kp \equiv 1$ (mod $a_n$)$ Finalmente $TEX: $MCD(a_m;a_n)=1$$ Jajaja solo quiero aclarar un que tuve cuando puse ...digamos que $TEX: $m=n+k$$ ... la verdad es que ese $TEX: $k$$ no es el mismo $TEX: $k$$ del enunciado, es un numero cualquiera de hecho es probablemente distinto, pero le puse $TEX: $k$$ por la fuerza de la costumbre, pero la verdad es que me equivoque en nombrarla, podria haber puesto $TEX: $m=n+h$$ y la solucion seria aun correcta, pero fue la fueza de la costumbre . La acabo de revisar y veo que me equivoque en nombrarla jajaja, podria haber puesto cualquier letra pero tenia que ser justo la $TEX: $k$$ jajaja. Eso no mas PD: No edite directamente el mensaje porque ya paso la fecha para las segundas soluciones de ese problema , espero que se entienda la situacion Mensaje modificado por Luffy el Oct 28 2006, 11:07 PM

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	Dec 11 2006, 01:51 PM Publicado: #96
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(Cesarator @ Oct 25 2006, 08:43 AM) $TEX: <br />{\bf Problema 22}. Demostrar que para cada entero $n>1$, existe un entero positivo<br />$p$ tal que $p^3+17$ es divisible por $3^n$ pero no por $3^{n+1}$.<br />$ $TEX: \noindent<br />Se trabajara en enteros. Diremos que $q^m$ es potencia divisora exacta de $k$ si y solo si es la mayor potencia entera de $q$ que divide a $k$. A demas, usaremos la notacion $d'$ para denotar el elemento de $\{-1,0,1\}$ tal que $d\equiv d' (\mod 3)$.\\<br />\\<br />Hacemos la sustitucion $p=3x-2$ obteniendo que $p^3+17=9(3x^3-6x^2+4x+1)$, luego, basta probar el siguiente enunciado:\\<br />Para todo $n\in\mathbb{N}_0$, existe un $x$ tal que $3^n$ es potencia divisora exacta de $3x^3-6x^2+4x+1$. (1)\\<br />Procedemos a demostrarlo;\\<br />Lema 1: Si $MCD(3,b)=1$ la congruencia $br+c\equiv 0 (\mod 3)$ tiene solucion unica para $r\in\{-1,0,1\}$ (en adelante asuma que $r\in\{-1,0,1\}$).\\<br />Demostracion Lema 1:\\<br /> La congruencia es equivalente a $b'r\equiv -c' (\mod 3)$; si $b'=-1$ la unica solucion sera $r=c'$, mientras que si $b=1$ la unica solucion sera $r=-c'$<br />\\<br />Definimos los polinomios $P_n$ como sigue;\\<br />i)$P_0(x)=3^{u_0}x^3+3a_0x^2+b_0x+c_0, MCD(3,b_0)=1$\\<br />ii)Si $3\|P_n(3x+r)$ para ciertos $x,r:r\in\{-1,0,1\}$, entonces $P_{n+1}(x)=\frac{1}{3}P_n(3x+r)$$ $TEX: \noindent<br />Lema 2: Existe un unico $r\in\{-1,0,1\}$ tal que $3\|P_n(3x+r)$ para algun entero $x$, mas aun, para ese $r$ se cumple $3\|P_n(3x+r)$ para todo $x$ entero.\\<br />Demostracion Lema 2:\\<br />Asumamos que $P_n(x)$ es de la forma\\ <br />$P_n(x)=3^{u_n}x^3+3a_nx^2+b_nx+c_n$ \\<br />Definiendo recursivamente $u_0=1, u_{n+1}=u_n+2$ (notar que $u_n\ge1$) y asumiendo que $b_n'\ne 0, \forall n\in\mathbb{N}_0$ tenemos por un desarrollo algebraico que\\ <br />$P_n(3x+r)=3(3^{u_{n+1}}x^3+3a_{n+1}x^2+b_{n+1}x)+3(3^{u_n-1}r^3+a_nr^2+ \frac{1}{3}(b_nr+c_n))$\\<br />donde\\<br />$a_{n+1}=3(3^{u_n}r+a_n)\\<br />b_{n+1}=3^{u_n+1}r^2+6a_nr+b_n$\\<br />de donde se deduce que $3\|P_n(3x+r)\Leftrightarrow 3\|b_nr+c_n$ (2) pero ya se probo en el Lema 1 que si $b_n'\ne0$ entonces existe un unico $r\in\{-1,0,1\}$ para el cual $3\|b_nr+c_n$. Como (2) no depende de $x$ (mientras sea un entero) lo unico que resta para probar el Lema 2 es la forma $P_n(x)=3^{u_n}x^3+3a_nx^2+b_nx+c_n$ del polinomio y que $b_n'\ne 0, \forall n\in\mathbb{N}_0$. Ambos se prueban por induccion;\\<br />para lo primero tomando el r adecuado podemos definir $c_{n+1}=(3^{u_n-1}r^3+a_nr^2+ \frac{1}{3}(b_nr+c_n))$, ahora vemos que la existencia de dicha forma para $P_{n}(x)$ implica que existe para $P_{n+1}(x)$ y como para $n=0$ existe dicha forma por definicion, estamos listos.\\<br />Probamos ahora lo segundo;\\<br />$b_0'=0$ por definicion\\<br />$b_{n+1}=3^{u_n+1}r^2+6a_nr+b_n\equiv b_n (\mod 3)$\\<br />y la conclusion es directa.\\<br />Esto finaliza la demostracion del Lema 2.$ $TEX: Sea $r_n$ el unico elemento de $\{-1,0,1\}$ que hace que $P_n(3x+r_n)$ sea divisible en $3$ para todo $x$ entero, y $s_n,t_n$ los elementos del mismo conjunto que al remplazar $r_n$ hacen que $P_n(3x+r_n)$ no sea multiplo de 3, sin importar $x$. Esto siempre es posible por el Lema 2. Para restringirnos al problema, consideremos solo los $x$ tales que $3x+w>0:w=r_n,s_n,t_n$.\\<br />Entonces razonando inductivamente, iteramos en el resultado del Lema 2 obteniendo que debe existir algun $x_0$ para el cual, realizando las sustituciones adecuadas se puede llegar a\\<br />$P_0(3x_0+r_0)=3^nP_n(3x_n+w)$\\<br />donde de antemano hemos elegido $w$. Si nuestro $w$ era $r_n$ entonces podemos "pasar" al siguiente polinomio $P_{n+1}(3x_{n+1}+w)$, y si $w$ era $s_n$ o $t_n$ entonces $P_n(3x_n+w)$ no es divisible por 3. Esta ultima eleccion de $x_0$ demuestra el enunciado (1) pues dicho enunciado es un caso particular de lo que acabamos de demostrar, con $u_0=1,a_0=-2,b_0=4,c_0=1$.\\<br />Esto finaliza la demostracion.<br />$ Mensaje modificado por Pasten el Dec 12 2006, 08:38 AM -------------------- Pasten, un buen muchacho en quien confiar.

Cesarator	Dec 12 2006, 09:13 AM Publicado: #97
Invitado	... parece que me va a tomar su time corregir totalmente la sol de Pasten, asi que confiaremos en su prestigio y planteamos el problema que sigue. $TEX: <br />{\bf Problema 23}. Alicia y Benito juegan un juego en el que se recogen porotos por<br />turnos de un total inicial de $n$ porotos. El n\'umero de porotos que se toman en cada turno debe ser una unidad menos que un n\'umero primo. Gana el jugador que regoge el \'ultimo poroto.<br /><br />Alicia comienza el juego.<br /><br />Se pide demostrar que existen infinitos valores de $n$ para los cuales Benito tiene una estrategia ganadora. <br /><br />Juego ejemplo: para $n=17$, Alicia puede tomar $6$, dejando $11$. Entonces Bob podr\'{\i}a tomar $1$, y Alicia tomar las $10$ restantes para ganar.<br />$ Mensaje modificado por Cesarator el Dec 12 2006, 09:14 AM

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	Dec 12 2006, 08:10 PM Publicado: #98
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(Cesarator @ Dec 12 2006, 10:13 AM) ... parece que me va a tomar su time corregir totalmente la sol de Pasten, asi que confiaremos en su prestigio y planteamos el problema que sigue. $TEX: <br />{\bf Problema 23}. Alicia y Benito juegan un juego en el que se recogen porotos por<br />turnos de un total inicial de $n$ porotos. El n\'umero de porotos que se toman en cada turno debe ser una unidad menos que un n\'umero primo. Gana el jugador que regoge el \'ultimo poroto.<br /><br />Alicia comienza el juego.<br /><br />Se pide demostrar que existen infinitos valores de $n$ para los cuales Benito tiene una estrategia ganadora. <br /><br />Juego ejemplo: para $n=17$, Alicia puede tomar $6$, dejando $11$. Entonces Bob podr\'{\i}a tomar $1$, y Alicia tomar las $10$ restantes para ganar.<br />$ $TEX: \noindent<br />Diremos que un numero es "ganador" si Benito (B) tiene la estrategia ganadora con esta cantidad de porotos, y lo llamaremos "perdedor" si B no tiene una estrategia para ganar con esa cantidad inicial de porotos.\\<br />Sean $g_i$ y $p_i$ los i-esimos numeros ganadores y oerdedores respectivamente.<br />Claramente $p_1=1,p_2=2,g_1=3$ para los primeros numeros naturales. Asumamos que ambos jugadores son ex-olimpicos y poseen una inteligencia sobrehumana, en estas condiciones como en su turno cada jugador decide cuantos porotos sacar y el juego no puede terminar en empate ni es aleatorio, cada natural $n$ debe ser o ganador o perdedor.\\<br />Lema \\<br />$n$ es perdedor si y solo si se cumple alguna de las dos siguientes condiciones;\\<br />1) $n=g_i+p-1$\\<br />2) $n=p-1$\\<br />para algunos $i$ natural y $p$ primo.\\<br />Demostracion del lema \\<br />definiendo $g_0=0$ (lo que no altera en nada la situacion si consideramos que pierde quien en algun turno juega con $0$ porotos en la mesa) las condiciones 1) y 2) se reducen solo a que $n=g_i+p-1$ para algun $p$ primo e $i$ entero no negativo.\\<br />Primero, si $n=g_i+p-1$ entonces Alicia (A) en su turno puede sacar $p-1$ porotos y al siguiente turno hacer de cuentas que B comienza con $g_i$ porotos, lo que por definicion da la estrategia ganadora a A al invertirse los roles.\\<br />Ahora, si $n$ no es de la forma $g_i+p-1$ no importa que primo $p$ elija A, al restar $p-1$ porotos no dejara sobre la mesa una cantidad ganadora, luego, dejara una cantidad perdedora de porotos de la forma $p_i$ con la que comienza su turno B. Por definicion, al invertirse los papeles A no podra ganar con lo cual B tendra la estrategia ganadora. Esto prueba el lema.$ $TEX: \noindent<br />De lo anterior, vemos que los enteros ganadores estan caracterizados por no ser de la forma $g_i+p-1$.\\<br />Para probar la infinitud de los $g_i$ razonaremos por contradiccion;\\<br />Suponga que existe una cantidad finita de enteros $g_i$, entonces debe existir el mayor de ellos que sera $g$. \\<br />No es dificil ver que en el intervalo $I=[(g+2)!+2, (g+2)!+g+2]$ no hay primos con lo que obtenemos $g+1$ compuestos consecutivos. El primo mas grande antes del intervalo podria ser $(g+2)!+1$ asi el mayor numero perdedor que se puede obtener en $I$ con primos anteriores al intervalo es $g+((g+2)!+1)-1=(g+2)!+g$. Ahora, el menor numero primo posterior a $I$ podria ser $(g+2)!+g+3$ asi que el menor perdedor determinado por los primos posteriores a $I$ seria $g_0+((g+2)!+g+3)-1=(g+2)!+g+2$. Lo anterior asegura que $g!+g+1$ no puede ser perdedor, asi que es ganador lo que claramente contradice la maximidad de $g$.\\<br />Por lo tanto, hay infinitos numeros ganadores, como se pedia probar.$ -------------------- Pasten, un buen muchacho en quien confiar.

Cesarator	Dec 14 2006, 02:53 PM Publicado: #99
Invitado	... solo decir que el problema anterior pertenece a la competicion universitaria "Putnam". Vamos a uno que tenia para el curso intensivo de combinatoria et al del veranomatematico $TEX: <br />{\bf Problema 24}. Hay 99 estaciones espaciales. Cada par de estaciones est\'a conectada por un t\'unel. Hay 99 t\'uneles principales con tr\'ansito en ambos sentidos, pero totdos los otros t\'uneles pueden transitarse en solo un sentido. Un grupo de 4 estaciones se dir\'a {\em totalmente conectado} si se puede ir de cualquier estaci\'on del grupo a otra del grupo usando solamente los 6 t\'uneles que conectan las 4. <br /><br />Calcular el mayor n\'umero de grupos totalmente conectados que puede tener un sistema como el descrito.<br />$

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	Jul 23 2007, 12:40 AM Publicado: #100
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	$TEX: \noindent<br />Por comodidad diremos que un grupo conectado es un grupo bueno, en caso contrario es un grupo malo. Un tunel de un solo sentido entre $A$ y $B$ sera una "flecha" y lo denotamos $AB$, en ese orden. Al hablar de "grupo" entiendase un conjunto de $4$ estaciones dadas, en caso contrario se especificara como conjunto indicando cuantas estaciones estan.\\<br />Dado un grupo, una estacion es de entrada si a ella llegan $3$ flechas y es de salida si de ella salen $3$ flechas, en ambos casos diremos que la estacion es fea.\\<br />Resolveremos el problema para $2n+3$ estaciones, con $n\ge3$ (o sea, para los impares mayores que $8$), por lo que en adelante asuma que esa es la cantidad de estaciones.<br />$ $TEX: \noindent<br />Caractericemos los grupos malos:\\<br />Lema 1: Un grupo es malo ssi tiene una estacion fea.\\<br />Demostracion: Si tiene una estacion fea es obvio que es malo (si es de salida no se puede llegar a ella, si es de entrada no se puede salir de ella).\\<br />Supongamos que no tiene estaciones feas y que las estaciones del grupo son $A,B,C,D$. Tratemos de forzar que el grupo sea malo sin estaciones feas. Si un tunel es doble complicamos el asunto remplazandolo por una flecha asi que digamos que no hay tuneles dobles. Sin perder generalidad asuma que ya estan las flechas $AB,AC,DA$, hay dos casos:\\<br />i) Esta la flecha BC: entonces esta la CD y el grupo es bueno. No sirve\\<br />ii) Esta la flecha CB: entonces esta la BD y el grupo es bueno. Tampoco sirve\\<br />Como cualquier otro caso nos lleva a un grafo dirigido isomorfo (salvo quisas el sentido de todas las flechas simultaneamente) vemos que no se puede, probando el lema. \\<br />\\<br />Lema 2: Cada grupo tiene a lo mas una estacion de salida.\\<br />Demostracion: Un grupo tiene a lo mas $2$ estaciones feas (trivial), que seran necesariamente una de entrada y otra de salida, por lo cual cada grupo tiene a lo mas una estacion de salida.\\<br />$ $TEX: \noindent<br />Lema 3: Sean $a_i;1\le i\le k$ enteros no negativos con suma $mk$, $m\ge3$, entonces<br />$$\sum_{a_i\ge 3}\binom{a_i}{3}\ge k\binom{m}{3}$$<br />donde la suma corre sobre los $a_i$ que sean mayores o iguales que $3$.\\<br />Demostracion: Sea $t$ la cantidad de sumandos de la izquierda de la desigualdad. Notemos que <br />$$f(x)=\frac{x(x-1)(x-2)}{6}; x\ge 3$$<br />es convexa asi que<br />$$\sum_{a_i\ge 3}\binom{a_i}{3}=\sum_{a_i\ge 3}f(a_i)\ge tf\left(\frac{1}{t}\sum_{a_i\ge3}a_i\right)$$<br />$ $TEX: \noindent<br />pero $\sum_{a_i\ge 3}a_i$ se minimiza cuando los otros $a_i$ (los menores que $3$) se maximizan, es decir, cuando estos $k-t$ terminos valen $2$. Luego<br />$$\frac{1}{t}\sum_{a_i\ge3}a_i\ge \frac{k(m-2)}{t}+2\ge 3$$<br />y como $f(x)$ es creciente para $x\ge 3$ tenemos<br />$ $TEX: \noindent<br />$$\sum_{a_i\ge 3}\binom{a_i}{3}\ge tf\left(\frac{k(m-2)}{t}+2\right) =\frac{k(m-2)}{6}\left(\frac{k(m-2)}{t}+1\right)\left(\frac{k(m-2)}{t}+2\right)$$<br />Esta ultima expresion es decreciente para $t$ pero $t\le k$ asi que se minimiza tomando $t=k$.\\<br />Esto prueba la desigualdad.<br />$ $TEX: \noindent<br />Ya con estos $3$ lemas podemos continuar;\\<br />En total hay $\frac{(2n+3)(2n+2)}{2}-(2n+3)=n(2n+3)$ flechas.\\<br />Luego, si a cada estacion le asignamos uno de los numeros $s_i:1\le i\le 2n+3$ que en cada caso correspondera a la cantidad de flechas que salen de esa estacion (la estacion i-esima), vemos que $\sum s_i=n(2n+3)$.<br />Si por cada grupo posible contamos la cantidad de estaciones de salida (cada estacion puede ser contada tantas veces como grupos en los que figure como estacion de salida) vemos que este numero (que llamaremos $\sigma$) es<br />$$\sum_{s_i\ge 3}\binom{s_i}{3}$$<br />porque solo pueden considerarse estaciones de las que salen al menos $3$ flechas, y la estacion $i$-esima aparecera contada en $\binom{s_i}{3}$ grupos.\\<br />Aplicamos el Lema 3, tomando $k=2n+3,m=n,a_i=s_i$ y obtenemos <br />$$\sigma\ge (2n+3)\binom{n}{3}$$<br />Ahora de los lemas 1 y 2 se sigue que el total de grupos malos no puede ser inferior a $\sigma$, desigualdad que resulta ser bastante bruta porque ni siquiera consideramos las de llegada.<br />$ $TEX: \noindent<br />Tomemos las estaciones como vertices de un poligono regular de $2n+3$ lados y numeradas desde 1 en sentido antihorario. Los lados del poligono seran los tuneles dobles. Las diagonales seran flechas con sentido antihorario respecto del centro del poligono si en el semiplano determinado por esa diagonal y que no contiene el centro hay una cantidad impar de vertices. En otro caso la flecha va en sentido horario respecto del centro.\\<br />Si un grupo contiene estaciones consecutivas no es complicado ver que es bueno, asi que los grupos malos no tienen estaciones consecutivas y solo estan conectados por flechas.\\<br />Miremos la estacion 1. De ella salen $n$ flechas y llegan $n$. Luego, sera estacion de salida en $\binom{n}{3}$ grupos y sera de llegada en otros $\binom{n}{3}$.<br />$ $TEX: \noindent<br />Si miramos alguno de los grupos en los que es estacion de salida, por los sentidos de las flechas que dimos no es complicado ver (por paridad) que la primera estacion del grupo que nos encontramos al recorrer en sentido horario los vertices del poligono desde la estacion 1, es una estacion de llegada para el grupo (que llamaremos $L$). Esto porque todas las flechas del grupo que no tocan a la estacion 1 van en sentido antihorario respecto de dicha estacion.\\<br />En efecto, las flechas que salen de la estacion 1 llegan a las estaciones de numeracion impar (salvo la $2n+3$ que es contigua). Esto es trivial para las de numeracion impar menor que $\frac{1}{2}(2n+3)$ pues son flechas en sentido antihorario, para las otras como son en sentido horario pero ya pasaron de la mitad del poligono estaran ditigidas a la estacion 1. Ahora a la $L$ llega una flecha desde la estacion 1, pero las demas del grupo tienen igual paridad que esta estacion asi que, con un razonamiento similar al anterior, vemos que las flechas del grupo que tocan $L$ se dirigen a ella.$ $TEX: \noindent<br />Por lo tanto en cada grupo donde la estacion 1 sea de salida, habra otra estacion de llegada. Ocurre de forma similar para los grupos en los que la estacion 1 es de llegada, estos tendran necesariamente una estacion de salida. Asi del lema 2 vemos que cada vez que la estacion 1 es fea, contamos un grupo malo pero cada uno de estos grupos tiene otra estacion fea asi que al repetir el proceso con las demas estaciones, cada grupo malo sera contado 2 veces. A demas esto es para todos los grupos malos, por el lema 1.\\<br />Como la numeracion de las estaciones fue arbitraria, esto ocurre con las $2n+3$ estaciones.\\<br />Luego, esta configuracion nos da <br />$$\frac{1}{2}(2n+3)\left(\binom{n}{3}+\binom{n}{3}\right)=(2n+3)\binom{n}{3}$$<br />grupos malos, que es el minimo posible<br />$ $TEX: \noindent<br />Por lo tanto el total de grupos buenos sera a lo mas<br />$$\binom{2n+3}{4}-(2n+3)\binom{n}{3}$$<br />tomando $n=48$ obtenemos $\binom{99}{4}-99\binom{48}{3}$, lo que se pedia.\\<br />\\<br />Saludos<br />$ -------------------- Pasten, un buen muchacho en quien confiar.

« Posterior · Problemas Propuestos · Anterior »

10 Páginas:

« < 8 9 10

Closed Topic

Start new topic

2 usuario(s) está(n) leyendo esta discusión (2 invitado(s) y 0 usuario(s) anónimo(s))

0 miembro(s):

Modo de Ver: Estándar · Cambiar a: Lineal+ · Cambiar a: Outline

Suscribirse · Enviar por correo · Imprimir · Suscribirse a este foro

Versión Lo-Fi

Fecha y Hora actual: 23rd November 2024 - 07:36 AM

Powered By IP.Board 2.2.1 © 2007 IPS, Inc.