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 will be closed after number is added. Determine the maximum number of elements in a closed set given that the initial set contains numbers.
Solution
The largest closed set has numbers. To get this number, start with ten primes , . The closed set consists of all products over all subsets of the set , hence there are elements in the closed set.
One cannot obtain more than 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 . 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.