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 1-2 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 instantly---then 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 2n-3 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 1-2 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 2n-3 moves (when n>1) is never optimal. Hence the optimal strategy takes exactly 2n-3 moves (when n>1). Proof: Suppose you have a solution with more than 2n-3 moves. Let's consider an altered version where every pair of moves is replaced with a 1 escort (or 1-2 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 1-2 ratchet. - The 1 escort is (A,P),(A),(A,Q),(A) and costs 2A + P + Q. - The 1-2 ratchet, if 2 is on the original side, is (A,B),(A),(P,Q),(B) and costs A+2B+Q. - The 1-2 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 1-escort 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 2n-3 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 one-way 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 2n-3 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 one-way trip. If it's of the form 1Q, we'll keep it. If it's of the form PQ, we'll have a 1-2 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 state-equivalent 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 alone----maybe 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 1-2 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 2n-3 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 1-2 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 one-way trip. Hence we can prove the 1 and 2 return trip thing by proving that we can reduce everyone else to a one-way 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 (P|Q) 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 1P-1-1Q-1, 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 1-escorts and 1-2-ratchets, 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 ... PQ-R...P outside of the time where you move---it doesn't depend on you. - The most straightforward escort is PX-P, where X stays on the right forever. All such escorts can be moved to the very beginning of the move sequence [no---what if X is used earlier in the move sequence?]. Moreover, they can be safely replaced with 1X-1. - If PX-P 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 1-2 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 one-two 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 1-2 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 4-person 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 (P|Q), (P|X), A, (Q|Y), plus whoever brings the flashlight back and gets A across: (B), (A|C). Suppose P < Q. Then instead we could've paid P, (P|X), ... 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]