I saw this brain teaser.

Suppose, we travel 1000 miles on a tricycle and we have 5 tyres, then how many times do we need to stop to change tyres so that each of the tyres travelled the same distance?

Here is a solution: After 400 miles change the back two tyres (could be any two) * After 600 miles change the front tyre for one of the ones that has 400 miles * After 800 miles change the front tyre again for the remaining tyre that has 400 miles.

So the answer is 3 stops, 4 changes.

However, suppose, if we have $M$ for an $N$-cycle, then what is the minimum number of changes and number of stops? It is not clear to me that there is a straightforward formula for stops. I imagine there is one for number of changes.

  • $\begingroup$ It is difficult to extrapolate from one data point. Try the problem again by hand with several options for $M,N$ and see if you can get a pattern. Only then you can try to prove it. $\endgroup$ – vadim123 Oct 7 '15 at 17:45
  • $\begingroup$ To be honest, I do not even know how to prove the above solution is optimal. I cannot find any better solution does not constitute a proof! $\endgroup$ – Lost1 Oct 7 '15 at 17:46
  • 1
    $\begingroup$ Before proving anything, try to collect some data. $\endgroup$ – vadim123 Oct 7 '15 at 17:47
  • $\begingroup$ I believe the minimum number of changes is $M-\gcd(M,N)$, which you can prove using something like the Euclidean algorithm. $\endgroup$ – joriki Oct 7 '15 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.