Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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)
alpha=delta=.5
nonstop=1
while (nonstop){
ta=(alpha/v)+((1-alpha)/m)
tb=(alpha/m)+((1-alpha)/v)
alpha=alpha+delta*(ta-tb)
if (abs(alpha-.5)>.5) alpha=runif(1)
delta=delta*.99
nonstop=(abs(ta-tb)>.01*ta)
print(alpha)
}


Filed under: R, Running Tagged: bike, gradient algorithm, mathematical puzzle        