Suppose you know that 0 <= x1 <= x2 <= x3 <= ... etc.
How do you know whether one set of coefficients [a1, a2, ..., an]
produces numbers that are always less than another set [b1, b2, ...,
bn]?
That is, how do you determine for all
0 <= x1 <= x2 <= x3 <= ... <= xn
that
a1x1 + ... + anxn <= b1x1 + ... + bnxn ?
Primitive operations:
If you increment a coefficient, you increase the result:
[ ... +1 ... ]
If you subtract 1 from a lower coeff and add it to a higher coeff, you increase the result:
[ ... 1 .... +1 ... ]
Question: Does the cumulative operator achieve the comparison?
L = [[1 0 0 0]
[1 1 0 0]
[1 1 1 0]
[1 1 1 1]]
1. It has the correct result on the zero vector, returning 0.
2. It's linear, so we just have to show that the primitive increments have the right effect.
Increment a coefficient:
L [... +1 ...] = [0 0 ... 0 1 1 1 ... 1]
Decrement and increment:
L [... 1 ... +1 ...] = [0 0 0 1 1 1 ... 1 0 0 0 0]
No go.
Hm. Maybe we need it to go right to left?
L = [[0 0 0 1]
[0 0 1 1]
[0 1 1 1]
[1 1 1 1]]
L [ ...+1...] = [1 ... 1 0 0 0 0 0]
L [ ... 1 ... +1 ...] = [0 0 0 ... 1 1 1 1 0 0 0]
Now we've got something that always increments! Excellent.
** Proof of optimality
I'll want to prove that:
1. There are two optimal strategies: escorted by 1, or the 12
ratchet. Which is better depends on whether A+C <=> 2B.
2. You are allowed to start with the heaviest (slowest) without loss of generality.
3. In an optimal strategy, you'll alternate moving two people across
and one person back. You can always avoid moving one person across
or two people back.
4. The optimal cost for moving n people is less than the optimal cost
for moving n+1 people.
Well this wouldn't be true if the fastest person moved
instantlythen you could escort people with effectively [0 1
... 1 1] which is faster than the other proposals.
What if the statement is instead: if you can optimally transport n
people in a certain time, it will take you longer to transport n
people plus an additional person with positive speed.
What if I do it for n+2 people instead? Would that be easier to
prove given that people can double up on the trip?
5. If the slowest people have already crossed, they will never (in an
optimal strategy) need to cross back to the beginning.
(Might be able to prove this by showing that one of the other
strategies such as 1 escort is better than any strategy where the
slowest person crosses back, even if the 1 escort isn't the optimal
strategy here.)
6. The strategy of moving the two slowest people over first (which
allows us to take advantage of the previous result) is
optimal. That is, the greedy solution is globally best.
7. The puzzle takes at least 2n3 moves to solve, simply to get the
appropriate number of people across and carry the flashlight back
and forth. The exception is the trivial case with one person, which
can be solved in one move.
The 1 escort takes two moves and transfers net one person across.
The 12 ratchet takes four moves and transfers net two people
across.
Hence ratchets and escorts both keep this bound.
8. Every puzzle solution, even the suboptimal ones, require an odd
number of moves. Proof: To finish, you must end up with the
flashlight on the far side, which happens exactly on the odd
moves. (If the flashlight is on the original side, someone is
holding it there and hence that person hasn't crossed yet. )
9. Taking more than 2n3 moves (when n>1) is never optimal. Hence the
optimal strategy takes exactly 2n3 moves (when n>1).
Proof: Suppose you have a solution with more than 2n3 moves. Let's
consider an altered version where every pair of moves is replaced
with a 1 escort (or 12 ratchet).
 The cheapest way to get any two guys over is sending them as a pair PQ.
 The cheapest way to get any two guys over /and return the
flashlight/ is sending them as a pair in the case where,
miraculously, 1 is on the other side and returns the
flashlight.
 If 1 is on the original side, the cheapest way to send PQ and return
the flashlight is either the 1 escort or 12 ratchet.
 The 1 escort is (A,P),(A),(A,Q),(A) and costs 2A + P + Q.
 The 12 ratchet, if 2 is on the original side, is
(A,B),(A),(P,Q),(B) and costs A+2B+Q.
 The 12 ratchet, if 2 is on the opposite side, is (P,Q),(B) and
costs Q+B.
 You can do an alternative escort, sending P and Q separately. This
looks like (X,P), (Y1,Y2), (Z,Q), (W1,W2). Of course, a 1escort
is cheaper. Also assuming we can establish that (1) optimal return
trips always send one person (2) in an optimal trip, you can
arrange it so that each person except perhaps the two fastest,
travel exactly once (...)
 You can do an alternative ratchet, sending P and Q together.
 Okay, suppose you have a solution that takes more than 2n3 moves
(for n>1). If every return trip is a (1), (2), or (1,2), then every
other guy makes a one way trip. Why not just do ratchets and
escorts?
 Within this solution, delete all useless loops.
 Within this solution, find all move sequences of the form
(1,P)(1) and move them toward the front. This change doesn't
affect the cost or the legality of any subsequent moves (except
maybe the ones after escorting 1&2 in the end, which would
interfere with loops). Find all move sequences of the form
(2,P)(2), replace them with (1,P)(1) and move them to the front
as well. Same deal.
 Now consider the first move made after all of these escorts are
finished. In the current state, we have 1 and 2 on the original
side, some number of escorted people who have already finished
their oneway trip, and some number of people left to make theirs.
 If we've escorted everyone, we're done. This is already an all
escort solution.
 Otherwise, 1 and 2 aren't the only ones left (or else we'd just escort them and be done.)
 Consider the first move.
 (P,Q) : impossible, because the return trip must be (1) or
