Étant donné un tableau $A$ et un index $c$, prouver qu'il existe toujours un sous-tableau dont la somme $\pmod {i} = 0$

Question

Étant donné un tableau $A$ d'entiers positifs de taille millions de dollars et un index de tableau $c$ (l'indexation commence à $1$).Prouver en utilisant l'induction mathématique sur millions de dollars qu'il existe toujours un sous-tableau contigu $S$ dans $A$ tel que la (somme des éléments de $S$) $\pmod {i} = 0.$

Je ne parviens pas à trouver la bonne approche pour résoudre ce problème.je suis sûr que le Principe du casier sera utile ici, mais je ne sais pas comment l'appliquer correctement dans la preuve.Quelqu'un peut me diriger dans la bonne direction?

Answer 1

Essayons de le faire, aucune induction impliquée.

Supposons que vous augmentez votre liste initiale $ a= [A_1, a_2, ..., a_m] $ avec un nouvel élément au début $ a_0= 0 $ , $ a '= [a_0, a_1, ..., a_m] $ .

Construisez maintenant des sommes partielles de $ a '$ , telle que $ p_i=sum_0 ^ i a_j $ . Notez que les sommes d'éléments de la liste initiale des positions $ B $ à positionner $ e $ est < span class="math-conteneur"> $ \ sum_b ^ e a_i= p_e - p_ {b - 1} $ . AVIS $ P_0= 0 $ est défini depuis que nous avons ajouté $ A_0 $ . C'est un tour très courant lorsque vous vous souciez des sommes d'intervalles.

Retour au problème, vous devez faire preuve d'exiger deux index $ i telle que $ C | (P_J - P_I) $ . Cela équivaut à dire qu'il existe deux index $ i tel que $ p_i \ equiv p_j \ mod $ . Nous ne nous soucions que du reste de chaque élément de $ p $ si elles sont divisées par $ C $ , et De plus, nous devrions seulement montrer qu'au moins deux éléments ont le même reste.

remarquez maintenant le nombre de restes différents donnés $ C $ est au plus $ C $ et le Longueur de la liste $ P $ est $ | P |= m + 1 $ . Depuis $ c \ le m <| p | $ par le principe du pigeonhole, vous pouvez garantir au moins deux éléments dans $ p $ avoir le même reste.

Answer 2

Laisser P(m) désignent l'énoncé que nous essayons de prouver :Étant donné un tableau d'entiers positifs A de taille m et un c dans [m] il existe un sous-tableau (contigu) dont la somme modulo c est 0.

Disons que de tels sous-réseaux satisfy P(m).

P(1) est trivial puisque c = 1.

Supposons P(m).Essayons de prouver pour P(m+1).

Si c <= m, puis ignorez le dernier élément du tableau et notez que tout sous-tableau qui satisfait P(m) satisfait également P(m+1).

Supposer c == m+1.

Prendre en compte m+1 sommes :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 l'un des S_i == 0, puis, sous-tableau A[1..i] satisfait P(m+1).

Si aucun des S_i sont 0, chacun S_i ne peut assumer qu'un des m valeurs dans la plage {1,2,...,m}.Selon le principe de Pigeonhole, il doit y avoir des indices i < j tel que S_i == S_j et A[i+1 ... j] satisfait P(m+1).