Contar - Foro fmat.cl

Portal Matemático

¿Qué es FMAT?

Foro fmat.cl > Sector Preparación Olimpiadas > Sector Olímpico > Combinatoria > Problemas Resueltos

Reply to this topic

Start new topic

Contar, [avanzado]

Felipe_ambuli Ver Perfil del Miembro Ver los mensajes de este miembro	Dec 5 2009, 01:36 PM Publicado: #1
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 836 Registrado: 9-January 07 Desde: Santiasko Miembro Nº: 3.659 Nacionalidad: Sexo:	Encuentre el numero de subconjuntos de $TEX: $\{1,2,...,2000\}$$ , talque la suma de sus elementos sea divisible por 5.

~Fatal_Collapse~ Ver Perfil del Miembro Ver los mensajes de este miembro	Dec 19 2009, 08:47 AM Publicado: #2
Dios Matemático Supremo Grupo: Usuario FMAT Mensajes: 1.564 Registrado: 12-November 07 Desde: La Union, XIV Region de los Rios Miembro Nº: 12.607 Nacionalidad: Colegio/Liceo: Universidad: Sexo:	CITA(Felipe_ambuli @ Dec 5 2009, 02:36 PM) Encuentre el numero de subconjuntos de $TEX: $\{1,2,...,2000\}$$ , talque la suma de sus elementos sea divisible por 5. Bonito problema Felipe , realmente instructivo, aprendi varias cosas intentandolo y bueno, sin mas que decir aqui va mi respuesta. Espero que te agrade, y que este correcta $TEX: Definamos $P(x)=\displaystyle \prod_{k=1}^{2000} (1+x^k)$ (). Veamos que al desarrollar $P(x)$ en la forma $\displaystyle \sum_{r=0}^{2001000}a_r\cdot x^r$, el coeficiente $a_r$ asociado a $x^r$ denota la cantidad de subconjuntos tal que la suma de sus elementos es $r$. Bajo estas condiciones, se nos pide calcular $\displaystyle \sum_{r=1}^{400200} a_{5r}$. <br /><br />Sea $w=e^{\frac{2\pi \cdot i}{5}}$. Primero ocupando () no es complicado obtener que $P(w)=P(w^2)=P(w^3)=P(w^4)=2^{400}$. En efecto, ocupando que $w^{5m+n}=w^n$ (), $m,n\in \mathbb{Z}^+$ podemos ver que:<br /><br />$P(w)=(1+w)^{400}(1+w^2)^{400}(1+w^3)^{400}(1+w^4)^{400}(1+w^5)^{400}$<br /><br />Como $w^5=1$ y desarollando los otros terminos de $P(w)$ se obtiene lo señalado. Las igualdades para $P(w^2)$, $P(w^3)$ y $P(w^4)$ se obtienen de forma analoga. Sea $A_i$ (i=0,1,2,3,4) el conjunto que contiene a todos los $a_j$, con $j\equiv i\pmod 5$, y sea $s_i$ la suma los elementos de $A_i$. Ocupando (), veamos que <br /><br />$P(w^i)=s_0+s_1w^i+s_2w^{2i}+s_3w^{3i}+s_4w^{4i}$<br /><br />Poniendo $i=0,1,2,3,4$ veamos que:<br /><br />$5s_0+(s_1+s_2+s_3+s_4)(1+w+w^2+w^3+w^4)=2^{2000}+4\cdot 2^{400}$<br /><br />Como $1+w+w^2+w^3+w^4=\dfrac{1-w^5}{1-w}=0$, obtenemos que:<br /><br />$s_0=\dfrac{2^{2000}+2^{402}}{5}$<br /><br />Pero entre los sumandos de $s_0$ aparece $a_0$, el cual no nos sirve, pues es la cantidad de formas de generar una suma cero. Como $a_0=P(0)=1$, finalmente la cantidad buscada de subconjuntos cuya suma de elementos sea divisible por $5$ es $s_0-1=\dfrac {2^{2000}+2^{402}}{5}-1$$ Saludos. -------------------- Ricardo Vargas Obando Ex-alumno Deutsche Schule La Unión (Generación 2010, de los 150 años). Novato de Licenciatura en Matemática/Estadística, en la Pontificia Universidad Católica de Chile. Grupo de facebook de Novatos Matemática y Estadística PUC 2011 Currículum Olímpico: Medalla de Plata, XIX Olimpiada Nacional de Matemática Nivel Menor (2007) Medalla de Oro, XXI Olimpiada Nacional de Matemática Nivel Mayor (2009) Medalla de Bronce, XXV Olimpiada Iberoamericana de Matemática (2010) Medalla de Oro, XXII Olimpiada Nacional de Matemática Nivel Mayor (2010) "What we learned as children, that one plus one equals two, we know to be false. One plus one equals one. We even have a word when you plus another, equals one. That word is love." "Todos piensan en cambiar el mundo, pero nadie piensa en cambiarse a sí mismo."