(2). Hence one of the travelers must always be 1 or 2.
 (1)(1), (2)(2) : skippable because the return trip would make
this useless.
 (1,P)(1) : keep it. optimal.
 (2,P)(2) : replace with (1,P)(1); same state.
 (1,2)(1)???(1).
 Must be (1,2)(1)(1,P)(1). In this case, instead let's do
(1,P)(1)(1,2)(1). Same initial and final state, same cost.
 (1,2)(1)???(2).
 Might be (1,2)(1)(1,P)(2), in which case instead do
(1,P)(1)(1,2)(2). Same inital and final state, same cost.
 Might be (1,2)(1)(P,Q)(2), which is a ratchet. keep
it. optimal.
 (1,2)(2)???(2).
 Must be (1,2)(2)(2,P)(2), in which case it's cheaper to do (1,P)(1)(1,2)(2).
 (1,2)(2)???(1).
 Might be (1,2)(2)(2,P)(1), in which case it's a
ratchet. Optimal. Weird to use 2 instead of 1 as escort, but not
less optimal given that P is the limiting factor.
 Might be (1,2)(2)(P,Q)(1), in which case it's a ratchet. keep it. optimal.
 By similar reasoning, all subsequent moves must follow these
constraints as well. Hence we have the result: among solutions
whose return trips consist only of 1 and 2, there's a solution
which uses only ratchets and escorts and doesn't cost any more.
 It must use exactly 2n3 moves, because each of the guys besides 1
and 2 move rightward exactly once. The guys who are part of a
ratchet take 4 moves (2 apiece), the guys who are part of an
escort take 2 moves (2 apiece), and finally 1 and 2 go together in
the end. (1 more).
 Can we prove that in the optimal solution, return trips consist
only of 1 and 2? If we could, we'd be done.
It cannot be of the form PQ because the
return trip must be (1) or (2). We can safely ignore it if it's (1)
or (2) because the return trip would return it back to the status
quo. Therefore, it must be of the form (1,2)(1), (1,P)(1), or
(2,P)(2). If it's (2,P)(2), let's instead do (1,P)(1) which
accomplishes the same thing but cheaper. If it's (1,2)(1), then we
might have (1,2)(1)(P,Q)(2) or (1,2)(1)(1,P)(1) or
(1,2)(1)(1,P)(2).
Consider all of the people except the two fastest. Each of them has
a oneway trip. If it's of the form 1Q, we'll keep it. If it's of
the form PQ, we'll have a 12 ratchet 12,1,PQ,2, tailored to suit
whichever of 1 and 2 is on each side.
If it's of the form 2Q, instead we'll have an escort 1Q (?). If it's
of the form PQ,
Get rid of any useless loops, where (1) or (2) travel rightward
alone. [what to replace them with?]
 Attempted proof: You can always find an optimal trip where the
return journeys consist of 1s and 2s only.
 Consider a given solution.
 We'll successively modify it. We'll ensure that with each chunk of
