Bezahlen ohne Rest

Aus einer Mathematikolympiade der neunziger Jahre, Klassenstufe 5


Es ist zu zeigen, dass man eine beliebige Rubelsumme, die größer als 7 Rubel ist, mit Banknoten von 5 und 3 Rubeln bezahlen kann, ohne dass Wechselgeld herausgegeben werden muss.

Es genügt zu zeigen, dass jede Rubelsumme zwischen 8 und 15 Rubeln in dieser Weise bezahlt werden kann.

Denn für jede Zahl n , die größer ist als 15, gilt: n = k•8 + r mit k≥ 2 und 0≤ r ≤ 7 .

Damit ist n = (k – 1)•8 + ( 8 + r) mit k – 1 ≥ 1 und 8 ≤ 8 + r ≤ 15

Das heißt: Jede Zahl, die größer ist als 15, unterscheidet sich von einer der Zahlen zwischen 8 und 15 um ein bestimmtes Vielfaches von 8. Wenn man also im Einzelnen zeigt, dass jede Zahl zwischen 8 und 15 sich in der geforderten Weise bezahlen lässt, so gilt das auch für jede Zahl, die größer ist als 15.

8 = 5+3;   9 = 3+3+3;   10 = 5 + 5;   11 = 5 + 3 + 3;   12 = 3+3+3+3;   13 = 5+5+3;   14= 5+ 3+3+3;   15 = 5+5+5