2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Moving backwards is forbidden both on foot and by bicycle, right? Otherwise answer always seems to be "Yes.". $\endgroup$
    – Kaban-5
    Commented Jul 18, 2018 at 9:18

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ Note that the linear equations effectively reduce us down to one variable so this is really just checking the consistency of a set of inequalities in one variable. $\endgroup$
    – Will Sawin
    Commented Jul 18, 2018 at 10:20
  • 2
    $\begingroup$ Your statement about being able to set the $l_i$ however you like does assume that all biking speeds are faster than all walking speeds. If the second person walks faster than the first person bikes, the situation could be more complicated. $\endgroup$
    – Dan Turetsky
    Commented Jul 18, 2018 at 22:20
  • 1
    $\begingroup$ Dan Turetsky: Nice catch! However if $w_i > b_j$, then $b_i \geqslant w_i > b_j \geqslant w_j$ and the $i$-th person always moves faster than the $j$-th person, therefore they can't reach the end in the same time. $\endgroup$
    – Kaban-5
    Commented Jul 19, 2018 at 13:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .