Maraton - Foro fmat.cl

Portal Matemático

¿Qué es FMAT?

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

41 Páginas:

« < 4 5 6 7 8 > »

Reply to this topic

Start new topic

Maraton

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	May 1 2011, 08:13 PM Publicado: #51
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(The Lord @ Apr 30 2011, 11:36 PM) Calcular la probabilidad de que al tirar N veces al aire una moneda no cargada el numero de caras que salga sea congruente a q modulo p. Opcionalmente vea que pasa si la moneda esta cargada. La probabilidad pedida es $TEX: <br />$$P=\frac{1}{2^n}\sum_{a\equiv q\mod p}\binom{n}{a}$$<br />$ donde la suma recorre los a congruentes con q modulo p en el rango 0,1,..,n. La cantidad de sumandos es (mas o menos) n/p asi que cuando n no es mucho mas grande que p esta suma es suficiente para calcular la probabilidad. El problema es cuando n es mucho mas grande que p, entonces n/p es grande. A continuacion demostramos otra expresion para P, la cual tiene p sumandos asi que sera mejor que la anterior cuando $TEX: $p<\sqrt{n}$$ . Sea $TEX: <br />$$<br />Q_r=\sum_{a=0}^n \exp(2\pi i ar/p)\binom{n}{a}<br />$$<br />$ entonces calculando las sumas geometricas, obtenemos $TEX: <br />$$<br />2^nP=\frac{1}{p}\sum_{r=0}^{p-1}\exp(-2\pi i qr/p)Q_r<br />$$<br />$ pero es claro que $TEX: <br />$$<br />Q_r=(1+\exp(2\pi i r/p))^n<br />$$<br />$ por lo tanto obtenemos $TEX: <br />\begin{eqnarray}<br />2^nP&=&\frac{1}{p}\sum_{r=0}^{p-1}\exp(-2\pi i qr/p)(1+\exp(2\pi i r/p))^n\\<br />&=&\frac{1}{p}\sum_{r=0}^{p-1}\exp(-2\pi i qr/p)\exp(\pi i nr/p)2^n \cos^n(\pi r/p)<br />\end{eqnarray}<br />$ y concluimos la siguiente formula para la probabilidad pedida $TEX: <br />\begin{eqnarray}<br />P&=&\frac{1}{p}\sum_{r=0}^{p-1}\exp(\pi i (n-2q)r/p)\cos^n(\pi r/p)\\<br />&=&\frac{1}{p}\sum_{r=0}^{p-1}\cos(\pi (n-2q)r/p)\cos^n(\pi r/p)<br />\end{eqnarray}<br />$ donde la ultima igualdad es porque la probabilidad es un numero real, asi que las partes imaginarias se tienen que calcelar y podemos eliminarlas de la suma. Si esta suma aun es muy complicada de evaluar, podemos aproximarla. La aproximaciones cada vez mejor en ma medida que n es grande con respecto a p, y si fijamos p y hacemos crecer n la aproximacion mejora exponencialmente con n. Veamos como se hace eso: Primero, observamos que para 0<x<1 se tiene $TEX: <br />$$1-x<(1-x) + (\frac{1}{2!}x^2-\frac{1}{3!}x^3)+\ldots=exp(-x)$$<br />$ Usando esto, y aislando el termino con r=0 de la ultima formula para P, obtenemos: $TEX: <br />\begin{eqnarray}<br />\|P-\frac{1}{p}\|&\le&\frac{1}{p}\sum_{r=1}^{p-1}\|\cos(\pi (n-2q)r/p)\cos^n(\pi r/p)\|\\<br />&<& \frac{1}{p}\sum_{r=1}^{p-1}\|\cos(\pi r/p)\|^n\\<br />&<&\frac{p-1}{p}\|\cos(\pi/p)\|^n<(1-(1-\|\cos(\pi/p)\|))^n\\<br />&<&\exp(-n(1-\cos(\pi/p)))<br />\end{eqnarray}<br />$ Vamos a echar a perder un poco la cota, para poder tener una expresion aun mas sencilla. Usamos lo siguiente: $TEX: <br />$$<br />\cos(x)=1-\frac{1}{2}x^2+\frac{1}{4!}x^4-\frac{1}{6!}x^6+\frac{1}{8!}x^8-\ldots<1-\frac{1}{2}x^2+\frac{1}{24}x^4<br />$$<br />$ y obtenemos (usando p>1 porque para p=1 el problema es trivial): $TEX: <br />$$<br />\|P-\frac{1}{p}\|<\exp(-\frac{\pi^2}{2}(1-\frac{1}{12}(\frac{\pi}{p})^2)\frac{n}{p^2})<\exp(-3.92n/p^2)<br />$$<br />$ esta estimacion es valida para $TEX: $p\ge 2$$ . Mientras mas grande es n, mas pequeño el error. Saludos Mensaje modificado por Pasten el May 1 2011, 10:20 PM -------------------- Pasten, un buen muchacho en quien confiar.

