MathDB
2016 Guts #26

Source:

August 14, 2022
2016Guts Round

Problem Statement

The Euclidean Algorithm on inputs aa and bb is a way to find the greatest common divisor gcd⁡(a,b)\gcd(a,b). Suppose WLOG that a>ba>b. On each step of the Euclidan Algorithm, we solve the equation a=bq+ra=bq+r for integers q,rq,r such that 0≤r<b0\leq r<b, and repeat on bb and rr. Thus gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b)=\gcd(b,r), and we repeat. If r=0r=0, we are done. For example, gcd⁡(100,15)=gcd⁡(15,10)=gcd⁡(10,5)=5\gcd(100,15)=\gcd(15,10)=\gcd(10,5)=5, because 100=15⋅6+10100=15\cdot6+10, 15=10⋅1+515=10\cdot1+5, and 10=5⋅2+010=5\cdot2+0. Thus, the Euclidean Algorithm here takes 33 steps. What is the largest number of steps that the Euclidean Algorithm can take on some integer inputs a,ba,b where 0<a,b<1020160<a,b<10^{2016}?
Let CC be the actual answer and AA be the answer you submit. If ∣A−C∣C>12\tfrac{|A-C|}{C}>\tfrac{1}{2}, then your score will be 00. Otherwise, your score will be given by max⁡{0,⌈25−2(∣A−C∣20)1/2.2⌉}\max\{0,\lceil25-2(\tfrac{|A-C|}{20})^{1/2.2}\rceil\}.
Back to ProblemsView on AoPS