# minimum number of times to change tyres.

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.

• 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. – vadim123 Oct 7 '15 at 17:45
• 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! – Lost1 Oct 7 '15 at 17:46
• Before proving anything, try to collect some data. – vadim123 Oct 7 '15 at 17:47
• I believe the minimum number of changes is $M-\gcd(M,N)$, which you can prove using something like the Euclidean algorithm. – joriki Oct 7 '15 at 18:00