path we modify, that the initial and final states remain
equivalent. Furthermore, we'll ensure that 1 and 2 don't swap
sides during the chunk.
 Consider the first move. It must have two people in it or else
there's no point. PQ. One of them must return with the flashlight.
 (P,Q)(P) or (P,Q)(Q).
 If the faster person returns (P,Q)(P), it's cheaper and stateequivalent to use (1,Q)(1).
 If the slower person returns (P,Q)(Q), why? You want to deposit P on that side, so use (1,P)(1).
 Now there's something R on the opposite side. Does it ever make a
return trip? If not, we've just escorted it. We can ignore it
henceforth.
 Otherwise, if it returns with someone else (R,X), just delete R's
round trip entirely. Instead of (1,R)(1)...(R,X), just do
...(X). It's state equivalent and cheaper.
 Otherwise, if R returns alonemaybe let it be for now.
replace R with 2 on that journey [??? highly disruptive of the
invariant]. Instead of (1,R)(1)...(R), use (1,2)(1)...(2).
 Now within that [...] period, we have 2 on the right hand side.
 Were there any journeys involving 2 within that period in the
original sequence?
 If 2 goes across and remains there, then forget about the terminal (2) step.
 If 2 goes across and comes back, send 1 in its place. (But what
if there was a 12 ratchet within that region?)
 Okay, so now we have (1,R)(1) .... (R).
 (1,R)(1)(X)(R) is silly; replace it with (1,X)(1).
 (1,R)(1)(A,B)(R) is a ratchet. If A=1, (1,R)(1)(1,B)(R),
just do an escort (1,B). If A=2, then R isn't 2 so
(1,R)(1)(2,B)(R), just send (2,B). If neither A,B are 1 or 2,
 Never send 1 over alone. Suppose in the original solution 1
travels and never comes back. Probably by the pigeonhole
principle, /someone/ has to be an escort (2n people traveling
rightward each time and 1 traveling leftward each time, and the
solution must have 2n3 steps). Someone has to go there and back
and there again.
Someone takes the flashlight back immediately after 1 makes its
one way trip. Can 1 safely take that person's place in all
subsequent moves? Well, if that person is 2, then we have some
complications with ratchets (they're not 12 ratchets
however). But otherwise, yes.
Nice result: If 1 ever gets sidelined, going across but never
going back even though the solution is ongoing, you can improve
the solution by having 1 take the place of the one that does go
back.
 Ah, the following are equivalent: In a particular solution, the
only return trips involve 1 and 2. In a particular solution, every
guy besides 1 and 2 makes a oneway trip.
Hence we can prove the 1 and 2 return trip thing by proving that
we can reduce everyone else to a oneway trip.
 Suppose P goes and comes back. PQ...P....PR. Suppose for
simplicity that Q never comes back. Then actually, we can instead
send "... QR ..." without affecting the state conditions and while
saving cost. (?) But it does affect state conditions because now P
is not on the far side. If we had our invariant, we could do
PQ..P..PR replaced with 1P, 1,...QR, for savings.
Suppose PQ go and each of P and Q come back later. If they next
come back together, it's a useless loop. If we have our invariant,
we can send (1,2) in place of P and Q, for savings. (But what
about using 1 and 2 in the meantime, in between PQ ... P, Q?)
 In an optimal strategy, you can always arrange so that ONE PERSON
TRAVELS LEFTWARD.
 Suppose two people travel leftward. Have both of them not travel
rightward their most recent time and not travel leftward. Now
you've saved (PQ) at least, and nothing in the state space
depends on them.
 In an optimal strategy, you can always make it so that TWO PEOPLE
TRAVEL RIGHTWARD each time. [not proven yet]
 Consider one person traveling rightward. (Assuming there's more
than one person traveling). It doesn't make sense on the first
move because then (if there is more than one person) you have to
head right back.
 Suppose we can always arrange it so that no one travels rightward
alone on the first n rightward moves. Consider the (n+1)st such
move. If one person P travels rightward on that move, then (by the
previous leftward result), one person Q travels leftward in the
next step. How did that person get there? Either Q=P and we have a
useless loop we can excise, or by the induction hypothesis, Q was
escorted by someone: QX. Replace QX with PX, and delete both P's
rightward journey and Q's leftward journey. This doesn't affect
the dependency structure. [well, but what if P was doing work in
between QX and P?]
#  Suppose it doesn't make sense for any of the first n rightward
# moves. That is, if you have an optimal strategy, then the first n
# moves never make sense to
It doesn't make sense on any return move because if P crosses
rightward alone and Q crosses leftward alone, [...]?
 What happens if 1 replaces the faster member of each rightward pair,
