Dado un arreglo $A$ y un índice $c$, demuestre que siempre existe un subarreglo cuya suma $\pmod {i} = 0$

Question

Dada una matriz $A$ de enteros positivos con tamaño $m$ y un índice de matriz $c$ (la indexación comienza en $1$).Demuestre usando inducción matemática sobre $m$ que siempre existe un subarreglo contiguo $S$ en $A$ tal que la (suma de los elementos de $S$) $\pmod {i} = 0.$

No puedo encontrar el enfoque correcto para resolver esto.Estoy seguro de que Principio de casillero Será útil aquí, pero no sé cómo aplicarlo correctamente dentro de la prueba.¿Alguien me puede apuntar en la dirección correcta?

Answer 1

Intentemos hacerlo, no hay inducción involucrada.

Supongamos que aumenta su lista inicial $ a= [A_1, A_2, ..., A_M] $ con un nuevo elemento al principio $ A_0= 0 $ , $ a '= [a_0, A_1, ..., A_M] $ .

Ahora crea sumas parciales de $ a '$ , de modo que $ p_i=sum_0 ^ i A_J $ . Observe que las sumas de elementos en la lista inicial de las posiciones $ b $ para posicionar $ e $ es < Span Class="Math-contenedor"> $ \ sum_b ^ e A_I= P_E - P_ {B - 1} $ . AVISO $ P_0= 0 $ se define desde que agregamos $ A_0 $ . Este es un truco muy común cuando se preocupa por las sumas de intervalos.

Volver al problema, debe probar que existan dos índice $ i de tal que $ c | (P_J - P_I) $ . Esto es equivalente a decir que existen dos índice $ i de tal manera que $ P_I \ EQUIV P_J \ MOD C $ . Solo nos preocupamos por el resto de cada elemento en $ P $ si están divididos por $ C $ , y Además, solo debemos demostrar que al menos dos elementos tienen el mismo resto.

Ahora note el número de diferentes restos dados $ c $ está en la mayoría $ C $ y el Longitud de la lista $ P $ es $ | p |= M + 1 $ . Desde $ C \ le m <| p | $ por el principio de pigeonhole Puede garantizar al menos dos elementos en $ P $ tiene el mismo resto.

Answer 2

Dejar P(m) denota la afirmación que estamos tratando de probar:Dada una matriz de enteros positivos A de tamaño m y un c en [m] hay un subarreglo (contiguo) cuya suma módulo c es 0.

Digamos que tales subarreglos satisfy Pm).

P(1) es trivial ya que c = 1.

Supongamos P(m).Intentemos demostrar P(m+1).

Si c <= m, luego ignore el último elemento de la matriz y observe que cualquier submatriz que satisfaga P(m) también satisfaga P(m+1).

Asumir c == m+1.

Considera el m+1 sumas:S1 = A[1]%(m+1), S2 = (A[1] + A[2])%(m+1),.... S_(m+1) = (A[1] + A[2] + ... + A[m+1])%(m+1)

Si uno de los S_i == 0, entonces, submatriz A[1..i] satisface P(m+1).

Si ninguno de los S_i son 0, cada uno S_i Sólo puede enfrentarse a uno de los m valores en el rango {1,2,...,m}.Según el principio de casillero, debe haber índices i < j tal que S_i == S_j y A[i+1 ... j] satisface P(m+1).