[ Post a Response | Puzzles Forum ]
Posted by markr on 16/9/2009, 6:37 am, in reply to "General passageway"
Denis,
There can't be a general formula for the minimum time based only on k=f+c, a, b, and c when m equals two.
Consider these six people:
a, b>a, c>b, d>c, e>>d, f>>d (>> means much greater than)
All solutions can be put in the form:
3 across
1 back
3 across
2 back
3 across
because the reverse of a solution is a solution.
Assume the minimum time is not dependent on d (only k, a, b, and c).
Clearly, e and f need to cross together. Therefore, they must go in the first or second group of three. Since the total time is not dependent on d, d must go with them. However, that means d comes back alone and factors into the total time. This contradicts the assumption.
Therefore, they must go in the second group of three, and this is the quickest sequence:
a, b, c ->
<- a
d, e, f ->
<- b, c
a, b, c ->
The time for this sequence is f+3c+a, and it is the best we can do assuming that the time function is not dependent on d.
Now, consider this sequence:
a, e, f ->
<- a
a, b, d ->
<- a, b
a, b, c ->
The time for this sequence is f+d+c+b+a.
Comparing the times, we can see that if b+d < 2c, then the second sequence is quicker than the first.
Therefore, a general formula for the minimum time can't strictly be based on k, a, b, and c when m equals two.
I suspect this may also be true for m > 2. I'll let MD prove that. 
Message Thread:
« Back to thread