One bicycle for two

Robin showed me a mathematical puzzle today that reminded me of a story my grand-father used to tell. When he was young, he and his cousin were working in the same place and on Sundays they used to visit my great-grand-mother in another village. However, they only had one bicycle between them, so they would share the bicyle by alternating walking and cycling episodes, every 200 meters or so! Robin’s problem is to find the optimal portions of the distance spent by each of both cousins on the bicycle if one knows their respective walking and cycling speeds.

If d is the distance to my great-grand-mother’s village, ma and va are the walking and cycling speeds of André, my grand-father, and mb and vb the walking and cycling speeds of Bernard, his cousin, and if α is the portion of the distance spent by André on the bicycle, his overall travel takes is αd/va+(1-α)d/ma, while Bernard’s overall traveling time is αd/mb+(1-α)d/vb. The optimal proportion α of the distance is then such that both durations equate, namely

\alpha = \dfrac{m_b^{-1}-v_a^{-1}}{m_a^{-1}-v_a^{-1}+m_b^{-1}-v_b^{-1}}

which gives 1/2 when both cousins have the same speeds. (I first tried using the speeds rather than the times, but this involves an additional parameter, namely the portion of the time γ no-one is riding the bicycle…)

A more challenging problem is to sequentially optimise the proportion α without knowing of the speeds ma, va, mb and vb of both cousins. However, since the above solution does not depend on the overall distance, we can think of a gradient algorithm that would produce fractions αi at each kilometer i, fractions updated by something like

\alpha_{i+1} = \alpha_i + \delta_i \{T_A(\alpha_i)-T_B(\alpha_i)\}

where the sequence of δi‘s slowly decreases to zero and where TA and TB are the times taken by André and Bernard to complete the current kilometer. (Granted, this assumes some unrealistic equipment for the 1920′s!) Here is an R code that replicates this scheme

#true but unknown values
v=c(30,20)
m=c(4,8)
#gradient optimisation
alpha=delta=.5
nonstop=1
while (nonstop){
  ta=(alpha/v[1])+((1-alpha)/m[1])
  tb=(alpha/m[2])+((1-alpha)/v[2])
  alpha=alpha+delta*(ta-tb)
  if (abs(alpha-.5)>.5) alpha=runif(1)
  delta=delta*.99
  nonstop=(abs(ta-tb)>.01*ta)
  print(alpha)
  }

2 Responses to “One bicycle for two”

  1. [...] One bicycle for two [...]

  2. In adventure racing, the so called Run and Bike race is based on that, with additional orienteering issues..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 551 other followers