and is always the returning party?
 Then you run into a situation where you have PQ>Q .... QX. If you
replace Q with 1, then you have P1>1 ... Q1 ?? can't happen
because Q is no longer on the left side. Oh, but it is. But you
have two unsatisfiable criteria, don't you?
 Suppose P > Q. Then PQ > P ... PX becomes P1 > 1 > ?. If P > X,
then it becomes P1 > 1 ... P1, which you can't do because P is
not on the left. If P < X, then it becomes P1 > 1 ... X1.
 Okay, let's just shatter everything. Given a solution, consider
each move in turn. If the rightward move PQ is still legal
(i.e. both P and Q are still on the left), then replace P
with 1. Replace the return trip with 1, which is always possible
given the replacement we just made. If the rightward move PQ is
illegal (at least one of P and Q is not on the left), replace one
of them with 1 to make it legal (if possible). If the rightward
move PQ is completely illegal, delete it and the return move.
What if the rightward move PQ already involves 1 and or 2? We
should not alter the number of people traveling back and forth. So
if Q is 1, don't alter it. What if Q is 1 and P is illegal? Then
skip this move and the return move.
What if the rightward move PQ is permanent? Then we should
probably not substitute it. Like, what if PQ go right exactly
once? We can't do a substitution and still keep the solution
property.
Now in a complete solution, everything moves to the right at least
once.
 Let's consider each move in turn. At the beginning, 1 and 2 are on
