Mathedings Nr. 15 - Schubfachprinzip

16. Dezember 2011

Heute mal eine Aufgabe für Zwischendurch:

Zeige, dass man aus einer Menge von n natürlichen Zahlen (ohne Null) einige (mindestens eine) so auswählen kann, dass die Summe der ausgewählten Zahlen durch n teilbar ist.

2 Antworten auf “Mathedings Nr. 15 - Schubfachprinzip”

  1. André sagt:

    Wenn eine durch n teilbare Zahl dabei ist, dann nehmen wir einfach die.

    Allgemein genügt es, nur die Reste mod n zu betrachten. Wir haben also n Zahlen, die den n Restklassen mod n angehören.

    Wir sind also in der zyklischen Gruppe der Ordnung n.

    Addieren wir nacheinander die Vertreter der Restklassen. Dabei beschreibt (x) die Nummer der Addition:

    (1) [a_1] = [z_1]
    (2) [z_1]+[a_2] = [z_2]
    (3) [z_2]+[a_3] = [z_3]
    (4) [z_3]+[a_4] = [z_4]
    ...
    (n) [z_{n-1}]+[a_n] = [z_n]

    Entweder gilt für irgendein [z_i] mit i aus {1,...,n}

    [z_i] = [0]

    Dann haben wir eine Lösung, nämlich:

    [a_1] + [a_2] + ... + [a_i] = [0]

    Oder aber es gibt [z_x] = [z_y] mit x ungleich y. Wenn wir nämlich die insgesamt n z_i auf n-1 Restklassen verteilen, muss mindestens eine doppelt vorkommen.

    Dann gilt

    [a_{x+1}] + [a_{x+2}] + ... + [a_y] = [0]

    q.e.d.

  2. Leif sagt:

    Genau richtig!
    Interessant dabei ist auch, dass diese Lösung stets aufeinanderfolgende Zahlen liefert, die die gesuchte Eigenschaft erfüllen, falls die Zahlen in irgendeiner Reihenfolge gegeben sind.

Schreibe einen Kommentar: