I'm with Gavin--we are not talking about sorting algorithms--we already know a vector of final index numbers (or two vectors, one for forward sorted and one for backward). I think we would like a logistical algorithm--one that requires the fewest Steps as defined clearly by Pickett: remove "i", slide some down, insert "i" in the "i-th" slot, slide some up The OP doesn't require this, but the OP DOES request to know the maximum fewest steps for N DVDs. I did exhaustively verify that every permutation of 12345 can be changed to either 12345 or 54321 in two Steps or less. I'm struck at how hard even this seemingly easy problem is: I can't straighten out BAKFHJCIDGE in under 7 moves. Nice problem, BMAD.
Part A ) I can identify weights of all bells in 6 weighings or less. I don't know what B ) means. In what follows, "L" means "Low", "H" means "High". The results of a weighing are always Equal (all three pans equal weight), LL (two Low pans are equal, third is lighter), L (one Low pan is lowest, other two pans are lighter and indeterminate)
Even more mature reflection suggests that relaxing ( 3 ) is not realistic--you would NOT have left off such a key rule. So, I propose relaxing my interpretation of ( 2 ). Please tell us if this is acceptable:
Gavin, mature reflection suggests to me that my assumptions ( 1 ) and ( 2 ) above are good assumptions, that make an interesting, challenging puzzle, but that ( 3 ) makes it impossible. ( 1 ) makes it possible to keep some information about each flag; ( 2 ) if you had infinite precision arithmetic, then one number could act as all of memory, large enough to contain a map of the entire maze, so restricting to finite sized numbers makes the puzzle interesting; ( 3 ) If the robot could leave breadcrumbs (Tremaux's algorithm, noted by DejMar), then you could imagine a strategy in which the robot uses the maze itself as the unbounded memory, tallying flags that have no breadcrumbs on them, and figuring out a way to determine that it has seen all of the boundary and all of the insides. So, did you somehow accidentally leave out one of the rules (I doubt it, as you a careful guy, but I can hope...), and the robot IS permitted to leave more than just a flag in a maze cell?
Bonanova, thanks for the clarification for how to use the explicit bin-centered velocities. But even more, I'm most excited by the observations that (a) only 4 of the 24 cases have mixed results ( either A or E ), and the notion of complementary cases (3124, 1243) and (2134, 1342). I'm less convinced of the assignment of I/(n+1) for velocities (I don't have clear enough vision) But it seems to me that the notion of complementary cases renders those assignments unnecessary. As you showed, 20 of the cases give unequivocal results without using explicit velocities, and the other four can be easily proven to be exact complements, so that those four add up to exactly two cases, also without explicit velocities. From this, I think we should be able to automatically analyze most of the 6! Cases, and list the remainder. Perhaps it will be obvious that we can automatically find complementary pairs again. As you said, the rationalization for the next coefficient is still missing... Oh well!
I'm still slow. How do those numbers help us know the annihilation order? Suppose there are 4 bullets, with velocities 2/5, 4/5, 3/5, 1/5 Don't I still need to compute collision times to discover whether it's zilch or escape? I gather from your note that these numbers are sufficient to recognize the pattern.