The Lord Ver Perfil del Miembro Ver los mensajes de este miembro	May 1 2011, 10:14 PM Publicado: #52
Dios Matemático Grupo: Usuario FMAT Mensajes: 374 Registrado: 16-September 06 Desde: New Haven, CT, USA. Miembro Nº: 2.275 Nacionalidad: Colegio/Liceo: Universidad: Sexo:	Excelente! bonita solución y bonito planteo de ella, justa y precisa. Propone Pasten.

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	May 1 2011, 11:05 PM Publicado: #53
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	Siguiente, ahora un poquito mas "olimpico" (ya que me reclamaron por ahi que nos estabamos desviando del tema). Sea S una circunferencia, B,C puntos distintos fijos de S. Dado un punto A en S (disntinto de B y C) se contruye el triangulo ABC con su incirculo I. Sea L la recta que pasa por los puntos de tangencia de I con los lados AB y AC. Sea P la interseccion de L con la bisectriz de ABC, y Q la intreseccion de L con la bisectriz de ACB. Pruebe que hay una circunferencia T tal que, cuando A varia en S, los puntos P,Q siempre estan en T. Saludos! -------------------- Pasten, un buen muchacho en quien confiar.

xD13G0x Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 12:04 AM Publicado: #54
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 532 Registrado: 19-October 08 Desde: Santa Cruz de la Sierra Miembro Nº: 36.531 Nacionalidad: Sexo:	Vamos a demostrar que la circunferencia de diametro BC siempre pasa por P y Q. Sean D y E los puntos de tangencia del incirculo de ABC con AB y AC, respectivamente. Se tiene que BPD=180-DBP-PDB=180-B/2-(90+A/2)=90-B/2-A/2=C/2=ICE, entonces IEPC es ciclico. Luego BPC=IPC=IEC=90 de donde P esta en la circunferencia de diametro BC. Analogamente Q esta en la circunferencia de diametro BC. -------------------- "I've never let my school interfere with my education.”

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 12:14 AM Publicado: #55
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(xD13G0x @ May 2 2011, 01:04 AM) Vamos a demostrar que la circunferencia de diametro BC siempre pasa por P y Q. Sean D y E los puntos de tangencia del incirculo de ABC con AB y AC, respectivamente. Se tiene que BPD=180-DBP-PDB=180-B/2-(90+A/2)=90-B/2-A/2=C/2=ICE, entonces IEPC es ciclico. Luego BPC=IPC=IEC=90 de donde P esta en la circunferencia de diametro BC. Analogamente Q esta en la circunferencia de diametro BC. I era el incirculo, no el incentro, pero se entiende. Correcto! Fuente: conocida propiedad. Ahora propone xD13G0x. -------------------- Pasten, un buen muchacho en quien confiar.

