We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they ride in turns. Each time a rider dismounts he leaves the bike by the side of the road, and walks on, while one of the other ones eventually arrives at the bike and jumps on it (if a group member sees the bike by the road, she can use the bike, but doesn't have to).


Group member $i$ has constant walking speed $w\_i\in\mathbb{Q}$ and constant bicycling speed $b\_i\in\mathbb{Q}$ such that $b\_i \geq w\_i$.


Is there an algorithm that takes $n$, $d$, $(w\_i)\_{i\in\{1,\ldots,n\}}$ and $(b\_i)\_{i\in\{1,\ldots,n\}}$ and decides whether it is possible that the $n$ people reach the destination at the same time?



Is this cycling problem computable?
I assume that moving backwards or stopping is forbidden, otherwise the answer is "Yes." for trivial reasons.


Clearly, the time it takes the $i$-th person to reach the end of the track depends only on the 
distance $l\_i$ that $i$-th person has spent riding the bike. Moreover, this time is 
$t\_i := \dfrac{l\_i}{b\_i} + \dfrac{d - l\_i}{w\_i}$. Now, total distance travelled on the bike
does not exceed $d$ (because the bike always moves forward), therefore 
$l\_1 + l\_2 + \ldots + l\_n \leqslant d$. 


On the other hand, it is possible to make $l\_i$ arbitrary as long as $0 \leqslant l\_i \mbox { for } i = 1, 2, \ldots, n$ and
$l\_1 + l\_2 + \ldots + l\_n \leqslant d$ — first person spends first $l\_i$ kilometers
on the bike then drops it and walks for the rest of journey; second person walks for the first $l\_1$ kilometers, 
spends second $l\_2$ kilometers on the bike, then drops it; et cetera.


So there is a solution to the problem if and only if the following system of linear equations and inequalities over $l\_1, l\_2, \ldots, l\_n$ is satisfiable:
\begin{cases}
\dfrac{l\_i}{b\_i} + \dfrac{d - l\_i}{w\_i} = \dfrac{l\_1}{b\_1} + \dfrac{d - l\_1}{w\_1} \mbox{ for } i = 1, 2, \ldots, n \\
0 \leqslant l\_i \mbox{ for } i = 1, 2, \ldots, n \\ l\_1 + l\_2 + \ldots + l\_n \leqslant d
\end{cases}
This is linear programming problem, therefore it is computable
(even in P, actually). 