xD13G0x Ver Perfil del Miembro Ver los mensajes de este miembro	Dec 19 2009, 04:11 PM Publicado: #3
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:	Dare una segunda solucion al problema, me tomo un tiempito sacarla (1 hora) pero ya salio, esta vez mas combinatoria, la solucion de kain 13 es algo mas algebraica, como yo no me manejo mucho en algebra, hay unas partes que no entiendo Bueno ahi va: $TEX: Vamos a usar induccion y a generalizar el problema.Todas las congruencias son tomadas modulo 5.Diremos que un conjunto es congruente a $n$, si la suma de sus elementos es congruente a $n$. Sea $C_n=\{ 1,2,...,5n \}$ y $1_n,2_n,3_n,4_n,5_n$ la cantidad de subconjuntos de $C_n$(tomando en cuenta el conjunto vacio) tales que la suma de sus elementos son congruentes a 1, 2, 3, 4 y 5 respectivamente. Entonces:$ $TEX: $1_n=2_n=3_n=4_n=\dfrac {2^{5n}-2^n}{5}$ y $5_n=\dfrac {2^{5n}+2^{n+2}}{5}$$ $TEX: El caso 1 es trivial, se lo puede comprobar escribiendo los $2^5$ subconjuntos de $\{ 1,2,3,4,5 \}$ y sacando la congruencia en cada subconjunto.$ $TEX: Entonces $1_1=2_1=3_1=4_1=6$ y $5_1=8$$ $TEX: Ahora probaremos la formula para $n+1$.Obviamente $C_{n+1}=C_n \cup \{5n+1,5n+2,5n+3,5n+4,5n+5\}$$ $TEX: Tenemos que $1_{n+1}=1_15_n+5_11_n+3 \cdotp 1_11_n=\dfrac {6(2^{5n}+2^{n+2})}{5} + \dfrac {26(2^{5n}-2^n)}{5}=\dfrac {2^{5(n+1)}-2^{n+1}}{5}$$ $TEX: Para ver lo ultimo, note que:cada subconjunto de $\{5n+1,5n+2,5n+3,5n+4,5n+5\}$ unido a cada subconjunto de $C_n$ forman todos los subconjuntos de $C_{n+1}$, un subconjunto de $\{5n+1,5n+2,5n+3,5n+4,5n+5\}$ congruente a 1 unido a un subconjunto de $C_n$ congruente a 0 es un subconjunto de $C_{n+1}$ congruente a 1, un subconjunto de $\{5n+1,5n+2,5n+3,5n+4,5n+5\}$ congruente a 0 unido a un subconjunto de $C_n$ congruente a 1 es un subconjunto de $C_{n+1}$ congruente a uno y un subconjunto de $\{5n+1,5n+2,5n+3,5n+4,5n+5\}$ congruente a 2, 3, 4 unido a un subconjunto de $C_n$ congruente a 4, 3, 2 respectivamente es un subconjunto de $C_{n+1}$ congruente a 1 y obviamente estos son todos los subconjuntos de $C_{n+1}$ congruentes a 1.$ $TEX: Analogamente hallamos la formula para $2_n,3_n,4_n$. Para $5_n$ cambia un poco la cosa, pero la idea es muy parecida, igual sale$ Mensaje modificado por xD13G0x el Dec 19 2009, 04:19 PM -------------------- "I've never let my school interfere with my education.”

« Posterior · Problemas Resueltos · Anterior »

Reply to this topic

Start new topic

1 usuario(s) está(n) leyendo esta discusión (1 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:43 AM

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