xD13G0x Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 12:19 AM Publicado: #56
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 532 Registrado: 19-October 08 Desde: Santa Cruz de la Sierra Miembro Nº: 36.531 Nacionalidad: Sexo:	Encuentre todos los enteros positivos k tales que existe un entero a tal que $TEX: $(a+k)^3-a^3$$ es multiplo de 2007 EDIT: herrores hortografikos. Mensaje modificado por xD13G0x el May 2 2011, 12:36 AM -------------------- "I've never let my school interfere with my education.”

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 12:58 AM Publicado: #57
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	CITA(xD13G0x @ May 2 2011, 01:19 AM) Encuentre todos los enteros positivos k tales que existe un entero a tal que $TEX: $(a+k)^3-a^3$$ es multiplo de 2007 EDIT: herrores hortografikos. Tenemos que 2007=9223 y ademas $TEX: $(a+k)^3-a^3=k(a^2+a(k+a)+(k+a)^2)=k(3a^2+3ak+k^2)$$ Asi que necesariamente 3\|k. Esto nos deja los casos (entiendanse excluyentes) 1. 3\|k 2. 9\|k 3. 3223\|k 4. 9*223\|k Los casos 3 y 4 claramente sirven, pues cualquier a es solucion. Para estudiar los casos 1., 2., supongamos que 223 no divide k. Entonces para tener solucion es necesario y suficiente que exista a tal que $TEX: $223\|(3a^2+3ak+k^2)$$ lo que es equivalente a decir que la ecuacion $TEX: <br />$$<br />3x^2+3kx+k^2=0<br />$$<br />$ tenga solucion modulo 223. El discriminante es $TEX: <br />$$<br />\Delta=(3k)^2-4\cdot 3\cdot k^2=-3k^2<br />$$<br />$ asi que la ecuacion tiene solucion modulo 223 si y solo si -3 es cuadrado modulo 223. Esto tiene facil respuesta: Si, -3 es el cuadrado de 79. Con esto concluimos que los casos 1.,2. tambien dan solucion para a. Los casos 1,2,3,4 se pueden resumir diciendo simplemente que 3\|k. Entonces tenemos solucion a si y solo si 3\|k. Nota: si no es evidente para ustedes que 79 es una raiz cuadrada de -3 modulo 223, entonces pueden usar reciprocidad cuadratica, porque nos interesa saber si es o no es un cuadrado, no cual es la raiz. Saludos -------------------- Pasten, un buen muchacho en quien confiar.

xD13G0x Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 01:11 AM Publicado: #58
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 532 Registrado: 19-October 08 Desde: Santa Cruz de la Sierra Miembro Nº: 36.531 Nacionalidad: Sexo:	Correcto, yo lo vi de otra forma pero demas que eso esta bien. Proponga Pasten y vayase a dormir xd EDIT: de donde lo saque no tenia fuente (si, de nuevo) Mensaje modificado por xD13G0x el May 2 2011, 01:13 AM -------------------- "I've never let my school interfere with my education.”

Pasten Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 01:35 AM Publicado: #59
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 765 Registrado: 6-December 05 Miembro Nº: 458 Nacionalidad: Sexo:	Sea p>2 primo y k entero coprimo con p. Sean X,Y subconjuntos de {0,1,...,p-1} con A,B elementos respectivamente. Demuestre que $TEX: <br />$$<br />\left\|\sum_{x\in X}\sum_{y\in Y}\left(\frac{xy+k}{p}\right)\right\|<\sqrt{ABp}<br />$$<br />$ donde (como siempre): $TEX: <br />$$<br />\left(\frac{u}{p}\right)=\begin{cases}<br />0\mbox{ si } p\|u\\<br />-1\mbox{ si } u \mbox{ no es residuo cuadratico modulo }p\\<br />1\mbox{ si } u \mbox{ es residuo cuadratico no nulo modulo }p.<br />\end{cases}<br />$$<br />$ Saludos -------------------- Pasten, un buen muchacho en quien confiar.

