Beweisen Sie bei einem gegebenen Array $A$ und einem Index $c$, dass es immer ein Unterarray gibt, dessen Summe $\pmod {i} = 0$ ist

Question

Gegeben ein Array $A$ von positiven ganzen Zahlen mit Größe $m$ und ein Array-Index $c$ (Die Indizierung beginnt bei $1$).Beweisen Sie mit der mathematischen Induktion über $m$ dass es immer ein zusammenhängendes Subarray gibt $S$ In $A$ so dass die (Summe der Elemente von $S$) $\pmod {i} = 0.$

Ich kann nicht den richtigen Ansatz finden, um dieses Problem zu lösen.Ich bin mir sicher Schubladenprinzip wird hier nützlich sein, aber ich weiß nicht, wie ich es im Beweis richtig anwenden soll.Kann mir jemand die richtige Richtung weisen?

Answer 1

Versuchen wir es, es zu tun, keine Induktion involviert.

Angenommen, Sie ergänzen Ihre Erstliste $ A= [A_1, A_2, ..., A_M] $ mit einem neuen Element am Anfang $ A_0= 0 $ , $ a '= [A_0, A_1, ..., A_M] $ .

bauen jetzt Teilsumme von $ a '$ , so dass $ p_i=sum_0 ^ i a_j $ . Beachten Sie, dass die Summen der Elemente in der Anfangsliste von Positionen $ B $ auf Position $ E $ ist < Span-Klasse="Math-Container"> $ \ SUM_B ^ E A_I= P_E - P_ {B - 1} $ . Hinweis $ P_0= 0 $ ist definiert, da wir $ A_0 $ hinzugefügt werden. Dies ist ein sehr häufiger Trick, wenn Sie sich um die Summen der Intervalle kümmern.

Zurück zum Problem, Sie müssen den Nachweis bestehen, dass es zwei Index gibt $ i so, dass $ C | (P_j - p_i) $ . Dies ist äquivalent zu sagen, dass es zwei Index gibt $ i so, dass $ P_I \ EQUIV P_J \ mod C $ . Wir kümmern uns nur um den Rest jedes Elements in $ P $ Wenn sie durch $ C $ geteilt werden, und Außerdem sollten wir nur zeigen, dass mindestens zwei Elemente den gleichen Rest haben.

Beachten Sie nun die Anzahl der verschiedenen Restreste $ C $ ist höchstens $ C $ und das Länge der Liste $ P $ ist $ | P |= m + 1 $ . Seit $ C \ le m <| P | $ Durch das Pigeonloch-Prinzip können Sie mindestens zwei Elemente in $ P $ garantieren den gleichen Rest haben.

Answer 2

Lassen P(m) bezeichnen die Aussage, die wir zu beweisen versuchen:Gegeben sei ein positiv-ganzzahliges Array A der Größe m und ein c In [m] Es gibt ein (zusammenhängendes) Subarray, dessen Summe modulo ist c ist 0.

Nehmen wir an, solche Subarrays satisfy P(m).

P(1) ist trivial, da c = 1.

Angenommen P(m).Versuchen wir es für P(m+1) zu beweisen.

Wenn c <= m, dann ignorieren Sie das letzte Element des Arrays und beachten Sie, dass jedes Unterarray, das P(m) erfüllt, auch P(m+1) erfüllt.

Annehmen c == m+1.

Bedenke die m+1 Summen:S1 = A[1]%(m+1), S2 = (A[1] + A[2])%(m+1),.... S_(m+1) = (A[1] + A[2] + ... + A[m+1])%(m+1)

Wenn einer der S_i == 0, dann Unterarray A[1..i] erfüllt P(m+1).

Wenn nichts davon S_i sind jeweils 0 S_i kann nur eines davon übernehmen m Werte im Bereich {1,2,...,m}.Nach dem Pigeonhole-Prinzip müssen Indizes vorhanden sein i < j so dass S_i == S_j Und A[i+1 ... j] erfüllt P(m+1).