[Teoria liczb] Ciąg i podzielność czyli fajna teoria liczb

[Burii]

Przypuśćmy że \(\displaystyle{ m \ge k \ge 2}\) i \(\displaystyle{ k}\) dzieli \(\displaystyle{ m}\). Pokaż, że w każdym ciągu liczb naturalnych długości \(\displaystyle{ m+k-1}\) istnieje podciąg długości \(\displaystyle{ m}\) o sumie wyrazów podzielnej przez \(\displaystyle{ k}\).

[Damianito]

Ukryta treść:    

Kluczowy przypadek \(\displaystyle{ m=k}\) to dokładnie sformułowanie twierdzenia Erdosa-Ginzburga-Ziva. Na jego podstawie dowiedziemy żądanej tezy również dla \(\displaystyle{ m>k}\). Będziemy odkładać "na bok" z naszego ciągu o \(\displaystyle{ m+k-1}\) elementach \(\displaystyle{ k}\)-elementowe podciągi o sumach podzielnych przez \(\displaystyle{ k}\). Z twierdzenia EGZ wynika, że jest to na pewno możliwe, dopóki pozostałych wyrazów ciągu jest co najmniej \(\displaystyle{ 2k-1}\), więc odkładamy podciągi dopóki możemy i w końcu pozostanie elementów nieodłożonych mniej niż \(\displaystyle{ 2k-1}\), a skoro \(\displaystyle{ k}\) dzieli \(\displaystyle{ m}\), to pozostać musi \(\displaystyle{ k-1}\) elementów, czyli odłożonych mamy "na boku" \(\displaystyle{ m}\) elementów ciągu, które można podzielić na ciągi \(\displaystyle{ k}\)-elementowe sumujące się do liczb podzielnych przez \(\displaystyle{ k}\), czyli tworzą one wszystkie podciąg długości \(\displaystyle{ m}\) o sumie wyrazów podzielnej przez \(\displaystyle{ k}\), c.n.d.