coquitao Ver Perfil del Miembro Ver los mensajes de este miembro	May 2 2011, 01:38 PM Publicado: #60
Dios Matemático Supremo Grupo: Super Moderador Mensajes: 2.065 Registrado: 25-May 08 Desde: Pelotillehue Miembro Nº: 24.463	Sea $TEX: $S:= \sum_{x \in X} \sum_{y \in Y} \left(\frac{xy+k}{p}\right)$$ . Por Cauchy-Schwarz se tiene que $TEX: $\|S\|^{2} \leq \|X\| \sum_{x \in X} \left(\sum_{y \in Y} \left(\frac{xy+k}{p}\right)\right)^{2} \leq A \sum_{x=0}^{p-1} \left(\sum_{y \in Y} \left(\frac{xy+k}{p}\right)\right)^{2}=$$ $TEX: $= A \sum_{y \in Y} \sum_{y_{1} \in Y} \sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right).$$ ----------(1) Estudiemos la expresión $TEX: $\sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right)$$ en términos de $TEX: $y$$ y $TEX: $y_{1}$$ . Si $TEX: $y=0=y_{1}$$ entonces $TEX: $\sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right) = p.$$ Si $TEX: $y \neq 0$$ y $TEX: $y_{1} = 0$$ entonces $TEX: $\sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right) = 0$$ . Lo mismo ocurre en los casos en que $TEX: $y=0$$ y $TEX: $y_{1} \neq 0$$ . Ahora bien, si $TEX: $y=y_{1}$$ , con $TEX: $y \neq 0$$ , entonces $TEX: $\sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right) = \sum_{x=0}^{p-1}\left(\frac{xy+k}{p}\right)^{2} = (p-1).$$ Finalmente, si el par $TEX: $(y,y_{1})$$ cae en ninguno de los casos anteriores, se cumple que $TEX: $\sum_{x=0}^{p-1} \left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right) = \sum_{x=0}^{p-1} \left(\frac{yy_{1}}{p}\right)\left(\frac{x+ky^{\ast}}{p}\right)\left(\frac{x+ky_{1}^{\ast}}{p}\right) =$$ $TEX: $=\left(\frac{yy_{1}}{p}\right) \sum_{x=0}^{p-1} \left(\frac{x+ky^{\ast}}{p}\right)\left(\frac{x+ky^{\ast} + (ky_{1}^{\ast}-ky^{\ast})}{p}\right) = -\left(\frac{yy_{1}}{p}\right).$$ Las desigualdades en (1), dan en vista del análisis anterior que, $TEX: $\|S\|^{2} \leq A[p \chi_{Y}(0) + (p-1)(B-\chi_{Y}(0)) + \sum_{y>0}\sum_{y_{1}\neq y, y_{1}> 0} \sum_{x=0}^{p-1}\left(\frac{xy+k}{p}\right)\left(\frac{xy_{1}+k}{p}\right)]=$$ $TEX: $= A[p \chi_{Y}(0) + (p-1)(B-\chi_{Y}(0)) + \sum_{y>0}\sum_{y_{1} \neq y , y_{1}>0} (-1)\left(\frac{yy_{1}}{p}\right)] = $$ $TEX: $= A[p \chi_{Y}(0) + (p-1)(B-\chi_{Y}(0)) + \sum_{y>0}\sum_{y_{1} \neq y, y_{1}>0} (-1)\left(\frac{yy_{1}}{p}\right)+$$ $TEX: $+ (B-\chi_{Y}(0))-\sum_{y>0} \left(\frac{y^{2}}{p}\right)] =$$ $TEX: $= A[p\chi_{Y}(0) + (p-1)(B-\chi_{Y}(0)) + (B-\chi_{Y}(0)) - \left(\sum_{y \in Y, y>0} \left(\frac{y}{p}\right)\right)^{2}] \leq $$ $TEX: $\leq ABp$$ y de aquí el resultado que se pedía. OBSERVACIONES. 1. $TEX: $y^{\ast}$'> es el inverso multiplicativo mod p de [tex=./tex/419c04b27804fbad45d097fcc50cc864.png]$y$$ . 2. $TEX: $\chi_{Y}(0)=1$$ si 0 está en Y y $TEX: $\chi_{Y}(0) = 0$$ si no está. 3. Utilizamos el hecho de que la suma de los símbolos de Legendre sobre un sistema completo de restos mod p es 0. También utilizamos el hecho conocido de que si $TEX: $(k,p)=1$$ entonces $TEX: $\sum_{x=0}^{p-1} \left(\frac{x(x+k)}{p}\right)=-1$$ (líneas 8-10). La prueba de este segundo hecho es como sigue: $TEX: $\sum_{x=0}^{p-1} \left(\frac{x(x+k)}{p}\right) = \sum_{x=1}^{p-1} \left(\frac{x^{\ast}}{p}\right)^{2}\left(\frac{x(x+k)}{p}\right) = \sum_{x=1}^{p-1}\left(\frac{1+kx^{\ast}}{p}\right)= \sum_{x=1}^{p-1} \left(\frac{1+x}{p}\right) = $$ $TEX: $= \sum_{x=0}^{p-1} \left(\frac{1+x}{p}\right) - \left(\frac{1}{p}\right)=-1.$$ -------------------- "Please forget everything you have learned in school; for you haven't learned it... Please keep in mind at all times the corresponding portions of your school curriculum; for you haven't actually forgotten them." -- E. Landau

« Posterior · Problemas Propuestos · Anterior »

41 Páginas:

« < 4 5 6 7 8 > »

Reply to this 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 - 01:14 PM

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