Find a set of positive integers with the greatest possible number of elements such that the least common multiple of all of them is less than $2011$.
Problem
Source: 2011 Cuba MO 2.7
Tags: number theory, LCM, least common multiple
17.09.2024 21:49
Lcm(1,2,...,10) is 2520. So set must be a subset of this. Now maximum power of 3 is 2 which is the element 9. But if we ignore 10 that is not much efficient because greatest power of 5 is 1 and greatest power of 2 is 3 but 10=5×2. So after ignoring 10 the lcm is still 2520. So we have to omit 9 also. Thus lcm of the set becomes less than 2011. So the set is {1,2,...,8}
17.09.2024 22:03
We can see that in every set which satisfies this condition every number has to be smallest than $2011$, so from that it follows that every number in such set has at most $4$ distinct prime divisors. From that we'll have that there are at most $4$ distinct primes, which divides at least one element in our set, but now we have that to maximize number of elements in our set, we have to minimize prime divisors of numbers in this set, so our possible prime divisors of numbers in our sets are $2, 3, 5, 7$. Now we can consider $4$ cases. Case 1: There is only one prime divisor of numbers in set. Then we have that the maximum number of elements in this set is $11$, because $2^10 < 2011$, so our set would be ${1, 2, 4, ... , 1024}$ Case 2: There are $2$ prime divisors of numbers in set. To minimize this primes we have to take primes $2, 3$, so every number in our set can be represented as $2^{a}3^{b}$. If LCM of numbers in our set is equal to $2^{a}3^b$ then we can take at most $(a+1)(b+1)$ elements in our set, so maximum number of elements in this situation is $28$. To check it you can try every case, because there are only few at which you have to look at. Case 3: There are $3$ prime divisors of numbers in set. It can be done similarly to second case and from this we get that in this situation there are at most $36$ elements in this set. Case 4: There are $4$ prime divisors of numbers in set. Similarly as before we get that in this case there are at most $40$ numbers in such set. From this we see that answer is at most $40$ and actually this is an answer, because we can take a set, which contains every divisor of $1680$.