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$.

3 comentarios:

Unknown dijo...

¿Los brincos son todos en dirección positiva?

nivek dijo...

si

Unknown dijo...

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