Some Generalizations of the Bridge and Torch Problem

For the classic bridge and torch problem with crossing times $\left\{1,\ldots,n\right\}$ , the optimal crossing time $T\left(n\right)$ is already known: it is recorded in A078476, and it follows from the optimal recursive procedure of Rote. We give a short derivation of the closed form

$\displaystyle T\left(n\right)=\frac{n^2}{4}+3n-5+\frac{\left(-1\right)^n-1}{8},$

where $n\ge 2$ . We also determine a secondary quantity exactly: the least number of trips made by the fastest person in a schedule of minimum total time is $2\lceil \frac{n}{2}\rceil-1$ . We then generalize the problem to a bridge of capacity 3, and prove that

$\displaystyle T_3\left(n\right)= \frac{n^{2}}{6}+2n-\frac{181}{36}+\frac{\left(-1\right)^{n}}{4}-\frac{2}{9}\cos\left(\frac{2n\pi}{3}\right)$

for all $n\ge 7$ . The resulting values form A392834. Lastly, we explore the problem on star graphs, where we determine the optimal time exactly in the regime of abundant torches, and the answer turns out to be a partial sum of a floor function, giving a scheduling interpretation of several sequences of such partial sums.

Some Generalizations of the Bridge and Torch Problem

Thang Pang Ern Department of Mathematics National University of Singapore 10 Lower Kent Ridge Road Singapore 119076 Gerard Sayson Nanyang Junior College 128 Serangoon Avenue 3 Singapore 556111

Thang Pang Ern
Department of Mathematics
National University of Singapore
10 Lower Kent Ridge Road
Singapore 119076
Gerard Sayson
Nanyang Junior College
128 Serangoon Avenue 3
Singapore 556111