Problema 3 - Solución
Dados n números naturales ninguno múltiplo de n ¿cual es el mínimo número de enteros, que debo tomar para asegurar que al menos dos de ellos tiene su suma o su resta múltiplos de n?
Solución:
Por lo tanto necesitamos averiguar cual es el mínimo número de enteros que necesito para asegurar que la suma o resta es múltiplo de n
Veamos que si ambos pertenecen a la misma clase ya está:
Sin perder generalidad supongamos que a y b pertenecen a la misma clase entonces
La dificultad se plantea cuando ambos números pertenecen a distinta clase, por ejemplo
Entonces, si ambos números están en la misma clase podemos tomar, sin perder generalidad un elemento de cada una de las clases desde 1 hasta (n-1)/2 y ningún par sumará múltiplo de n.
Por Palomar, cuando tomemos un elemento más de alguna clase, estamos en la generalización anterior. Resulta que debemos tomar al menos.
[(n-1)/2] + 1 números.
Por lo tanto necesitamos averiguar cual es el mínimo número de enteros que necesito para asegurar que la suma o resta es múltiplo de n
Veamos que si ambos pertenecen a la misma clase ya está:
Sin perder generalidad supongamos que a y b pertenecen a la misma clase entonces
La dificultad se plantea cuando ambos números pertenecen a distinta clase, por ejemplo
Entonces, si ambos números están en la misma clase podemos tomar, sin perder generalidad un elemento de cada una de las clases desde 1 hasta (n-2)/2 y ningún par sumará múltiplo de n.
Por Palomar, cuando tomemos un elemento más de alguna clase, estamos en la generalización anterior. Resulta que debemos tomar al menos [(n-2)/2] + 2 números.