Competition problem — Number theory

Library / /15 of 27

Number theory Difficulty 6.0 AIME, harder Prove it Brazil

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. Can Jade make a list of questions that guarantees that she can find the product of the 2011 numbers?

Solution

She can obtain the product of any two numbers $a$ and $b$ by asking $\gcd(a, b)$ and $\text{lcm}(a, b)$ , since $\text{lcm}(a, b) \cdot \gcd(a, b) = ab$ . The identity
$abc = \frac{\text{lcm}(a, b) \cdot \text{lcm}(a, c) \cdot \text{lcm}(b, c) \cdot \gcd(a, b, c)}{\text{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} \mid a_i$ then $p^{\min\{x_i\}} \mid \gcd(a_1, a_2, \dots, a_n)$ and $p^{\max\{x_i\}} \mid \text{lcm}(a_1, a_2, \dots, a_n)$ .

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 and solution reproduced as published; topic and difficulty added by this site.