Brazilian Math Olympiad

Question

Emerald and Jade play the following game: Emerald writes a list with 2011 positive integers, but does not show it to Jade. Jade's goal is finding the product of the 2011 numbers in Emerald's list. In order to do so, she is allowed to ask Emerald the gcd or the lcm of any subset with at least two of the 2011 numbers (as, for instance, "what is the gcd of the first, second, 10th and 2000th numbers from your list?" or "what is the lcm of all the numbers in your list?"). Jade can make as many questions as she wants, but can only obtain her (correct) answers from Emerald after making all her questions (Emerald is generous and also says which answer corresponds to each question). Jade then can use any of the four elementary operations (add, subtract, multiply, divide) with Emerald's answers. Ca…

Accepted Answer

She can obtain the product of any two numbers

a

and

b

by asking

g cd (a, b)

and

lcm (a, b)

, since

lcm (a, b) \cdot g cd (a, b) = ab

. The identity

ab c = \frac{lcm ( a , b ) \cdot lcm ( a , c ) \cdot lcm ( b , c ) \cdot g cd ( a , b , c )}{lcm ( a , b , c )}

essentially finishes the proof, since the 2011 numbers can be divided into a set of three numbers and 1004 sets of two numbers.

It remains to prove the above identity. But this follows from the facts that

max (x, y) + max (x, z) + max (y, z) + min (x, y, z) - max (x, y, z) = x + y + z

, and if

p^{x_{i}} ∣ a_{i}

then

p^{m i n {x_{i}}} ∣ g cd (a_{1}, a_{2}, \dots, a_{n})

and

p^{m a x {x_{i}}} ∣ lcm (a_{1}, a_{2}, \dots, a_{n})

.