Dada uma matriz $A$ e um índice de $c$, provar, sempre existe um subarray cuja soma $\pmod {i} = 0$

Question

Dada uma matriz $A$ de inteiros positivos com tamanho $m$ e um índice de matriz $c$ (indexação começa em $1$).Prove usando indução matemática sobre $m$ que sempre existe um contíguos subarray $S$ no $A$ tal que a soma dos elementos de $S$) $\pmod {i} = 0.$

Eu sou incapaz de encontrar a abordagem correta para resolver isso.Tenho certeza que o Classificar Princípio vai ser útil aqui, mas não sei como aplicar corretamente dentro da prova.Alguém pode me apontar na direção certa?

Answer 1

Vamos tentar fazê-lo, sem indução envolvida.

Suponha que você aumente sua lista inicial $ a= [A_1, A_2, ..., A_M] $ com um novo elemento no início $ a_0= 0 $ , $ a '= [a_0, a_1, ..., a_m] $ .

Agora construa somas parciais da $ a '$ , tal que $ P_I=SUM_0 ^ i A_J $ . Observe que as somas dos elementos na lista inicial de posições $ B $ para posicionar $ e $ é < span class="contentor de matemática"> $ \ sum_b ^ e a_i= p_e - p_ {b - 1} $ . Observe $ p_0= 0 $ é definido desde que adicionamos $ a_0 $ . Este é um truque muito comum quando você se importa com as somas dos intervalos.

Voltar para o problema, você precisa provar lá existem dois índice $ i tal que $ c | (P_j - p_i) $ . Isso é equivalente a dizer que existem dois índice $ i tal que $ p_i \ equiv p_j \ mod c $ . Nós só nos preocupamos com o restante de cada elemento na $ P $ se eles forem divididos por $ c $ , e Além disso, devemos mostrar apenas que pelo menos dois elementos têm o mesmo restante.

Note agora o número de restantes diferentes dados $ c $ é no máximo $ c $ e o Comprimento da lista $ P $ é $ | p |= M + 1 $ . Como $ c \ le m <| p | $ pelo princípio de pombo você pode garantir pelo menos dois elementos em $ P $ tem o mesmo restante.

Answer 2

Deixe P(m) assinalar a declaração de que estamos tentando provar:Dado positivo-matriz de inteiros A tamanho m e um c no [m] há um (contígua) subarray cuja soma módulo c é 0.

Vamos dizer que estes subarrays satisfy P(m).

P(1) é trivial, desde que c = 1.

Suponha que P(m).Vamos tentar provar para P(m+1).

Se c <= m, e , em seguida, ignorar o último elemento da matriz e o aviso de que qualquer subarray que satisfaz P(m) também satisfaz P(m+1).

Suponha c == m+1.

Considere o m+1 somas:S1 = A[1]%(m+1), S2 = (A[1] + A[2])%(m+1),.... S_(m+1) = (A[1] + A[2] + ... + A[m+1])%(m+1)

Se um dos S_i == 0, em seguida, sub-matriz A[1..i] satisfaz P(m+1).

Se nenhum dos S_i são 0, cada S_i só pode assumir um dos m valores no intervalo de {1,2,...,m}.Por Classificar Princípio, não deve ser índices de i < j de tal forma que S_i == S_j e A[i+1 ... j] satisfaz P(m+1).