Competition problem — Number theory

Library / /92 of 220

Number theory Difficulty 5.7 AIME, harder Prove it Ukraine

Let $a_1 < a_2 < \dots < a_k$ be positive integers. For each $a_i$ Zarina has written down all the positive divisors of $a_i$ in the notebook (some numbers might be written several times). Then, Marina split all the numbers in the notebook into several groups. It turned out that the numbers in each of these groups form a set of all the positive divisors of some positive integer, which Marina has decided to also write down on the desk. Prove that the numbers on the desk are $a_1, a_2, \dots, a_k$ in some order.

Solution

Notice that number $a_k$ is written only once in the notebook. Then there exists some Marina's group that contains all divisors of $a_k$ . Therefore $a_k$ is also on the desk. Then we cross out from the notebook all divisors of $a_k$ one time. Now, by similar thoughts it follows that $a_{k-1}$ is also on the desk, we can cross out it and all of its divisors and so on. Therefore, all the numbers $a_1, a_2, \dots, a_k$ are present on the desk.

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.