\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{float}
\usepackage{psfig}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{fullpage}

\usepackage{diagbox}
\usepackage{array}
\usepackage{doi}
\usepackage{url}
\usepackage{caption}
\usepackage{color}
\usepackage{enumitem}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{tikz}
\usetikzlibrary {arrows.meta}
\usetikzlibrary{decorations.pathmorphing,shapes.geometric,positioning}
\tikzset{note/.style={font=\small}}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf Some Generalizations of the \\
\vskip .15in
Bridge and Torch Problem
}
\vskip 1 cm
\large
Thang Pang Ern\\
Department of Mathematics \\
National University of Singapore \\
10 Lower Kent Ridge Road \\
Singapore 119076 \\
\href{mailto:thangpangern@u.nus.edu}{\tt thangpangern@u.nus.edu}
\vskip 1 cm
\large
Gerard Sayson\\
Nanyang Junior College \\
128 Serangoon Avenue 3 \\
Singapore 556111 \\
\href{mailto:gerard@gsn.bz}{\tt gerard@gsn.bz}
\end{center}

\vskip .2in

\begin{abstract}
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 \seqnum{A078476}, and it follows from the optimal recursive procedure of Rote. We give a short derivation of the closed form \[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 \[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 \seqnum{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.
\end{abstract}

\section{Introduction}
The bridge and torch problem is an interesting scheduling puzzle: a group of people must cross a single bridge at night with one torch. At most two people can be on the bridge at any time, the torch must be carried on every crossing, and a pair moves at the speed of its slower member. Assign each person a crossing time. The goal is to move everyone from the left side to the right side in minimum total time (Figure \ref{fig:Visualizing the bridge and torch problem}).

This problem has appeared in many forms over the years with various anecdotes attached to it. There are numerous names such as the bridge-crossing puzzle, the four men problem, the flashlight puzzle etc. The oldest reference of this classic problem is a puzzle book by Levmore and Cook \cite{LevmoreCook1981}. The well-known version with four people whose crossing times are $1,2,5,10$ units is perhaps the most common \cite{Rote2002}. Beyond being a fun puzzle, the bridge and torch problem is also a neat example of an optimization task with constraints and trade-offs. With only a few simple rules, it forces careful thought about order and timing. It has also often been used to introduce ideas from computer science, such as dynamic programming.

The general problem is well understood. Rote \cite{Rote2002} solved the capacity-two problem for arbitrary crossing times $0<t_1<\cdots<t_N$, and his analysis ends with an optimal recursive procedure. Jianu, Jianu and Popescu \cite{JianuJianuPopescu2020} later gave a combinatorial proof of the same result. For arbitrary capacity $c$, Backhouse \cite{Backhouse2008} treats the capacity-$c$ torch problem with the capacity and the crossing times among the inputs, and obtains an algorithm whose number of primitive computations is proportional to the square of the number of people; Backhouse and Truong \cite{BackhouseTruong2015} revisit the problem by dynamic programming. Consequently, \emph{computing} the optimum for a given instance is not the issue here. What can still be of interest, and what we pursue, is the shape of the answer for the particular family of crossing times $t_i=i$: for such instances one may hope for a short closed formula, and for a description of the structure of the schedules that attain it.

Our contributions are as follows.
\begin{itemize}
\itemsep 0em
\item In Section \ref{section:capacity two}, we revisit the known formula for $T(n)$ by specializing Rote's procedure. We then consider a secondary objective, and show that the least number of trips made by the fastest person in a time-optimal schedule is $2\lceil \frac{n}{2}\rceil-1$ (Proposition \ref{proposition:a(n) nice odd}).
\item In Section \ref{section:capacity three}, we treat the capacity-three case with crossing times $\left\{1,\ldots,n\right\}$ and determine $T_3(n)$ exactly for $n\ge 7$. The upper bound is a block construction. The lower bound is proved by exhibiting a system of weights which is verified one move at a time, so that no reasoning about the order of moves, the states visited, or the pattern of returns is required.
\item In Section \ref{section:star graphs}, we move beyond the simple linear `left bank to right bank' model to explore the problem on star graphs $\mathcal{S}\left(k\right)$ for $k$ leaves, allowing for multiple torches. The exact answer we obtain concerns the regime in which torches are abundant enough that no torch ever has to be returned, where the problem becomes an accessible batching problem. Moreover, the answer is a partial sum of a floor function, which gives those partial sums a scheduling interpretation.
\end{itemize}

\begin{figure}[H]
\centering
\begin{tikzpicture}[
  scale=1,
  person/.style={circle, draw, fill=white, minimum size=6mm, inner sep=0pt, font=\sffamily},
  bank/.style={fill=green!18, draw=green!40!black},
  water/.style={fill=blue!10, draw=blue!40!black},
  bridge/.style={fill=gray!25, draw=gray!55}
]

% Background river
\draw[water] (2,0) rectangle (12,6);

% Banks
\draw[bank] (0,0) rectangle (2,6);
\draw[bank] (12,0) rectangle (14,6);

% Labels for banks
\node at (1,6.35) {Left of bridge};
\node at (13,6.35) {Right of bridge};

% Bridge (a horizontal deck spanning the river)
\draw[bridge, line join=round] (2,2.5) rectangle (12,3.5);
% Planks/rails for visual clarity
\foreach \x in {3,4,5,6,7,8,9,10,11}{
  \draw[gray!60] (\x,2.5) -- (\x,3.5);
}
\draw[gray!70,line cap=round] (2,3.65) -- (12,3.65);
\draw[gray!70,line cap=round] (2,2.35) -- (12,2.35);

% Gentle waves (purely decorative)
\foreach \y in {1.0, 1.8, 4.2, 5.0}{
  \draw[blue!45,decorate,decoration={snake,segment length=12mm, amplitude=0.6mm}] (2,\y) -- (12,\y);
}

% People on the near side (aligned neatly)
% Choose tidy y-levels
\def\yA{5.1}
\def\yB{4.0}
\def\yC{2.9}
\def\yD{1.8}

\node[person] (p1) at (1,\yA) {1};
\node[person] (p2) at (1,\yB) {2};
\node[person] (p3) at (1,\yC) {3};
\node[person] (p4) at (1,\yD) {4};

% Flashlight next to the fastest
\node[star,star points=5,star point ratio=2,fill=yellow!85!orange,draw=orange!70,minimum size=5mm] (torch) at (0.5,0.7) {};
\node[note,anchor=west] at (0.8,0.7) {torch};

% “Already crossed” placeholders (aligned)
\foreach \y in {\yA,\yB,\yC,\yD}{
  \node[person,draw=gray!50,fill=gray!10] at (13,\y) {};
}

% Example crossing arrow along the bridge (center line)
\draw[-{Latex[length=2.4mm]},very thick,gray!60]
  (2.2,3.0) -- (11.8,3.0);
\node[note] at (8.7,3.25) {crossing path};

\node[person,minimum size=5mm] at (2.6,0.4) {};
\node[note,anchor=west] at (2.9,0.4) {node label = crossing time};

\end{tikzpicture}
\caption{Visualizing the bridge and torch problem}
\label{fig:Visualizing the bridge and torch problem}
\end{figure}

\section{The capacity-two case}\label{section:capacity two}
Throughout this section, the people are $\left\{1,\ldots,n\right\}$ and person $i$ has crossing time $i$. A state is a pair $\left(L,\lambda\right)$ where $L\subseteq\left\{1,\ldots,n\right\}$ is the set currently on the left bank and $\lambda\in\left\{\textsf{L},\textsf{R}\right\}$ is the position of the torch. The initial and terminal states are $s=\left(\left\{1,\ldots,n\right\},\textsf{L}\right)$ and $t=\left(\emptyset,\textsf{R}\right)$ respectively. A move sends a non-empty set $A$ of at most $c$ people, all on the side of the torch, to the other side; its cost is $\max A$, and the torch changes sides. A schedule is a sequence of moves from $s$ to $t$, and its cost is the sum of the costs of its moves. Since the torch changes sides at every move, a schedule alternates between left-to-right moves (forward moves) and right-to-left moves (returns), begins with a forward move and ends with a forward move; if it has $f$ forward moves, then it has exactly $f-1$ returns.

\begin{theorem}\label{theorem one bridge one torch with crossing times 1 to n}
Let there be $n$ persons on one side of a bridge of capacity $c=2$ with crossing times $\left\{1,\ldots,n\right\}$, and let $T\left(n\right)$ denote the optimal crossing time. Then
\begin{align}\label{theorem: optimal crossing time}
T\left(n\right)=\frac{n^2}{4}+3n-5+\frac{\left(-1\right)^n-1}{8}\quad\text{for all positive integers }n\ge 2.
\end{align}
\end{theorem}
The terms $T\left(1\right),T\left(2\right),T\left(3\right),T\left(4\right),\ldots=1,2,6,11,\ldots$ appear in sequence \seqnum{A078476}. It denotes the set of times taken to get $n$ people from one side of a bridge to the other where (a) the only \emph{flashlight} must be carried when crossing; (b) only one or two people may cross at the same time; (c) a pair crosses at the speed of the slowest member; and (d) the $k^\text{th}$ person's speed requires $k$ units to cross the bridge, where $1\le k \le n$. This sequence is a special case of \seqnum{A318271}, which denotes the optimal crossing time for the bridge and torch problem given that the crossing times for the group's members are given by the $n^\text{th}$ partition of the triangle in which the $n^\text{th}$ row lists juxtaposed lexicographically ordered partitions of $n$.

We emphasize that Theorem \ref{theorem one bridge one torch with crossing times 1 to n} is a known formula, which we revisit rather than establish for the first time. The expression (\ref{theorem: optimal crossing time}), including its parity correction, appears in \seqnum{A078476}, whose comments dated 2013 record the equivalent formulas for even and odd $n$; and, as the proof below shows, the recurrence behind it is an immediate specialization of Rote's optimal recursive procedure \cite{Rote2002}. Our reason for including a proof is that the specialization is short and elementary, and that the same summation technique is used again in Section \ref{section:capacity three}.

Also, note that equivalently, for all $n\ge 2$,
\begin{align}\label{eqn:formula for T(n)}
    T\left(n\right)=\left\lfloor \frac{n^2+12n-20}{4}\right\rfloor.
\end{align}

Before proving Theorem \ref{theorem one bridge one torch with crossing times 1 to n}, we state Lemma \ref{lemma: odd even sequence general term}, which provides the general formula of a sequence that is defined by separate formulae for even and odd terms.
\begin{lemma}\label{lemma: odd even sequence general term}
Let $f,g:\mathbb{N}\to\mathbb{R}$ and let $\left\{a_n\right\}_{n\ge 0}$ be the sequence defined by $a_{2m}=f\left(m\right)$ and $a_{2m+1}=g\left(m\right)$ for all $m\in\mathbb{N}$. Then, for every $n\ge 0$,
\[a_n=\frac{1+\left(-1\right)^n}{2}f\left(\left\lfloor \frac{n}{2}\right\rfloor\right)+\frac{1-\left(-1\right)^n}{2}g\left(\left\lfloor \frac{n}{2}\right\rfloor\right).\]
\end{lemma}
\begin{proof}
Both $f$ and $g$ are evaluated at $\lfloor \frac n2\rfloor\in\mathbb{N}$, so the right side is defined for every $n\ge 0$. If $n=2m$ is even, then $\lfloor \frac n2\rfloor=m$ and the two coefficients are $1$ and $0$, so the right-hand side equals $f\left(m\right)=a_n$. If $n=2m+1$ is odd, then $\lfloor \frac n2\rfloor=m$ and the coefficients are $0$ and $1$, so the right-hand side equals $g(m)=a_n$.
\end{proof}

We now give a proof of Theorem \ref{theorem one bridge one torch with crossing times 1 to n}.
\begin{proof}
Rote's analysis of the capacity-two problem with arbitrary crossing times $t_1<t_2<\cdots<t_N$ ends with an optimal recursive procedure \cite{Rote2002}: there is an optimal schedule in which the two slowest people $N-1$ and $N$ are transported either together, by the moves
\[\left\{1,2\right\}\to\textsf{R},\quad 1\to\textsf{L},\quad \left\{N-1,N\right\}\to\textsf{R},\quad 2\to\textsf{L},\]
with cost $t_1+2t_2+t_N$, or separately, by the moves
\[\left\{1,N\right\}\to\textsf{R},\quad 1\to\textsf{L},\quad \left\{1,N-1\right\}\to\textsf{R},\quad 1\to\textsf{L},\]
with cost $2t_1+t_{N-1}+t_N$. In either case, the remaining instance is the one with crossing times $t_1,\ldots,t_{N-2}$, and the optimum is obtained by taking the cheaper of the two options and solving that instance optimally.

In particular, for $t_i=i$ and $N=k$, the two incremental costs are $t_1+2t_2+t_k=k+5$ and $2t_1+t_{k-1}+t_k=2k+1$. Since $k+5\le 2k+1$ when $k\ge 4$, the cheaper option for every $k\ge 4$ is to transport the two slowest people together, and therefore
\begin{align}\label{eqn: T(k) = T(k-2) + k + 5}
T\left(k\right)=T\left(k-2\right)+k+5\quad\text{for all }k\ge 4.
\end{align}
For the base cases, one can directly check that $T\left(2\right)=2$ and $T\left(3\right)=6$. We then solve the recurrence relation. If $n=2m$ with $m\ge 1$, then \[T\left(2m\right)=T\left(2\right)+\sum_{j=2}^{m}\left(2j+5\right)=m^2+6m-5=\frac{n^2}{4}+3n-5.\]
On the other hand, if $n=2m+1$ with $m\ge 1$, then \[T\left(2m+1\right)=T\left(3\right)+\sum_{j=2}^{m}\left(\left(2j+1\right)+5\right)=m^2+7m-2=\frac{n^2}{4}+3n-5-\frac{1}{4}.\]
Applying Lemma \ref{lemma: odd even sequence general term} with $f(m)=m^2+6m-5$ and $g(m)=m^2+7m-2$ combines the parity cases into the single formula (\ref{theorem: optimal crossing time}), valid for all $n\ge 2$.
\end{proof}

\begin{remark}\label{remark:k=4 tie}
At $k=4$ the two incremental costs coincide, $k+5=2k+1=9$, which is the source of the non-uniqueness recorded below.
\end{remark}

\begin{remark}\label{remark:no naive shuttle}
   Optimal schedules are not unique. The shuttle schedule in Figure \ref{fig:c2 n4} attains $T(4)=11$, but its five-person analogue costs $17>T(5)=16$. The schedule $\{1,4\}\to\textsf{R},\ 1\to\textsf{L},\ \{1,3\}\to\textsf{R},\ 1\to\textsf{L},\ \{1,2\}\to\textsf{R}$ is also optimal, so arguments about when the two slowest people first arrive together fail. Hence, we rely on Rote's procedure.
   \end{remark}

\begin{figure}[H]
    \centering
    \begin{tabular}{|c|c|c|c|c|}
        \hline
        Step & Direction & People & Time & Cumulative \\
        \hline
        1 & \textsf{L} to \textsf{R} & 1, 2 & 2 & 2 \\
        \hline
        2 & \textsf{R} to \textsf{L} & 1 & 1 & 3 \\
        \hline
        3 & \textsf{L} to \textsf{R} & 1, 3 & 3 & 6 \\
        \hline
        4 & \textsf{R} to \textsf{L} & 1 & 1 & 7 \\
        \hline
        5 & \textsf{L} to \textsf{R} & 1, 4 & 4 & 11 \\
        \hline
    \end{tabular}
    \caption{One optimal schedule for $T(4) = 11$.}
    \label{fig:c2 n4}
\end{figure}

As mentioned in Remark \ref{remark:no naive shuttle}, optimal schedules are not unique. As such, it is convenient to also consider another objective where we seek to minimize the number of trips made by person 1.
\begin{definition}\label{definition:a(n)}
For $n\ge 1$, let
\[a\left(n\right)=\min\left\{\#\left\{\text{trips made by person }1\text{ in }\sigma\right\} : \sigma\text{ is a schedule of total time }T\left(n\right)\right\}.\]
\end{definition}
The restriction to schedules of minimum total time is essential. Without it, the quantity is uninteresting because person 1 may cross once and then remain on the right bank while person 2 carries the torch back and forth, so the unrestricted minimum is $1$ for every $n$.
\begin{proposition}\label{proposition:a(n) nice odd}
For all $n\ge 1$, we have $a(n)=2\left\lceil \frac{n}{2}\right\rceil-1$.
\end{proposition}
We will prove Proposition \ref{proposition:a(n) nice odd} later.
\begin{lemma}\label{lemma:d1 lower bound}
Let $n\ge 3$ and let $\sigma$ be any schedule for $\left\{1,\ldots,n\right\}$ with capacity $c=2$. Suppose person 1 takes part in $a$ forward moves, $m$ of the returns carry two people, and $s$ of the forward moves carry one person. Then,
\[\operatorname{cost}\left(\sigma\right)\ge T\left(n\right)+\left\lceil \frac n2\right\rceil-a+4m+3s.\]
\end{lemma}
\begin{proof}
Let $f$ denote the number of forward moves of $\sigma$. Since the torch changes sides at every move and $\sigma$ begins and ends with a forward move, there are $f-1$ returns.
 
Each forward move carries one or two people, and $s$ of them carry one, so the forward moves carry $2f-s$ people in total. Each return carries one or two people, and $m$ of them carry two, so the returns carry $\left(f-1\right)+m$ people in total. The two totals differ by $n$, the number of people who end up across, so 
\begin{align}\label{eqn:f count cap2}
2f-s=n+\left(f-1\right)+m\quad\text{which implies}\quad f=n-1+m+s. 
\end{align}
Person 1 starts on the left, ends on the right, and changes side at every move it joins, so its moves alternate and it makes $a$ forward moves and $a-1$ returns. The other $\left(f-1\right)-\left(a-1\right)$ returns carry nobody faster than person 2, so each of them costs at least 2, while each return containing person 1 costs at least 1. Hence, the returns cost at least
\[\left(a-1\right)+2\left(f-a\right)=2f-a-1.\]
Next, at most $s$ forward moves are cheaper than 2, since a forward move costing 1 can only be person 1 traveling alone. By $\eqref{eqn:f count cap2}$, the number of forward moves costing at least 2 is therefore at least $f-s=n-1+m\ge \left\lceil \frac{n}{2}\right\rceil$ since $n\ge 3$.
 
Next, we bound the $\left\lceil \frac{n}{2}\right\rceil$ most expensive forward moves. Fix $j\le \left\lceil \frac{n}{2}\right\rceil$ and consider the $2\left(j-1\right)+1$ slowest people, namely those with labels at least $n-2\left(j-1\right)$. Each of them goes forward at least once, and a forward move carries at most two of them, so their forward moves cannot all fit into $j-1$ moves: at least $j$ forward moves cost at least $n-2\left(j-1\right)$. Hence, the $j^\text{th}$ most expensive forward move costs at least $n-2\left(j-1\right)$, and also at least 2 by the previous paragraph. As such, the $\left\lceil \frac{n}{2}\right\rceil$ most expensive forward moves cost at least
\[S:=\sum_{j=1}^{\left\lceil \frac{n}{2}\right\rceil}\max\left\{n-2\left(j-1\right),2\right\}
=\begin{cases}\frac{n^2}{4}+\frac n2,& \text{if } n\text{ even};\\
\frac{\left(n+1\right)^2}{4}+1,& \text{if } n\text{ odd}.\end{cases}\]
The two values arise because for even $n$, the terms are $n,n-2,\ldots,2$, while for odd $n$, they are $n,n-2,\ldots,3$ followed by a final term 2 in place of 1. Each of the remaining $f-\left\lceil \frac{n}{2}\right\rceil$ forward moves costs at least 2, except for at most $s$ of them which cost at least 1, so all the forward moves together cost at least $S+2\left(f-\left\lceil \frac{n}{2}\right\rceil\right)-s$.

Hence,
\begin{align*}
\operatorname{cost}\left(\sigma\right)&\ge S+2\left(f-\left\lceil \frac{n}{2}\right\rceil\right)-s+2f-a-1\\&=S+4f-2\left\lceil \frac{n}{2}\right\rceil-s-a-1\\&=S+4n+4m+3s-2\left\lceil \frac{n}{2}\right\rceil-a-5.
\end{align*}
If $n$ is even, then $\left\lceil \frac{n}{2}\right\rceil=\frac n2$ and $S=\frac{n^2}{4}+\frac n2$, so the right side is
\[\frac{n^2}{4}+3n-5+\left(\frac n2-a\right)+4m+3s=T\left(n\right)+\left(\left\lceil \frac{n}{2}\right\rceil-a\right)+4m+3s.\]
If $n$ is odd, then $\left\lceil \frac{n}{2}\right\rceil=\frac{n+1}{2}$ and $S=\frac{\left(n+1\right)^2}{4}+1$, and $T\left(n\right)=\frac{n^2-1}{4}+3n-5$. Since $\frac{\left(n+1\right)^2}{4}-\frac{n^2-1}{4}=\frac{n+1}{2}=\left\lceil \frac{n}{2}\right\rceil$, the right side is again $T\left(n\right)+\left(\left\lceil \frac{n}{2}\right\rceil-a\right)+4m+3s$. This is the claimed inequality.
\end{proof}
 
We can now prove Proposition \ref{proposition:a(n) nice odd}.
\begin{proof}
For the upper bound, we exhibit a schedule of total time $T(n)$ in which person 1 makes exactly $2\lceil \frac{n}{2}\rceil-1$ trips. By the proof of Theorem \ref{theorem one bridge one torch with crossing times 1 to n}, iterating the cheaper option of Rote's procedure is optimal, and it consists of blocks of the form
\[\left\{1,2\right\}\to \textsf{R},\quad 1\to \textsf{L},\quad \left\{k-1,k\right\}\to \textsf{R},\quad 2\to \textsf{L}.\]
If $n\ge 4$ is even, then there are $\frac{n}{2}-1$ such blocks, followed by a single move $\left\{1,2\right\}\to \textsf{R}$; if $n\ge 5$ is odd, then there are $\frac{n-3}{2}$ such blocks, followed by the moves $\left\{1,2\right\}\to \textsf{R}$, $1\to \textsf{L}$, $\left\{1,3\right\}\to\textsf{R}$. Person 1 makes exactly two trips per block, and one further trip in the even case, respectively three further trips in the odd case, giving $2\left(\frac n2-1\right)+1=n-1$ trips for even $n\ge 4$ and $2\cdot\frac{n-3}{2}+3=n$ for odd $n\ge 5$; both equal $2\lceil \frac{n}{2}\rceil-1$. The cases $n\le 3$ are immediate.

For the lower bound, note first that for $n\le 2$, the claim is trivial, since $2\lceil \frac{n}{2}\rceil-1=1$ and person 1 must cross at least once. Suppose $n\ge 3$ and let $\sigma$ be any schedule such that $\operatorname{cost}(\sigma)=T(n)$. By Lemma \ref{lemma:d1 lower bound},
\[0=\operatorname{cost}(\sigma)-T(n)\ge  \left\lceil \frac n2\right\rceil-a+4m+3s,\]
so $a\ge \lceil \frac{n}{2}\rceil+4m+3s\ge \lceil \frac{n}{2}\rceil$. Person 1 makes $a$ forward trips and $a-1$ returns, hence $2a-1\ge 2\lceil \frac{n}{2}\rceil-1$ trips in total. As $\sigma$ was an arbitrary time-optimal schedule, $a(n)\ge 2\lceil \frac{n}{2}\rceil-1$, and with the upper bound, this gives equality.
\end{proof}
We can visualize the set of moves taken to obtain $T\left(n\right)$. We give two examples for $T\left(5\right)$ and $T\left(8\right)$ as shown in Figures \ref{fig:visualizing set of crossings for T(5)} and \ref{fig:visualizing set of crossings for T(8)} respectively. Here, each non-loop edge denotes a forward move made by the two vertices it joins, where vertex $i$ represents person $i$ with crossing time $i$; a loop at vertex $i$ denotes a solo return by person $i$. Unlike Rote's visualization in \cite{Rote2002}, ours incorporates loops for vertices 1 and 2 so that Proposition \ref{proposition:a(n) nice odd} becomes more apparent. Moreover, we have colored vertices 1 and 2 as they have more interaction than the others. We must be careful about what the loops contribute. Under the usual graph-theoretic convention, a loop adds $2$ to the degree of its vertex, whereas a solo return is a single trip. Accordingly, we do not use the degree of vertex 1, but its \emph{trip-incidence count}
\[\tau_1=e_1+\ell_1,\]
where $e_1$ is the number of non-loop edges incident with vertex 1 and $\ell_1$ is the number of loops at vertex 1; its usual degree is $e_1+2\ell_1$. With this convention, $a\left(n\right)=\tau_1$ for the displayed schedules: in Figure \ref{fig:visualizing set of crossings for T(5)} we have $e_1=3$ and $\ell_1=2$, so $\tau_1=5=a\left(5\right)$, and in Figure \ref{fig:visualizing set of crossings for T(8)}, we have $e_1=4$ and $\ell_1=3$, so $\tau_1=7=a\left(8\right)$.
\begin{figure}[H]
    \centering
    \begin{tikzpicture}[scale=1]

    % Nodes
    \foreach \x/\lab in {0/1,2/2,4/3,6/4,8/5}{
      \fill (\x,0) circle (2.5pt);
      \node[above] at (\x,0.1) {\lab};
    }

    % Multiple arcs between 1 and 2
    \draw[bend left=20] (0,0) to (2,0);
    \draw[bend left=35] (0,0) to (4,0);

    \draw (6,0) to (8,0);
    \draw (0,0) to (2,0);

    \node[circle,draw,inner sep=1.5pt, draw=red, fill=red] (v1) at (0,0) {};
    \draw (v1) edge[loop below] node[below]{2 loops} ();

    \node[circle,draw,inner sep=1.5pt, draw=red, fill=red] (v2) at (2,0) {};
    \draw (v2) edge[loop below] node[below]{1 loop} ();

    \end{tikzpicture}
    \caption{Visualizing the set of moves to obtain $T\left(5\right)$}
    \label{fig:visualizing set of crossings for T(5)}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}[scale=1]

    % Nodes
    \foreach \x/\lab in {0/1,2/2,4/3,6/4,8/5,10/6,12/7,14/8}{
      \fill (\x,0) circle (2.5pt);
      \node[above] at (\x,0.1) {\lab};
    }

    % Multiple arcs between 1 and 2
    \draw[bend left=20] (0,0) to (2,0);
    \draw[bend left=35] (0,0) to (2,0);
    \draw[bend left=55] (0,0) to (2,0);
    \draw (0,0) to (2,0);

    \draw (4,0) to (6,0);
    \draw (8,0) to (10,0);
    \draw (12,0) to (14,0);

    \node[circle,draw,inner sep=1.5pt, draw=red, fill=red] (v1) at (0,0) {};
    \draw (v1) edge[loop below] node[below]{3 loops} ();

    \node[circle,draw,inner sep=1.5pt, draw=red, fill=red] (v2) at (2,0) {};
    \draw (v2) edge[loop below] node[below]{3 loops} ();

    \end{tikzpicture}
    \caption{Visualizing the set of moves to obtain $T\left(8\right)$}
    \label{fig:visualizing set of crossings for T(8)}
\end{figure}

\section{The capacity-three case}\label{section:capacity three}
Let $c$ denote the capacity of the bridge, meaning that at most $c$ persons may be on the bridge in a single move. The classical bridge and torch puzzle corresponds to the case $c=2$, which was discussed in Section \ref{section:capacity two}. In this section, we study the bridge and torch problem for capacity $c=3$ with crossing times $\left\{1,\ldots,n\right\}$, while retaining the single-torch constraint. We write $T_3\left(n\right)$ for the optimal total time.
\begin{proposition}\label{proposition initial val t3}
$T_3\left(1\right)=1$, $T_3\left(2\right)=2$, $T_3\left(3\right)=3$, $T_3\left(4\right)=7$, $T_3\left(5\right)=9$, $T_3\left(6\right)=14$.
\end{proposition}
\begin{proof}
By complete search over the finite state space.
\end{proof}
\begin{lemma}\label{lemma fastest person always returns}
There exists an optimal schedule in which every return is made by a single person, and that person is the fastest person then present on the right bank.
\end{lemma}
\begin{proof}
See Sniedovich \cite{Sniedovich2002}, whose analysis exhibits properties possessed by at least one optimal policy.
\end{proof}
\begin{remark}\label{remark: fastest returner not every optimum}
Lemma \ref{lemma fastest person always returns} must not be strengthened to the assertion that in \emph{every} optimal schedule, returns are made by the fastest person on the right. For example, if $n=6$ and $c=3$, the schedule
\[\left\{1,2,3\right\}\to\textsf{R},\quad 2\to\textsf{L},\quad \left\{4,5,6\right\}\to\textsf{R},\quad 1\to\textsf{L},\quad \left\{1,2\right\}\to\textsf{R}\]
has total time $3+2+6+1+2=14=T_3(6)$ and is therefore optimal, yet its first return is made by person 2 while person 1 is also on the right bank.
\end{remark}

\subsection{An upper bound}
\begin{proposition}\label{proposition recurrence t3}
For all $k\ge 9$, we have $T_3(k) \le T_3(k-6) + 2k + 6$.
\end{proposition}
\begin{proof}
We construct a sequence of moves from the state $S_k=\left(\left\{1,\ldots,k\right\},\textsf{L}\right)$ to the state $S_{k-6}=\left(\left\{1,\ldots,k-6\right\},\textsf{L}\right)$, namely the six moves in Figure \ref{fig:c3 block schedule}.
    \begin{figure}[H]
        \centering
        \begin{tabular}{|c|c|c|c|c|}
            \hline
            Step & Direction & People & Time & Cumulative \\
            \hline
            1 & \textsf{L} to \textsf{R} & 1, 2, 3 & 3 & 3 \\
            \hline
            2 & \textsf{R} to \textsf{L} & 1 & 1 & 4 \\
            \hline
            3 & \textsf{L} to \textsf{R} & $k-2$, $k-1$, $k$ & $k$ & $k+4$ \\
            \hline
            4 & \textsf{R} to \textsf{L} & 2 & 2 & $k+6$ \\
            \hline
            5 & \textsf{L} to \textsf{R} & $k-5$, $k-4$, $k-3$ & $k-3$ & $2k+3$ \\
            \hline
            6 & \textsf{R} to \textsf{L} & 3 & 3 & $2k+6$ \\
            \hline
        \end{tabular}
        \caption{A sequence of moves from $S_k$ to $S_{k-6}$, valid for $k\ge 9$.}
        \label{fig:c3 block schedule}
    \end{figure}
Each move respects the capacity constraint, and for $k\ge 9$, each move takes people who are on the side of the torch. The hypothesis $k\ge 9$ is needed: step 5 requires $k-5,k-4,k-3$ all to be on the left bank at that moment, and after steps 1--4 the left bank is $\left\{1,2\right\}\cup\left\{4,\ldots,k-3\right\}$, so $k-5\ge 4$ is required. For $k=7$ and $k=8$ the sequence is not legal, since person 3 has already crossed and would appear again in step 5; those two values are not used below. After these moves, exactly the six people $\{k-5,k-4,k-3,k-2,k-1,k\}$ are on the right bank, while $\{1,\ldots,k-6\}$ remain on the left bank and the torch is on the left; that is, we have reached $S_{k-6}$. The total cost of these six moves is $3+1+k+2+(k-3)+3=2k+6$. Appending an optimal schedule for the remaining instance, which is the $(k-6)$-person instance with crossing times $1,\ldots,k-6$, gives a feasible schedule of total cost $(2k+6)+T_3(k-6)$, whence the stated upper bound.
\end{proof}
Only the range $k\ge 13$ is used below, so the restriction to $k\ge 9$ costs nothing. Iterating Proposition \ref{proposition recurrence t3} from the values
\begin{align}\label{eqn:base block c3}
T_3(7)=17,\quad T_3(8)=22,\quad T_3(9)=26,\quad T_3(10)=32,\quad T_3(11)=37,\quad T_3(12)=43,
\end{align}
which are obtained by exhaustive search on the finite state space, yields the following explicit bound.
\begin{theorem}\label{theorem capacity c optimal}
For all $n\ge 7$,
\begin{align}\label{eqn:closed form c3}
T_3\left(n\right)\le U(n):=\frac{n^{2}}{6}+2n-\frac{181}{36}+\frac{\left(-1\right)^{n}}{4}-\frac{2}{9}\cos\left(\frac{2n\pi}{3}\right).
\end{align}
\end{theorem}
\begin{proof}
Define $E(n)=U(n)-\frac{n^2}{6}-2n$, so $E$ is the sum of a period-2 and a period-3 term and hence is 6-periodic. Note that $U\left(n\right)$ satisfies the recurrence relation $U(n)=U(n-6)+2n+6$ for all $n$. A direct evaluation shows that $U(n)$ agrees with the six values in (\ref{eqn:base block c3}) for $n=7,\ldots,12$:
\[
\begin{array}{c|cccccc}
n&7&8&9&10&11&12\\\hline
U(n)-\frac{n^2}{6}-2n&-\frac{31}{6}&-\frac{14}{3}&-\frac{11}{2}&-\frac{14}{3}&-\frac{31}{6}&-5
\end{array}
\]
and these are the values of $T_3(n)-\frac{n^2}{6}-2n$ for $n=7,\ldots,12$. The claim now follows by induction on $n$: it holds for $7\le n\le 12$, and if it holds for $n-6$ with $n\ge 13$, then by Proposition \ref{proposition recurrence t3},
\[T_3(n)\le T_3(n-6)+2n+6\le U(n-6)+2n+6=U(n).\qedhere\]
\end{proof}

\subsection{A lower bound}\label{subsection:bags}
The difficulty in bounding $T_3(n)$ from below is that expensive crossings may be interleaved with the transport of other people, and no particular state need be visited. We now record a reformulation in which the order is discarded entirely, so that the quantity to be bounded is the minimum of an explicit weight over a set defined by two counting conditions. The idea of replacing a sequence of crossings by the bag of its forward trips is due to Backhouse \cite{Backhouse2008}, whose central theorem transforms the problem of determining an optimal sequence into that of determining an optimal \emph{bag} of forward trips.
\begin{definition}[admissible bag]\label{definition:admissible bag}
We say that a finite multiset $F$ of non-empty subsets of $\left\{1,\ldots,n\right\}$ is an admissible bag if the following hold:
\begin{enumerate}[label=(\roman*)]
\itemsep 0em
\item $\left|T\right|\le 3$ for every $T\in F$ since at most three people cross in one trip;
\item every $i\in\left\{1,\ldots,n\right\}$ belongs to at least one $T\in F$;
\item $\sum_{T\in F}\left(\left|T\right|-1\right)=n-1$.
\end{enumerate}
Its weight is
\[w(F)=\sum_{T\in F}\left(\max T+\sum_{i\in T}i\right)-\frac{n(n+1)}{2},\]
and we write $B_3(n)$ for the minimum of $w(F)$ over all admissible bags $F$.
\end{definition}

\begin{proposition}\label{proposition:bag reformulation}
Let $\sigma$ be a schedule for capacity 3 in which every return carries exactly one person, and let $F(\sigma)$ be the multiset of its forward trips. Then $F(\sigma)$ is an admissible bag and the total cost of $\sigma$ equals $w\left(F(\sigma)\right)$. Consequently, $T_3(n)\ge B_3(n)$.
\end{proposition}
\begin{proof}
For every $i\in\left\{1,\ldots,n\right\}$, let $d_i$ denote the number of forward trips of $\sigma$ containing person $i$. As person $i$ starts on the left and ends on the right, and every trip containing $i$ changes the side of $i$, then person $i$ makes $d_i-1$ returns. Since each return carries one person, then \begin{align*}
    \text{the total cost of the returns is }&\sum_{i}\left(d_i-1\right)i\quad \text{and}\\
    \text{the total cost of the forward trips is }&\sum_{T\in F\left(\sigma\right)}\max T.
\end{align*}
Let $f=\left|F\left(\sigma\right)\right|$ denote the number of forward trips of $\sigma$. Then, $\sigma$ has $f-1$ returns, so $\sum_{i}\left(d_i-1\right)=f-1$. Also, note that $\sum_{i}d_i=\sum_{T\in F\left(\sigma\right)}\left|T\right|$, which implies \[\sum_{T\in F\left(\sigma\right)}\left(\left|T\right|-1\right)=\sum_{i}d_i-f=f-1+\sum_{i}1-f=n-1,\]
which is condition (iii) of Definition \ref{definition:admissible bag}. Note that condition (i) holds trivially since this refers to the capacity constraint; condition (ii) holds too because every person crosses forward at least once. Next, we note the identity \[\sum_i d_ii=\sum_{T\in F(\sigma)}\sum_{i\in T}i,\]
so \[\operatorname{cost}(\sigma)=\sum_{T\in F(\sigma)}\max T+\sum_i\left(d_i-1\right)i=\sum_{T\in F(\sigma)}\left(\max T+\sum_{i\in T}i\right)-\frac{n(n+1)}{2}=w\left(F(\sigma)\right).\]
By Lemma \ref{lemma fastest person always returns}, there is an optimal schedule in which every return is made by a single person. Applying the identity to it gives $T_3(n)=w\left(F\right)\ge B_3(n)$ for that bag $F$.
\end{proof}
When every return carries one person, the cost of a schedule depends only on its bag of forward trips, and both the cost and the constraints of Definition \ref{definition:admissible bag} are sums over the trips. This suggests bounding each trip separately and adding. We look for a price $y_i\ge 0$ for each person and a price $\lambda$ for each unit of progress $|T|-1$, such that no trip is worth more than it costs. That is,
\begin{align}\label{eqn:trip inequality}
\sum_{i\in T}y_i+\lambda\left(|T|-1\right)\le\max T+\sum_{i\in T}i.
\end{align}
Summing over the trips of an admissible bag and using conditions (ii) and (iii) of Definition \ref{definition:admissible bag}  yields \begin{align}\label{eqn:dual bound}
w(F)\ge\sum_i y_i+\lambda(n-1)-\frac{n(n+1)}{2}.
\end{align}
In the language of linear programming, the prices are said to form a \emph{feasible dual solution}. To make the bound as strong as possible, the trips used by the construction of Proposition \ref{proposition recurrence t3} should be tight. That is to say, the trips must satisfy \eqref{eqn:trip inequality} with equality. We determine the prices in three steps.

First, for $T=\left\{1,2,3\right\}$, the right side of \eqref{eqn:trip inequality} is $3+\left(1+2+3\right)=9$ and $|T|-1=2$, so $y_1+y_2+y_3+2\lambda\le 9$. Since $y_i\ge 0$, the largest admissible value is $\lambda=\frac92$, and it forces $y_1=y_2=y_3=0$.

Second, for a consecutive triple $T=\left\{c-2,c-1,c\right\}$, the right side is $c+\left(3c-3\right)=4c-3$, so tightness with $\lambda=\frac92$ means
\[y_{c-2}+y_{c-1}+y_c=4c-3-9=4c-12.\]
Trying $y_i=\alpha i+\beta$, the left side is $3\alpha c-3\alpha+3\beta$. Comparing coefficients gives $\alpha=\frac43$ and $\beta=-\frac83$, so \[y_i=\frac43\left(i-2\right).\]
Third, this formula is too large for some small $i$, because trips containing person 1 are cheap. For $T=\left\{1,2,c\right\}$ with $c\ge 3$, the right side is $c+\left(3+c\right)=2c+3$, so $y_1=y_2=0$ gives
\[y_c\le 2c+3-9=2c-6.\]
At $c=4$ this requires $y_4\le 2$, whereas $\frac43\left(4-2\right)=\frac83$, so we take $y_4=2$. At $c=5$ it requires $y_5\le 4$, which the formula meets with equality, so $y_5=4$. For $T=\left\{1,5,6\right\}$, the right side is $6+12=18$, so
\[y_5+y_6\le 18-9=9,\]
and with $y_5=4$ this requires $y_6\le 5$, whereas $\frac43\left(6-2\right)=\frac{16}{3}$, so we take $y_6=5$. For $i\ge 7$, the linear formula satisfies every constraint, as Lemma \ref{lemma:local inequality} shows.
\begin{lemma}[local inequality]\label{lemma:local inequality}
For $i\ge 1$, define the sequence $\left(y_i\right)$ as follows: $y_1=y_2=y_3=0$, $y_4=2$, $y_5=4$, $y_6=5$, and for $i\ge 7$, $y_i=\frac{1}{3}\left(4i-8\right)$. Then, for every non-empty $T\subseteq\left\{1,2,3,\ldots\right\}$ with $\left|T\right|\le 3$,
\[\sum_{i\in T}y_i+\frac{9}{2}\left(\left|T\right|-1\right)\le \max T+\sum_{i\in T}i.\]
\end{lemma}
\begin{proof}Clearly $y_i\ge 0$ for all $i$. Moreover, we use the bounds
\begin{alignat}{2}
y_i&\le \tfrac43\left(i-2\right) &\quad&\text{for } i\ge 2,\label{eqn:y lin}\\
y_i&\le 2i-6 &&\text{for } i\ge 3,\label{eqn:y A}\\
y_i&\le 2i-7 &&\text{for } i\ge 6.\label{eqn:y B}
\end{alignat}
For $i\le 6$, these are checked directly. For $i\ge 7$, \eqref{eqn:y lin} holds with equality, and \eqref{eqn:y A} and \eqref{eqn:y B} reduce to $i\ge 5$ and $i\ge\frac{13}{2}$.

Write $T=\left\{a\right\}$, $\left\{a,b\right\}$ or $\left\{a,b,c\right\}$ with $a<b<c$. The claim is then
\[y_a\le 2a,\qquad y_a+y_b\le a+2b-\tfrac92,\qquad y_a+y_b+y_c\le a+b+2c-9.\]
If $a\ge 2$, then by \eqref{eqn:y lin}, it suffices to show that $4\left(a-2\right)\le 6a$, $2a\le 4b+5$, and $a+b\le 2c-3$. All three hold because $a<b<c$ are integers.

If $a=1$, then $y_1=0$ and the claim becomes
\[0\le 2,\qquad y_b\le 2b-\tfrac72,\qquad y_b+y_c\le b+2c-8.\]
The second inequality holds for $b=2$ since $0\le\frac12$, and for $b\ge 3$ by \eqref{eqn:y A}. For the third, there are three cases.
\begin{itemize}
\itemsep 0em
\item If $b\le 4$, combine $y_b\le b-2$ with \eqref{eqn:y A} for $c$.
\item If $b=5$, combine $y_5=b-1$ with \eqref{eqn:y B} for $c\ge 6$.
\item If $b\ge 6$, then \eqref{eqn:y lin} reduces the claim to $b+8\le 2c$, which follows from $c\ge b+1$.\qedhere
\end{itemize}
\end{proof}
 
\begin{lemma}[return inequality]\label{lemma:return inequality}
Let the sequence $\left(y_i\right)$ be as defined in Lemma \ref{lemma:local inequality}. Then, for every non-empty $R\subseteq\left\{1,2,3,\ldots\right\}$ with $\left|R\right|\le 3$,
\[g(R):=\frac{9}{2}\left(\left|R\right|-1\right)+\max R+\sum_{i\in R}\left(y_i-i\right) \ge 0.\]
\end{lemma}
\begin{proof}
We use the fact that
\begin{align}\label{eqn:y minus i}
y_i-i\ge -3\quad\text{for every }i\ge 1.
\end{align}
If $R=\left\{a\right\}$, then $g(R)=a+\left(y_a-a\right)=y_a\ge 0$. If $R=\left\{a,b\right\}$ with $a<b$, then
\[g(R)=\frac92+b+\left(y_a-a\right)+\left(y_b-b\right)=\frac92+\left(y_a-a\right)+y_b\ge  \frac92-3+0=\frac32.\]
If $R=\left\{a,b,c\right\}$ with $a<b<c$, then
\[g(R)=9+c+\left(y_a-a\right)+\left(y_b-b\right)+\left(y_c-c\right)=9+\left(y_a-a\right)+\left(y_b-b\right)+y_c\ge  9-3-3+0=3.\]
In each case, we used the facts that $y_i\ge 0$ and (\ref{eqn:y minus i}).
\end{proof}
 
We can now bound the cost of an arbitrary schedule, with no assumption whatever about the form of its returns.
\begin{proposition}\label{proposition:schedule bound}
Let $n\ge 7$ and let $\sigma$ be any schedule for $\left\{1,\ldots,n\right\}$ with capacity $c=3$. Then,
\[\operatorname{cost}(\sigma)\ge  V(n):=\frac{n^2}{6}+2n-\frac{11}{2}.\]
\end{proposition}
\begin{proof}
Let $\sigma$ have forward trips $T_1,\ldots,T_f$ and returns $R_1,\ldots,R_{f-1}$, and for each person $i$, let $d_i$ and $b_i$ be the numbers of forward trips and of returns containing $i$. Each trip containing $i$ changes the side of $i$, and $i$ starts on the left and ends on the right, so
\begin{align}\label{eqn:d=b+1}
d_i=b_i+1\quad\text{for every }i.
\end{align}
Since \[\sum_i d_i=\sum_{u}\left|T_u\right|\quad\text{and}\quad \sum_{i}b_i=\sum_{j}\left|R_j\right|,\] 
then (\ref{eqn:d=b+1}) gives \[\sum_u\left|T_u\right|=n+\sum_j\left|R_j\right|.\] 
Next, using the fact that \[\sum_j\left|R_j\right|=\sum_j\left(\left|R_j\right|-1\right)+(f-1),\]
we have 
\begin{align}\label{eqn:trip count general}
\sum_{u}\left(\left|T_u\right|-1\right)=n-1+\sum_{j}\left(\left|R_j\right|-1\right).
\end{align}
Applying Lemma \ref{lemma:local inequality} to each forward trip, \[\max T_u+\sum_{i\in T_u}i\ge \sum_{i\in T_u}y_i+\frac{9}{2}\left(\left|T_u\right|-1\right).\]
Summing over all $u$ yields \begin{align*}
    \sum_{u}\left(\max T_u+\sum_{i\in T_u}i\right)\ge \sum_{u}\sum_{i\in T_u}y_i+\frac{9}{2}\sum_{u}\left(\left|T_u\right|-1\right).
\end{align*}
Hence, \[\sum_{u}\max T_u+\sum_{i}d_i i\ge \sum_{i}d_iy_i+\frac{9}{2}\sum_{u}\left(\left|T_u\right|-1\right) .\]
By (\ref{eqn:d=b+1}), we have \[\sum_i d_ii=\frac{n(n+1)}{2}+\sum_i b_ii\quad\text{and}\quad\sum_i d_iy_i=\sum_i y_i+\sum_i b_iy_i, \] so
\[\sum_{u}\max T_u\ge \left(\sum_{i}y_i+\frac{9}{2}(n-1)-\frac{n(n+1)}{2}\right)+\frac{9}{2}\sum_{j}\left(\left|R_j\right|-1\right)+\sum_{i}b_i\left(y_i-i\right).\]
Adding $\sum_j\max R_j$ to both sides and using $\sum_i b_i\left(y_i-i\right)=\sum_j\sum_{i\in R_j}\left(y_i-i\right)$,
\[\operatorname{cost}(\sigma)=\sum_{u}\max T_u+\sum_{j}\max R_j\ge \left(\sum_{i}y_i+\frac{9}{2}(n-1)-\frac{n(n+1)}{2}\right)+\sum_{j}g\left(R_j\right),\]
with $g$ as in Lemma \ref{lemma:return inequality}. Note that $g(R_j)\ge 0$ by that lemma, so it remains to evaluate the bracket. For $n\ge 7$,
\begin{align*}
\sum_{i=1}^{n}y_i=\left(0+0+0+2+4+5\right)+\sum_{i=7}^{n}\frac{4i-8}{3}=\frac23n^2-2n-1.
\end{align*}
Hence,
\begin{align}\label{eqn:V evaluation}
\sum_{i=1}^{n}y_i+\frac92(n-1)-\frac{n(n+1)}{2}=\frac{n^2}{6}+2n-\frac{11}{2},
\end{align}
which is $V(n)$.
\end{proof}
\begin{corollary}\label{corollary:bag bound}
For every $n\ge 7$, $B_3(n)\ge V(n)$.
\end{corollary}
\begin{proof}
Lemma \ref{lemma:local inequality} states that the sequence $(y_i)$ defined there, together with $\lambda=\frac92$, satisfies \eqref{eqn:trip inequality} for every non-empty $T$ with $|T|\le 3$. Hence, \eqref{eqn:dual bound} holds with $\lambda=\frac92$, that is,
\[w(F)\ge\sum_{i=1}^{n}y_i+\frac92(n-1)-\frac{n(n+1)}{2}\]
for every admissible bag $F$. By \eqref{eqn:V evaluation}, the right side equals $V(n)$ for $n\ge 7$. Taking the minimum over all admissible bags gives $B_3(n)\ge V(n)$.
\end{proof}
The weights are not \emph{quite} sharp: $V(n)$ falls below $U(n)$, but always by less than 1. To close the gap, we invoke Lemma \ref{lemma:U integral}.
\begin{lemma}\label{lemma:U integral}
For every $n\ge 7$ we have $U(n)\in\mathbb{Z}$ and $0\le U(n)-V(n)<1$.
\end{lemma}
\begin{proof}
As noted in the proof of Theorem \ref{theorem capacity c optimal}, $U(n)=U(n-6)+2n+6$ for every $n$, and $U(7),\ldots,U(12)$ are the integers $17,22,26,32,37,43$. By induction on $n$, $U(n)\in\mathbb{Z}$ for all $n\ge 7$. Next, $U(n)-V(n)=E(n)+\frac{11}{2}$ where $E(n)=U(n)-\frac{n^2}{6}-2n$ is $6$-periodic with the six values $-\frac{31}{6},-\frac{14}{3},-\frac{11}{2},-\frac{14}{3},-\frac{31}{6},-5$ listed in the proof of Theorem \ref{theorem capacity c optimal}. Hence, $U(n)-V(n)$ takes only the values $\frac13,\frac56,0,\frac56,\frac13,\frac12$, all of which lie in $[0,1)$.
\end{proof}

\begin{theorem}\label{theorem:exact c3}
For all $n\ge 7$,
\[T_3(n)=\frac{n^{2}}{6}+2n-\frac{181}{36}+\frac{\left(-1\right)^{n}}{4}-\frac{2}{9}\cos\left(\frac{2n\pi}{3}\right).\]
\end{theorem}
\begin{proof}
By Proposition \ref{proposition:schedule bound}, every schedule costs at least $V(n)$, so $T_3(n)\ge V(n)$. Since $T_3(n)\in\mathbb{Z}$, then $T_3(n)\ge\left\lceil V(n)\right\rceil$. By Lemma \ref{lemma:U integral}, $U(n)\in\mathbb{Z}$ such that $U(n)-1<V(n)\le U(n)$, so $\left\lceil V(n)\right\rceil=U(n)$. Hence, $T_3(n)\ge U(n)$. The reverse inequality is Theorem \ref{theorem capacity c optimal}.
\end{proof}
\begin{corollary}\label{corollary:recurrence exact}
$T_3(n)=T_3(n-6)+2n+6$ for all $n\ge 13$.
\end{corollary}
\begin{proof}
Immediate from Theorem \ref{theorem:exact c3} and the identity $U(n)=U(n-6)+2n+6$.
\end{proof}
\begin{example}[$c=3$] The values of $T_3(n)$ for small $n$ are as follows; those for $n\le 6$ are from Proposition \ref{proposition initial val t3} and those for $n\ge 7$ are given by Theorem \ref{theorem:exact c3}.
\[
\begin{array}{c|cccccccccccccccccccc}
n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline
T_3\left(n\right)&1&2&3&7&9&14&17&22&26&32&37&43&49&56&62&70&77&85&93&102
\end{array}
\]
These are the terms of \seqnum{A392834}.
\end{example}

\begin{example}[$c=4$] When $c=4$, by complete search one generates the sequence
\[
\begin{array}{c|cccccccccccccccccccc}
n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\hline
T_4\left(n\right)&1&2&3&4&8&10&12&17&20&23&28&32&36&42&47&52&58&64&70&77
\end{array}
\]
\end{example}
Note that $T_c\left(n\right)$ is most interesting for small capacities $c$. Indeed, as $c$ grows relative to $n$, the constraint becomes weak: if $c\ge n$, everyone can cross in a single move, so $T_c\left(n\right)=n$. For $c\ge 4$ two questions should be distinguished. Computing the optimum for a given instance is settled by the general methods of \cite{Backhouse2008,BackhouseTruong2015}. What may remain interesting is whether a particularly short closed formula, or a recurrence of bounded order, exists for the consecutive crossing times $t_i=i$; we conjecture that it does for each small $c$, in analogy with the period-6 quadratic of Theorem \ref{theorem:exact c3}. We note that the method of Section \ref{section:capacity three} is not special to $c=3$: the bag formulation and the local inequality both make sense for any capacity, and the task for a given $c$ is to find a system of weights whose value matches the construction.

\section{A generalization to star graphs}\label{section:star graphs}
As we have seen, the bridge and torch problem usually involves a single bridge with limited capacity. The task is to decide who crosses together, who returns with the torch, and in what order, to finish as soon as possible. Now, consider a setting with more than one bridge. At a node, some travelers go in different directions. The goal is to schedule movements so that everyone reaches a destination quickly.

Here, we will discuss some applications to star graphs (Definition \ref{definition of star graph}). In such a graph, travelers start at the root and must reach the leaves.
\begin{definition}[star graph]\label{definition of star graph} Fix an integer $k\ge 1$. The star graph with $k$ edges, denoted by $\mathcal{S}(k)$, is the graph with vertex set $V=\{o\}\cup\{u_1,\ldots,u_k\}$ where $o$ is the center and $u_1,\ldots,u_k$ are the leaves. We define the edge set to be $E=\{\{o,u_i\}:i=1,\ldots,k\}$. Equivalently, $\mathcal{S}(k)$ is the unique graph on $k+1$ vertices in which $\deg(o)=k$ and $\deg(u_i)=1$ for all $i=1,\dots,k$, up to graph isomorphism.
\end{definition}
Essentially, one can think of a star graph as a hub-and-spoke system where there is a single root node and multiple child nodes connected only to the root node. We will work on star graphs up to rotation. For example, Figure \ref{fig:star graph with 7 edges} shows a star graph with root/center $o$ and edges $\left\{o,u_i\right\}$ where $i=1,\ldots,7$.
\begin{figure}[H]
    \centering
\begin{tikzpicture}[
    every node/.style={circle,draw,fill=white,minimum size=7mm,font=\sffamily},
    edge/.style={draw,thick},scale=0.6
]

% center
\node (o) at (0,0) {$o$};

% leaves
\foreach \i/\angle in {1/90,2/38,3/-14,4/-66,5/-118,6/-170,7/142} {
    \node (u\i) at (\angle:3cm) {$u_{\i}$};
    \draw[edge] (o) -- (u\i);
}

\end{tikzpicture}
    \caption{The star graph $\mathcal{S}(7)$ with 7 edges}
    \label{fig:star graph with 7 edges}
\end{figure}

We now formally define the problem for star graphs. Since several modeling choices are possible, we state our assumptions in full.
\begin{definition}[the star model]\label{definition:star model}
Let $\mathcal{S}(k)$ have center $o$ and leaves $u_1,\ldots,u_k$, let the $n$ persons have crossing times $1<2<\cdots<n$, and let $t\ge 1$ torches be given. Initially, all $n$ persons and all $t$ torches are at the center $o$. A torch-movement consists of one or two persons together with one torch, all currently at the same vertex, traversing a single edge; the persons carry the torch, and the duration of the movement is the larger crossing time among its participants. A parallel step is a collection of torch-movements executed simultaneously subject to:
\begin{itemize}
\itemsep 0em
\item \emph{disjoint people}: no person participates in more than one movement in that step;
\item \emph{disjoint star edges}: no star edge is traversed by more than one movement in that step;
\item \emph{disjoint torches}: no torch is used by more than one movement in that step.
\end{itemize}
The duration of a parallel step is the maximum duration among its movements, and steps are executed one after another, each step finishing before the next begins. The objective is to, in minimum total duration, reach a configuration in which every person is at some leaf. Any person may finish at any leaf, several persons may finish at the same leaf, and torches may be left at the center or at any leaf. We write $T(n,k,t)$ for the minimum total duration.
\end{definition}

\begin{theorem}[bridge and torch problem for star graphs]\label{theorem: bridge and torch for star graphs}
In the model of Definition \ref{definition:star model}, let $m=\min (k,t)$ and $s=\left\lceil \frac{n}{2m}\right\rceil$. Then, for $n\ge 2$,
\begin{align}\label{eqn: star graph lower and upper bounds}
sn-ms(s-1)\le T(n,k,t) \le T(n)=\frac{n^2}{4}+3n-5+\frac{(-1)^n-1}{8},
\end{align}
and the lower bound is attained whenever $t\ge\left\lceil \frac n2\right\rceil$. Moreover, writing $n=2mq+r$ with $0\le r<2m$,
\begin{align}\label{eqn:exact lower bound expression}
sn-ms(s-1)=\frac{n^2}{4m}+\frac n2+\frac{r(2m-r)}{4m}\ge \frac{n^{2}}{4m}+\frac{n}{2}.
\end{align}
\end{theorem}
Before discussing the proof, we look at some important cases. First, if $m\ge \lceil \frac{n}{2}\rceil$, then $s=1$ and $T(n,k,t)=n$. Indeed, this holds because everybody leaves the center in a single parallel step. On the other hand, if $k=1$ and $t\ge \lceil\frac{n}{2}\rceil$, then $m=1$ and $s=\lceil\frac{n}{2}\rceil$, which implies \[T(n,1,t)=\left\lfloor \frac{(n+1)^2}{4}\right\rfloor.\]
By considering the expression in (\ref{eqn:formula for T(n)}), we see that for all $n\ge 2$, \[T(n,1,t)=\left\lfloor \frac{(n+1)^2}{4}\right\rfloor\le \left\lfloor \frac{n^2+12n-20}{4}\right\rfloor=T(n).\]
This makes sense because the conventional bridge and torch problem only allows one torch, so that all the returns which the conventional problem must pay for are avoided here.

In the general setting where $t = \lceil \frac{n}{2}\rceil$, and $k \ge 2$ and $n$ vary, a query of the values in Figure \ref{fig values star tnkfloor c2} on the OEIS \cite{OEIS2026} returns sequences of partial sums of floor functions. One checks directly from Theorem \ref{theorem: bridge and torch for star graphs} that
\begin{align}\label{eqn:star floor sums}
T\left(n,k,\left\lceil \tfrac n2\right\rceil\right)=\sum_{j=0}^{n+2k-1}\left\lfloor \frac{j}{2k}\right\rfloor\quad\text{for all }n\ge 1\text{ and }k\ge 2,
\end{align}
which is what identifies the rows of Figure \ref{fig values star tnkfloor c2} with the sequences listed there. What the star model contributes is therefore a scheduling interpretation of these partial sums: $\sum_{j=0}^{n+2k-1}\left\lfloor \frac{j}{2k}\right\rfloor$ is the least total time needed to move $n$ people of speeds $1,\ldots,n$ from the center of $\mathcal{S}(k)$ to its leaves when torches are abundant.

We stress that the closed forms themselves are not new. For $k=2$, combining (\ref{eqn:star floor sums}) with Theorem \ref{theorem: bridge and torch for star graphs} gives
\[\sum_{j=0}^{n}\left\lfloor \frac{j}{4}\right\rfloor=\left\lceil \frac {n-3}{4}\right\rceil\left(n-3-2\left(\left\lceil \frac {n-3}{4}\right\rceil-1\right)\right)\quad\text{where }n\ge 3,\]
but since $\left\lceil \frac{n-3}{4}\right\rceil=\left\lfloor \frac n4\right\rfloor$ for every $n$, the right side is $\left\lfloor \frac n4\right\rfloor\left(n-1-2\left\lfloor \frac n4\right\rfloor\right)$, which is one of the formulas already recorded in \seqnum{A130519} (as is the shorter $\left\lfloor \frac{(n-1)^2}{8}\right\rfloor$). The same applies for the other values of $k$. As such, the derivation above should be read as a new route to known identities and as an interpretation of them, rather than as a source of new ones.
\begin{figure}[H]
    \centering
    \begin{tabular}{|c|c|c|}
        \hline
        $k$ & Sequence values for $n=1,\dots,20$ & Related seq. \\
        \hline
        2 & 1, 2, 3, 4, 6, 8, 10, 12, 15, 18, 21, 24, 28, 32, 36, 40, 45, 50, 55, 60
        & \seqnum{A130519} \\
        \hline
        3 & 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 33, 36, 40, 44
        & \seqnum{A174709} \\
        \hline
        4 & 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 18, 20, 22, 24, 27, 30, 33, 36
        & \seqnum{A118729} \\
        \hline
        5 & 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
        & \seqnum{A131242} \\
        \hline
        6 & 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 16, 18, 20, 22, 24, 26, 28
        & \seqnum{A221912} \\
        \hline
    \end{tabular}
    \caption{Values of $T(n,k,\lceil\frac{n}{2}\rceil)$ for varying $n=1,\dots,20$ and $k=2,\dots,6$. The related sequence in each row is the sequence of partial sums of $\lfloor j/2k\rfloor$, in accordance with (\ref{eqn:star floor sums}).}
    \label{fig values star tnkfloor c2}
\end{figure}

We now give a proof of Theorem \ref{theorem: bridge and torch for star graphs}.
\begin{proof}
Let $m=\min (k,t)$. In any parallel step, the movements leaving the center use distinct edges and distinct torches, so there are at most $\min (k,t) =m$ of them. Since each carries at most two people, at most $2m$ people depart from the center in any one step. Call a step outward if it contains at least one movement leaving the center.

For the lower bound, we do not assume anything about the chronological order in which people leave the center. List the durations of the outward steps in decreasing order as $d_1\ge d_2\ge\cdots$. Fix $j$ with $1\le j\le s$ and set
\[h_j=n-2m(j-1) \ge 1,\]
and the inequality holds because $s=\lceil \frac{n}{2m}\rceil$ gives $2m(s-1)<n$. Consider the $2m(j-1)+1$ people with labels at least $h_j$. Each of them starts at the center and finishes at a leaf, so each has at least one departure from the center. As at most $2m$ such departures occur in any one step, the departures of these people occupy at least
\[\left\lceil \frac{2m(j-1)+1}{2m}\right\rceil=j\]
distinct steps. Each of those steps contains a person with label at least $h_j$, so its duration is at least $h_j$. Therefore, at least $j$ outward steps have duration at least $h_j$, which is to say $d_j\ge h_j$. In particular, at least $s$ outward steps exist, and
\[T(n,k,t)\ge \sum_{j=1}^{s}d_j \ge  \sum_{j=1}^{s}\left(n-2m(j-1)\right)=sn-2m\sum_{j=1}^{s}(j-1)=sn-ms(s-1).\]
Next, write $n=2mq+r$ with $0\le r<2m$. If $r=0$, then $s=q$ and \[sn-ms(s-1)=mq^2+mq=\frac{n^2}{4m}+\frac n2,\] which is in agreement with \eqref{eqn:exact lower bound expression} since $r(2m-r)=0$. If $r>0$, then $s=q+1$ and
\[sn-ms(s-1)=(q+1)(2mq+r)-m(q+1)q=mq^2+qr+mq+r,\]
while
\[\frac{n^2}{4m}+\frac n2+\frac{r(2m-r)}{4m}=mq^2+qr+\frac{r^2}{4m}+mq+\frac r2+\frac{r}{2}-\frac{r^2}{4m}=mq^2+qr+mq+r,\]
as required. Since $0\le r<2m$, we have $r(2m-r)\ge 0$, which yields \eqref{eqn:exact lower bound expression}.

As for the upper bound, since every person is permitted to finish at the same leaf, we may simply fix one leaf $u_1$, one torch, and ignore all other edges and torches. What remains is exactly the capacity-two bridge and torch problem of Section \ref{section:capacity two} along the edge $\{o,u_1\}$, so any optimal schedule for that problem is feasible here and $T(n,k,t)\le T(n)$ for $n\ge 2$, with $T(n)$ as in (\ref{theorem: optimal crossing time}).

Lastly, we shall prove that equality holds when $t\ge \lceil \frac n2\rceil$. Assume $t\ge \lceil \frac n2\rceil$ and let $s=\lceil \frac{n}{2m}\rceil$ as above. Partition $\{1,\ldots,n\}$ into $s$ consecutive blocks in decreasing order of labels, namely
\[B_j=\left\{n-2mj+1,\ldots,n-2m(j-1)\right\}\cap\{1,\ldots,n\}\quad \text{where }j=1,\ldots,s,\]
each of size at most $2m$. In step $j$, split $B_j$ into pairs together with at most one singleton, and send these groups outward along distinct edges, each group carrying a torch not used before. This is a legal move because $|B_j|\le 2m$ gives at most $m$ movements in the step, and $m\le k$ edges are available, and the total number of torches used over the whole schedule is $\sum_{j=1}^{s}\lceil |B_j|/2\rceil=\lceil \frac n2\rceil\le t$, so a torch is always available and no torch ever has to be returned to the center. The largest label in $B_j$ is $n-2m(j-1)$, so the duration of step $j$ is $n-2m(j-1)$ and the total duration is
\[\sum_{j=1}^{s}\left(n-2m(j-1)\right)=sn-ms(s-1).\]
Together with the lower bound, this gives equality, so $T(n,k,t)=sn-ms(s-1)$.
\end{proof}

\section{Acknowledgments}
The second author thanks Chuanjie Duanmu from River Valley High School for providing assistance with programming in SageMath \cite{sagemath}.  We would also like to thank Beno\^{i}t Corsini from the National University of Singapore for providing invaluable guidance. We are grateful to the anonymous referee, whose report corrected several errors in the original paper.

\begin{thebibliography}{9}

\bibitem{Backhouse2008}
R. Backhouse, The capacity-$C$ torch problem, in {\it Mathematics of Program Construction}, Lecture Notes in Comput. Sci., Vol. 5133, Springer, 2008, pp. 57--78.

\bibitem{BackhouseTruong2015}
R. Backhouse and T. M. Truong, The capacity-$C$ torch problem, {\it Sci. Comput. Program.} {\bf 102} (2015), 76--107.

\bibitem{JianuJianuPopescu2020}
M. Jianu, M. Jianu, and S. A. Popescu, A combinatorial solution for bridge and torch problem, {\it SN Oper. Res. Forum} {\bf 1} (2020), Article 21.

\bibitem{LevmoreCook1981}
S. X. Levmore and E. E. Cook, {\it Super Strategies for Puzzles and Games}, Doubleday, 1981.

\bibitem{OEIS2026}
OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2026. Available at \url{https://oeis.org}.

\bibitem{Rote2002}
G. Rote, Crossing the bridge at night, {\it Bull. Eur. Assoc. Theor. Comput. Sci.} {\bf 78} (2002), 241--246.

\bibitem{sagemath}
The Sage Developers, {\it SageMath, the Sage Mathematics Software System (Version 10.6)}, 2025. Available at \url{https://www.sagemath.org}.

\bibitem{Sniedovich2002}
M.~Sniedovich, The bridge and torch problem, 2002. Available at
  \url{https://www.moshe-online.com/tutor/bridge/}.

\end{thebibliography}
\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}: Primary 90B35; Secondary 90C27, 11B83.

\noindent \emph{Keywords:} bridge and torch problem, scheduling, combinatorial optimization, linear programming duality, star graph.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A078476},
\seqnum{A118729},
\seqnum{A130519},
\seqnum{A131242},
\seqnum{A174709},
\seqnum{A221912},
\seqnum{A318271}, and
\seqnum{A392834}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 23 2026;
revised version received  October 5 2026.
Published in {\it Journal of Integer Sequences}, October 9 2026.

\bigskip
\hrule
\bigskip

\noindent
Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}.
\vskip .1in


\end{document}