Am wenigsten Fahrten würden benötigt, wenn jeweils 2 Käfer hin (Maximum) und einer (Minimum)
zurück fahren würde. (Die Anzahl der Rückfahrten ist um eins kleiner als die hinwärts.)
10 -(n+1)*2 + n*1 = 0 => n = 8
Also 9 mal hin und 8 mal zurück.
Leider können die zwei 10-Pkt-Käfer nur allein hinwärts fahren => es sind noch 2 ihrer Käfer im Süden,
die nicht mehr aufs Boot passten.
(Da nun mit der Rückfahrt begonnen wird, ist die Anzahl der Hin- und Rückfahrten gleich.)
2 -m*2 + m*1 = 0 => m = 2
Also 2 mal hin und 2 mal zurück.
Summe der Einzelreisen:
9*2 (doppele Hinfahrt)
+2*1 (einfache Hinfahrt)
+10*1 (einfache Rückfahrt)
= 30
Es müssen also mindestens 30 Einzelreise unternommen werden. Das sind 3 Reisen pro Käfer.
Da das auch das erlaubte Maximum ist, folgt, dass genau 30 Einzelreisen unternommen werden.
Außerdem folgt daraus, dass 9+2= 11 (Hinfahrten) Läuse mit rüber genommen werden.
Die Käfer 3, 4, 6 & 7 müssen umlackiert werden, da ihre Punkte nicht zu Rückreise passen.
Die Käfer 2 & 5 (je 10 Pkt.)müssen umlackiert werden, da sie sonst wieder allein nach Norden reisen müssten, dann aber nicht
mehr alle Käfer dort ankommen könnten (s.o.).
=> mindestens 6 Läuse zur Umlackierung
=> Es können netto maximal 11 - 6 = 5 Läuse 'gerettet' werden.
(Die Käfer sollten sich also vor ihrer jeweils letzten Nordfahrt besser noch mal richtig satt essen.
)
Eine bessere Lösung als 5 ist also nicht möglich. Eine möglich Variante, um dieses Maximum zu erreichen, ist:
N: nach Norden, S nach Süden, L: Umlackieren, Käfernummer(Punktanzahl[>neu auflackierte Punktanzahl])
N 3(1) & 7(7)
L 3(1>2)
S 3(2)
N 3(2) & 1(6)
S 1(6)
N 1(6) & 8(4)
S 8(4)
N 8(4) & 9(2)
S 9(2)
N 9(2) & 10(8)
S 10(8)
N 4(5) & 6(5)
L 4(5>2)
L 6(5>4)
L 7(7>4)
S 4(2)
N 4(2) & 10(8)
S 6(4)
N 5(10)
S 7(4)
N 2(10)
L 2(10>6)
L 5(10>6)
S 5(6)
N 5(6) & 6(4)
S 2(6)
N 2(6) & 7(4)
Aber wehe jetzt findet jemand eine bessere Lösung.
