Maths Olympiad Prep

Library / /13 of 15

Number theory Difficulty 5.6 AIME, harder Prove it United States

Problem:

Aerith timed how long it took herself to solve a BMC monthly contest. She writes down the elapsed time as days:hours:minutes:seconds, and also simply as seconds. For example, if she spent 1,000,0001,000,000 seconds, she would write down 11:13:46:4011:13:46:40 and 1,000,0001,000,000.

Bob sees her numbers and subtracts them, ignoring punctuation; in this case he would get

11134640−1000000=10134640. 11134640-1000000=10134640.

What is the largest number that always must divide his result?

Solution

Solution:

Say that Aerith took dd days, hh hours, mm minutes, and ss seconds. Bob would then get

Δ=(1003d+1002h+100m+s)−(24⋅60⋅60d+60⋅60h+60m+s)=(1003−24⋅60⋅60)d+(1002−60⋅60)h+(100−60)m+(1−1)s=(26⋅56−27⋅33⋅52)d+(24⋅54−24⋅32⋅52)h+40m=(23⋅5)[(23⋅55−24⋅335)d+(2⋅53−2⋅32⋅5)h+m], \begin{aligned} \Delta & =\left(100^{3} d+100^{2} h+100 m+s\right)-(24 \cdot 60 \cdot 60 d+60 \cdot 60 h+60 m+s) \\ & =\left(100^{3}-24 \cdot 60 \cdot 60\right) d+\left(100^{2}-60 \cdot 60\right) h+(100-60) m+(1-1) s \\ & =\left(2^{6} \cdot 5^{6}-2^{7} \cdot 3^{3} \cdot 5^{2}\right) d+\left(2^{4} \cdot 5^{4}-2^{4} \cdot 3^{2} \cdot 5^{2}\right) h+40 m \\ & =\left(2^{3} \cdot 5\right)\left[\left(2^{3} \cdot 5^{5}-2^{4} \cdot 3^{3} 5\right) d+\left(2 \cdot 5^{3}-2 \cdot 3^{2} \cdot 5\right) h+m\right], \end{aligned}

so 23⋅5=402^{3} \cdot 5=40 must divide his number. However, no larger number works, because if Aerith spent 6060 seconds =1:00=1:00, Bob would get 100−60=40100-60=40 seconds.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.