Maths Olympiad Prep

Library / /16 of 27

Geometry Difficulty 5.8 AIME, harder Prove it Croatia

Let ABCDABCD be a quadrilateral such that AB=6|AB| = 6, BC=9|BC| = 9, CD=18|CD| = 18 and AD=5|AD| = 5 hold. Determine the length of the diagonal ACAC if it is known that it is a positive integer. (Andrea Aglić-Aljinović)

Solution

2.5. Let ana_n be the number the grasshopper is located at after the nthn^{th} jump, i.e.
a1=1,an=1+k++kn1,n2. a_1 = 1, \quad a_n = 1 + k + \dots + k^{n-1}, \quad n \ge 2.
We are looking for all numbers kk such that 2015an2015 \nmid a_n for all n=1,,2015n = 1, \dots, 2015.
Suppose that M(k,2015)=d>1M(k, 2015) = d > 1. Then every ana_n divided by dd gives the remainder 1, and since 2015 is divisible by dd we have that 2015an2015 \nmid a_n for all nn. Therefore, all positive integers which are not relatively prime to 2015 comply with the terms of the problem.
If M(k,2015)=1M(k, 2015) = 1, we observe the remainders of dividing a1,,a2015a_1, \dots, a_{2015} by 2015. If one of them is divisible by 2015, such a kk is not good. Otherwise, since there are 2014 possible remainders, at least two numbers give the same remainder. Let these numbers be ala_l and ama_m, m>lm > l. In this case, their difference is divisible by 2015. On the other hand, we have that
amal=kl++km1=kl(1++kml1)=klaml. a_m - a_l = k^l + \dots + k^{m-1} = k^l (1 + \dots + k^{m-l-1}) = k^l \cdot a_{m-l}.
From 2015klaml2015 \mid k^l \cdot a_{m-l} and M(k,2015)=1M(k, 2015) = 1, it follows that 2015aml2015 \mid a_{m-l}, which is in contradiction with the assumption that none of the numbers a1,,a2015a_1, \dots, a_{2015} is divisible by 2015. Therefore, if M(k,2015)=1M(k, 2015) = 1, the grasshopper will jump into a hole.
To conclude, the only numbers which are suitable for the terms of the problem are those which are not relatively prime to 2015.

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.