Im Reich des Königs Robert gibt es mehrere Firmen, die Botendienste anbieten. Die Firmen bieten verschiedene Tarife an. Robert hat drei Bedingungen aufgestellt, denen alle Tarife genügen müssen.
Bezeichnen A, B, C Orte in Roberts Reich und d(A,B) den Preis, um eine Botschaft von A nach B zu bringen, so lauten Roberts Bedingungen:
- d(A,A) = 0 für jeden Ort A (ohne Bewegung der Boten kein Geld)
- d(A,B) = d(B,A)>0 für B≠A (jeder Weg wird bezahlt; gleiche Kosten für Hin-und Rückweg)
- d(A,C) ≤ d(A,B) + d(B,C) (Der direkte Weg von A nach C darf nicht mehr kosten als ein Weg, der von A über eine Station B nach C führt)
Bezahlt wird in der Währungseinheit Caramba ( Ca). Ein Ca ist viel wert, und so bietet eine Firma den folgenden Tarif D (A,B) an, um einen bestehenden Tarif d (A,B) zu unterbieten.
D(A,B) = min(d(A,B); 1). In Worten: D(A,B) ist das Minimum der beiden Zahlen d(A,B) und 1. Das bedeutet, dass der Tarif d(A,B) "gedeckelt" werden soll. D(A,B) ist so lange gleich d(A,B), wie d(A,B)< 1 Ca. Erreicht oder übersteigt d(A,B) 1Ca, so ist D(A,B) = 1 Ca.
Aber ist der Tarif D zulässig, erfüllt er König Roberts Bedingungen?