One bicycle for two

March 22, 2011
By

(This article was first published on Xi'an's Og » R, and kindly contributed to R-bloggers)

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

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

To leave a comment for the author, please follow the link and comment on their blog: Xi'an's Og » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , , , ,

Comments are closed.

Sponsors

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)