Sea $c(n)$ la cantidad de formas de escribir al entero positivo $n$ (sin contar el orden) como suma de enteros positivos, de modo que cualesquiera dos sumandos difieren al menos en dos. Sea $d(n)$ la cantidad de formas de escribir $n$ (sin contar el orden) como suma de algunos enteros positivos de la forma $5k+1$ o $5k-1$.
Por ejemplo, $c(10)=6$, pues $10=9+1=8+2=7+3=6+4=6+3+1$ (nota que estamos contando $10$ como una forma) y $d(10)=6$, pues $10=9+1=6+4=6+1+1+1+1=1+1+1+1+1+1+1+1+1+1$
$=4+1+1+1+1+1+1=4+4+1$ (aquí no cuenta $10$ pues no es de la forma deseada).
Muestra que para todo entero positivo $n$ se tiene $c(n)=d(n)$.
jueves, 31 de marzo de 2011
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
Ok, creo que para el Blog sí fue un problema muy manchado : p. Se los dejo por si lo quieren seguir pensando, pero para evaluar el trabajo en el Blog, mejor que se quede el siguiente:
En un torneo de Bridge con $110$ equipos en cada ronda hay $55$ partidos (en un partido se enfrentan $2$ equipos). Hay $6$ rondas. Cada equipo juega una vez por ronda y nunca juega contra un equipo más de una vez. Muestra que hay $19$ equipos tales que ningunos dos de ellos se enfrentaron entre sí.
Va la solución del problema del torneo de Bridge.
Probaremos algo más general, si hay $6k+2$ equipos y juegan 6 rondas, entonces hay al menos $k+1$ equipos que no se enfrentaron entre si.
Traslademos el problema a una gráfica donde los vértices son los equipos y pone una arista entre dos equipos si se enfrentaron en algun momento.
Procedamos por inducción. Si $k=1$ como hay $8$ personas y una persona solo se enfrento a $6$ entonces hay dos que no se enfrentaron.
Ahora supongamos que para todo $r<k$ se cumple, y probaremos que entonces para $k$ se cumple.
Para esto escojamos un vértice $v_1$ y denotemos el conjunto de las personas con las que jugó $v_1$ como $C_1$, luego escojamos una persona $v_2$ que no sea de $C_1$ pero que haya jugado con alguna persona de $C_1$ y consideremos $C_2$ el conjunto de las personas que jugo pero que no estan en $C_1$, de esta forma seguimos construyendo a $v_3$ como una persona que haya jugado con alguien de $C_1$ o $C_2$ y que no este en estos conjuntos, y así sucesivamente.
Supongamos que siempre podemos encontrar a $v_i$ entonces va como hay $6k+2$ personas y cada $v_i$ combinado con su respectivo $C_i$ tiene 6 personas menos el primero que tiene 7, entonces va a haber al menos $k+1$ $v_i$ y claramente si escojemos los $v_i$ son $k+1$ y no jugaron entre sí, por lo tanto si cumplen.
Ahora si en algun momento ya contruimos $v_1 , v_2 , v_3 , ... v_r$ pero no se puede construir $v_{r+1}$ significa que todas las personas que estan entre $v_1,...,v_r, C_1,...,C_r$ jugaron solo con personas de este conjunto. Pero de este conjunto hay a lo mas $6r+1$ personas, pero no puede haber un número impar por que juegan por parejas en cada ronda, por lo tanto hay a lo mas $6r$ personas, por lo tanto en las personas restantes hay al menos $6k+2-(6r)=6(k-r)+2)$ que por lo inducción sabemos que ha al menos $k-r+1$ personas que no jugaron entre sí y si les agregamos a $v_1,v_2,...,v_r$ juntamos a $k+1$ personas que no jugaron entre si$
Por lo tanto queda completa la inducción y cumple para todo $k$ natural, en particular para $k=18$
Bien George!
Publicar un comentario