the left. We're going to keep that invariant throughout this
entire process. We're also going to make every rightward trip
permanent for everything except 1 and 2.
Suppose one person P moves right. They might be 1,2, or something
else. If they're 1 or 2 moving rightward, delete this move and the
next one. If you deleted 2's rightward move, make a note.
Otherwise, if P is something else, it might be an illegal move
(because of what we've changed so far) if P is no longer on the
left. In that case, delete this move and the next one.
Otherwise, send 1P instead of P, and return 1 instead of whoever
comes back next time.
Suppose two people PQ move right. If it's of the form (1,2),
delete it and the next move [what about ratchets? this doesn't
work]. If it's of the form 1P, and P is still legal, let it stand
and make 1 return. If it's of the form 2P, let it be of the form
1P instead and make 1 return.
Otherwise, it's of the form PQ where neither P nor Q is equal to 1
or 2.
If they're both illegal (i.e. both P and Q are already on the
right), delete this move and the following one.
If exactly one is legal (say, P), replace it with 1P and make 1 return.
Otherwise, they're both legal. Instead of sending PQ and whatever
return, send (1,2)(1)(PQ)(2) or 1P11Q1, whichever is
cheaper. [this doesn't look like a savings, prima facie?]
Now we've made it so that everything moves right exactly once
except 1 and 2. If the solution was already in the form of
1escorts and 12ratchets, this process doesn't change
anything. Conversely, if it's not of that exact form, this changes
things.
 Can I articulate the state space dependency requirements? It's
something like if you escort someone rightward, then they depend on
you being on the left side. If you head leftward at a certain time,
then someone may depend on you being able to carry the flashlight
leftward (as in a ratchet) or it might be superfluous.
 The ratchet seems to depend on whether the PQ ever return.
 If exactly one of them returns, it's an escort. You can move the
chunk XR ... PQR...P outside of the time where you moveit doesn't depend on
you.
 The most straightforward escort is PXP, where X stays on the
right forever. All such escorts can be moved to the very beginning
of the move sequence [nowhat if X is used earlier in the move
sequence?]. Moreover, they can be safely replaced with 1X1.
 If PXP and X stays on the right forever, this move sequence
cannot be moved left of any time that P is on the left (because
then it will violate the state requirement that P be on the left,
and the requirement that X eventually be forever on the right.)
So it looks like:  P< X< PX> P<  And we can't move PX> anywhere
left of these endpoints (unless they're just at the beginning of
the game).

# Among the original moves, there may be a time where PQ move
# rightward as a pair exactly once and never come back. If these are
# 1 & 2, they'll go at the end as usual. Otherwise, replace this move
# with a 12 ratchet of PQ. This takes four moves and costs A+2*B+Q,
# which is more than Q, I know. But the cheapest way to transfer any
# two people is with a onetwo ratchet.
# Let A_1 .... A_k be the costs of the people who moved rightward and
# were the slowest person in their group; let each person be
# represented at most once (no duplicate costs for multiple
# journeys).
# Let B_1 ... B_m be the costs of people who moved rightward and
# weren't the slowest person in their group (masked speed).
# Replace one instance of every A_i trip and whatever return with an
# 1 & A_i escort followed by a 1 return. This swap costs no more, and
# is probably cheaper owing to the fastest person being the return
# trip.
# Replace the
# By the pigeonhole principle,
# If you have more than two people, you can't solve it in a single
# move but have to take at least two moves. In those two moves, you
# can change the net number of transferred people by 0 (two there and
# back; one there and back), by 1 (one there, two back), or by +1
# (two there, one back). The 1 case brings us to an inductive
# step. The 0 case brings us back to where we're started, plus two
# more.
We can prove, by exhaustion, the base cases:
 When there are three people crossing, the best strategy is the 1
escort. It costs [1 1 1].
 When there are four people crossing, the best strategy is either the
1 escort ([2 1 1 1]) or the 12 ratchet ([1 3 0 1]), depending.
There's an invariant I hope to maintain, which is that the flashlight
is on the original side along with 1 & 2, the two fastest people, and
everyone on the opposite side is slower than everyone on the original
side. Call this the invariant condition.
Okay, let's prove (3): if the slowest people have already crossed,
they will never (in an optimal strategy) need to cross back to the
beginning.
Suppose we're in the invariant condition with n people on the original
side, including 1 & 2. Seems clear that the optimal strategy is to
ignore the slower people on the far shore and just solve this reduced
problem on n people. Can we prove it?
If it's two, just send those two over and the puzzle is finished. If
it's three people, let 1 escort them. It will cost [1 1 1 0]. If you
bring a slower person over, you now have a 4person problem which you
can solve in either [2 1 1 1] or [1 3 0 1], not counting whatever you
did to bring the slower person /back/ onto your side. These are
already more expensive than [1 1 1 0], so you won't bring any slower
person back over in the optimal case.
What about more than three?
In your first move, you must send two people over. (If you send one person over, they must come right back).
In your second move, you must send one person back. (If you send two people back, you've made a loop with no progress.)
In your third move, you should probably send two people over. If you
send one person over, then one new person has to come back and take
their place. You have subbed one person for another. It has cost you
one walk time from each of them and now you have to solve the optimal
strategy with them.
Okay suppose you have an optimal strategy for getting n people
over. How does the heaviest person get across, and who brings the
flashlight back?
If you move two people back, you've made a mistake. How will they each
get across again? If they go together, then you've looped without
reason. If they come across alone, then they shouldn't have come back
in the first place; you can save time by cutting out that round
trip. Suppose one of them (P) comes back with another different one
(X). The cost of P's return trip is at least P, and the cost of X's
trip forward is at least X. If you eliminate P's return trip and
escort, the end state is exactly the same but the cost is at least the
same and probably cheaper.
What if the two that return will escort others, perhaps multiple
others, before finally coming back in a pair? Does this argument still
apply?
Yes. The question to consider is what each of their next trips back is
like. Call the two people moving back P and Q. There are three
possible subsequent return trips:
1. Alone.
2. PQ
3. PX (escorting something else)
Suppose they both come back as escorts PX and QY. Someone (A) has to
bring the flashlight back, so the overall cost is (PQ), (PX), A,
(QY), plus whoever brings the flashlight back and gets A
across: (B), (AC). Suppose P < Q. Then instead we
could've paid P, (PX), ...
Lemma: In an optimal path, anyone who brings the flashlight back must
cost less than the person they subsequently escort over (This proof
assumes we already know that in an optimal path, we can always choose
to have exactly two people come over and exactly one person come back
in every step).
Supposing the fastest person takes no time at all, you can do the
escort strategy in time [0 1 1 1 ... 1]. What about a superfast
ratchet? If the two fastest people take no time at all, you can
ratchet everyone in time [0 0 0? 1 0 1 0 1 .. 0 1]