martes, 16 de junio de 2015
Tienes un conjunto de enteros positivos $S=a_1,a_2,...,a_n$ (se entiende que todos los elementos son distintos) y un conjunto $M$ de enteros positivos con $n-1$ elementos que no tiene a $a_1+...+a_n$. Un saltamontes inicia en el número 0 y da brincos del tamaño de elementos de $S$ y no puede repetir elementos. Demuestra que es posible que salte de manera que nunca caiga en uno de los elementos de $M$.
Suscribirse a:
Comentarios de la entrada (Atom)
3 comentarios:
¿Los brincos son todos en dirección positiva?
si
Lo hacemos por induccion, el caso base sera n=2, el cual es muy facil de hacer, l y ahora considero las n sumas de los elementos de S que usan n-1 elementos, veo que todas son distintas entre si, ya que si dos fueran iguales entonces dos elementos de S serian iguales, entonces como tengo estas n sumas distintas y en M hay n-1 elementos, forzosamente una de estas sumas podemos asegurar que no es algun elemento de M, ahora me tomo esos n-1 elementos tal que su suma no es ningun elemento de M, y me tomo cualesquiera n-2 elementos de M, por hipotesis de induccion puedo hacer los saltos con estos n-1 elementos, y claramente puedo agregar el elemento faltante de S ya que ningun elemento de M es la suma de los elementos de S.
Publicar un comentario