Proof that any solution to the "shipping puzzle" of https://kevinlynagh.com/notes/shipping-puzzle/ is optimal

shipping-puzzle.org

Any solution is optimal, it’s ok to just join legs until no longer possible

General observation:

Any solution can be obtained by merging routes two at a time

This can be thought of as merging two edges in a DAG

Thus the number of edges is reduced by 1 at each step

Inductive proof

Induction on maximum length of route (i.e. number of days - 1)

Base case: 1 (only considering Monday-Tuesday flights)

Trivial, only one solution possible – no joins – one plane per leg

Inductive step:

Hypothesis: for max route ≤ n all solutions are optimal

1. Show that any extension of an optimal solution is a solution

“Extension” means take a solution for the first n days, add final day

Each final-day leg can be joined to any route that ends at its source

Clearly doesn’t matter which one

Done once we run out of final-day legs or routes to join them to

At this point any leftover final-day legs become one-leg route

No way to do better assuming the first-n-days solution remains fixed

2. Show that a solution thus obtained is necessarily optimal

Suppose otherwise and let X be a superior competing n+1-day solution

Discard final-days legs from X obtaining a solution X’ for n days

Since X has the same endpoints as the original n-day solution…

…we cannot add more final-day legs to those endpoints than previously…

…thus X’ must be an n-day solution superior to the first one we had…

…but this contradicts the assumption of the latter’s optimality

Direct proof

Start from the general observation

Note that there is a fixed number of merge opportunities at any day boundary

E.g. Wednesday/Thursday – choices at other boundaries irrelevant

Any optimal solution will take as many of those as possible

Keep merging until we run out of matching pairs of endpoints…

…which always happens after the same number of mergers…

…specifically sum( min_city(left, right) | city @ boundary )

min_city(left, right) means the smaller of:

number of edges ending in {city} among the earlier legs

number of edges starting in {city} among the later legs

city @ boundary means the set of:

cities represented among the legs that start/end at this boundary

We do this for every boundary

Number of mergers is fixed at each boundary (see above)

Mergers at different boundaries are independent

Thus the total number of mergers is fixed