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, m_a and v_a are the walking and cycling speeds of André, my grand-father, and m_b and v_b 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/v_a+(1-α)d/m_a, while Bernard’s overall traveling time is αd/m_b+(1-α)d/v_b. The optimal proportion α of the distance is then such that both durations equate, namely

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 m_a, v_a, m_b and v_b 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

where the sequence of δ_i‘s slowly decreases to zero and where T_A and T_B 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)
  }