Frage von MatheArtur, 44

Jeden Abend müssen 9 oder 10 aus 33 Lehrern im Dienst sein. Wie viele Tage reichen (das Minimum), damit jeder Lehrer gleich soviel arbeitet?

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von kreisfoermig, 15

Bezeichne mit k∈ℕ (bzw. m∈ℕ) mdie Anzahl der Tage, auf denen jeweils exakt 9 (bzw. 10) der Lehrkräfte eingesetzt werden. Um dass es nach k+m Tagen möglich ist, die Lehrer unter diesen Tagen so zu verteilen, dass alle die gleiche Anzahl an Tagen arbeiten, muss:

∃n∈ℤ: 9k+10m = 33n

gelten. (Das muss man zusätzlich beweisen: es ist offensichtlich, aber ein wenig aufwändig, sodass ich es hier erstmals lasse.) Es ist also notwendig und hinreichend, die o. s. Gleichung zu lösen, um alle Möglichkeiten zu finden (und dann unter diesen zu minimieren).

Laut der Zahlentheorie gilt 1 = ggT(9,10) | 9k+10m und es gibt k₀, m₀ ∈ ℤ so dass 9k₀+10m₀ = ggT(9,10). Nach Anwendung des Euklidschen Algorithmus (oder lediglich durch einfaches Raten!) erhält man bspw. k₀ = –1 und m₀ = 1. Laut der Zahlentheorie gilt:

(k,m) eine Lösung zu 9k+10m = 33n
gdw. ∃j∈ℤ: k = 33nk₀+10j (=–33n+10j)
und m = 33nm₀–9j (=33n–9j)

und in diesem Falle gilt:

Anzahl der Tage = k+m = –33n+10j+33n–9j = j,

wobei das j∈ℤ aus dem quantifizierten Ausdruck kommt. Insgesamt hat man bisher also

(k≥0,m≥0) eine Lösung zum Problem
gdw. ∃n,j∈ℤ: k = 33nk₀+10j (=–33n+10j)
und m = 33nm₀–9j (=33n–9j).

Es ist also j ≥ 1 zu minimieren, so dass

∃n∈ℤ: (k=)–33n+10j ≥ 0 und (m=)33n–9j ≥ 0

gilt. Nun beobachtet man für j∈ℤ:

  • –33n+10j ≥ 0 gdw. n ≤ 10j/33
  • 33n – 9j ≥ 0 gdw.  9j/33 ≤ n
  • darum k, m ≥ 0 gdw. 9j/33 ≤ n ≤ 10j/33
  • also ∃n∈ℤ: –33n+10j≥0 und 33n+9j≥0 gdw. [9j/33, 10j/33] eine ganze Zahl enthält.
(Lemma) dies gilt gdw. ceil(9j/33) ≤ floor(10j/33).

Das Problem lässt sich nun rechnerisch lösen. Man prüft nach, dass der kleinste Wert von j ≥ 1 mit dieser Bedingung gleich 7 ist (mit n=2). Also gilt

Minimaler Anzahl der Tage = 7.

Explizit gilt, dass an k=–33·2+10·7=4 der Tage 9 der Lehrer und an m=33·2–9·7=3 der Tage 10 der Lehrer eingesetzt werden.

Antwort
von MatheRaph, 25

Ich würde nach 33 Tagen sagen

Keine passende Antwort gefunden?

Fragen Sie die Community