Library / Romanian Mathematical Olympiad - District Round /23 of 34

Romanian Mathematical Olympiad - District Round

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\}$ will be closed after number $12$ is added. Determine the maximum number of elements in a closed set given that the initial set contains $10$ numbers.

Solution

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

One cannot obtain more than $2^{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, \dots, 10\}$ . The conclusion follows.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.