Maths Olympiad Prep

Library / /12 of 15

Number theory Difficulty 6.0 National Olympiad Prove it Romania

A finite set of distinct positive integers is written on a blackboard. A move consists in choosing two numbers and write their lowest common multiple, given that is not already written. The set is called closed if no moves are allowed – e.g., the set {2,3,4,6}\{2, 3, 4, 6\} will be closed after number 1212 is added. Determine the maximum number of elements in a closed set given that the initial set contains 1010 numbers.

Solution

The largest closed set has 21012^{10} - 1 numbers. To get this number, start with ten primes pip_i, i=1,2,,10i = 1, 2, \dots, 10. The closed set consists of all products iXpi\prod_{i \in X} p_i over all subsets XX of the set {1,2,,10}\{1, 2, \dots, 10\}, hence there are 21012^{10} - 1 elements in the closed set.

One cannot obtain more than 21012^{10} - 1 numbers. Indeed, each move gives the l.c.m. of two or more numbers from the initial set, so each added number corresponds to a nonempty set of the set {1,2,,10}\{1, 2, \dots, 10\}. The conclusion follows.

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.