Saltar al contenido

Demostrar que dado un conjunto de n enteros positivos, existe un subconjunto no vacío cuya suma es divisible por n

Nuestro grupo de trabajo ha estado mucho tiempo buscando soluciones a tu duda, te dejamos la solución por esto deseamos que resulte de mucha ayuda.

Solución:

A través de la aritmética modular, esto es muy fácil y es algo que puede verificar (si está familiarizado con esto). De lo contrario, se puede mostrar el siguiente resultado a través del algoritmo de división (es decir, simplemente división directa con cociente y resto):

Si $a$ y $b$ tienen el mismo resto cuando se dividen por $n$, entonces $ab$ es divisible por $n$.

La prueba es como sigue. Sea $r$ el resto común de $a$ y $b$ cuando se divide por $n$. El algoritmo de división da enteros $q,p$ tales que $a=qn+r$ y $b=pn+r$. Por lo tanto, obtenemos $$ab=(qn+r)-(pn+r)=(qn-pn)+(rr)=(qp)n$$ por lo que $n$ divide a $ab$.

Tenga en cuenta que el resultado anterior es más general y se puede aplicar a su situación si tiene $a=S_j$ y $b=S_i$. Realmente no importa que $S_i$ y $S_j$ sean sumas de números enteros al aplicar la declaración que acabo de probar; en lo que a nosotros respecta, son solo algunos números enteros $a$ y $b$.

Sea $p

y $S_q = sum_i=1^q s_i equiv r pmodn$

entonces tenemos $S_q-S_p=sum_i=p+1^q s_i equiv rr equiv 0 pmodn$

donde tenemos que usar la propiedad de que si $a equiv b pmodn$ y $c equiv d pmodn$, entonces tenemos $ac equiv bd pmodn$

Si no está familiarizado con la aritmética de módulo, véala como si $a = nk+r$ y $c = nt+r$, luego $ac = n(kt)$.

Recuerda que puedes recomendar esta sección si lograste el éxito.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *