Wieviele Männer und Frau sind es gewesen?

Question

Aufgabe:

Lineare Gleichungssysteme: Groschen und Taler (Aufgabe von Euler)

Problem/Ansatz:

Eine Gesellschaft von Männern und Frauen sind in einem Wirtshaus. Jeder Mann gibt 25 Groschen, jede Frau 16 Groschen aus, und es stellt sich heraus, dass sämtliche Frauen 1 Groschen mehr ausgegeben haben als die Männer. Wieviele Männer und Frau sind es gewesen?

Lösung: es sind 11 Frauen und 7 Männer. Die Frauen geben 11*16=176 Groschen aus, die Männer 7*25=175 Groschen. Die Zeche beträgt 351 Groschen. Und: die Personenanzahl ist "modulo 400 (=25*16)". Die Lösung ist also (11+n*25) Frauen und (7+n*16) Männer. Beispiel: 36 Frauen geben 36*16=576 Groschen aus, 23 Männer geben 23*25=575 Groschen aus.

Wie ist der EXAKTE Lösungsweg bzw. wie lässt sich dies geschlossen berechnen (inkl. Modulo)?

Ergänzung: die Kosten (x, y) müssen relativ prim sein wegen: x * M = y * F - 1. haben x und y einen gemeinsamen Teiler t so kann man kürzen und es ergibt sich x/t * M = y/t * F + 1/t. 1/t ist aber nicht gazzahlig (!)

Answer 1

25·m + 1 = 16·f

Das ist eine sogenannte lineare diophantische Gleichung. Also eine Gleichung die im Bereich der ganzen bzw. im Bereich der natürlichen Zahlen zu lösen ist.

Es gibt verschiedene Möglichkeiten das zu lösen. Z.B. über den erweiterten euklidischen Algorithmus.

Ich komme dabei auf

m = 7 + 16t
f = 11 + 25t

Und jetzt erkennst du auch das 7 und 11 nicht die einzige Lösung ist, sondern das es auch 23 Männer und 36 Frauen hätten sein können. Das ist dann nur noch eine Frage der Größe des Wirtshauses.

Answer 2

Sei F die Anzahl der Frauen und M die Anzahl der Männer.

Laut Aufgabe gilt dann

25 M = 16 F -1 .

Diese Gleichung mit ihren unendlich vielen Lösungespaaren (M,F) kannst du jetzt je nach Belieben

mod 25 oder mod 16 betrachten. Ich würde mod 16 vorschlagen.

Dann gilt

25 M ≡ 9 M ≡ -1  mod 16

Für 9M ≡ -1  mod 16

muss man nur 16 Möglichkeiten für M durchprobieren (oder diese Kongruenz je nach Kenntnisstand anderweitig lösen).

Eine Lösung ist M=7, weitere Lösungen sind M=23, M=39 usw.

Für M=7 ergibt sich F=11, für M=23 ergibt sich F=36, für M=39 ergibt sich F=61 ...

(Jede Erhöhung von M um 16 führt zu einer Erhöhung von F um 25.)