Skip to content

Instantly share code, notes, and snippets.

@michalmarczyk
Created November 2, 2018 21:54
Show Gist options
  • Save michalmarczyk/d3a156bae5945ad3ab058d1b7b6c8d72 to your computer and use it in GitHub Desktop.
Save michalmarczyk/d3a156bae5945ad3ab058d1b7b6c8d72 to your computer and use it in GitHub Desktop.
Proof that any solution to the "shipping puzzle" of https://kevinlynagh.com/notes/shipping-puzzle/ is optimal

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( mincity(left, right) | city @ boundary )

mincity(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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment