Maths Olympiad Prep

Library / /253 of 520

Number theory Difficulty 6.9 National olympiad Find the answer

For each positive integer n n,define f(n)\equallcm(1,2,...,n) f(n)\equal{}lcm(1,2,...,n).
(a)Prove that for every k k there exist k k consecutive positive integers on which f f is constant.
(b)Find the maximum possible cardinality of a set of consecutive positive integers on which f f is strictly increasing and find all sets for which this maximum is attained.

A number or a short expression. Spacing and $ signs are ignored.

Solution

### Part (a)
1. **Define the function f(n) f(n) :**
f(n)=lcm(1,2,,n) f(n) = \text{lcm}(1, 2, \ldots, n)
where lcm\text{lcm} denotes the least common multiple.

2. Observation:
For any integer n n , f(n) f(n) is the least common multiple of the first n n positive integers. If we consider f(n) f(n) and f(n+1) f(n+1) , we note that f(n+1) f(n+1) is the least common multiple of the first n+1 n+1 integers.

3. Key Insight:
If n+1 n+1 is not a prime number or a power of a prime, then f(n+1)=f(n) f(n+1) = f(n) . This is because the least common multiple of the first n n integers already includes all the prime factors of n+1 n+1 .

4. **Constructing k k consecutive integers:**
To find k k consecutive integers where f f is constant, we need k k consecutive integers none of which are primes or powers of primes. For example, consider the sequence starting from n=2 n = 2 :
4,6,8,9,10,12,14,15,16,18,20, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, \ldots
These numbers are not primes or powers of primes. We can always find such sequences of any length k k .

5. Conclusion:
For any k k , there exist k k consecutive positive integers on which f f is constant.

### Part (b)
1. Observation:
f(n+1)>f(n) f(n+1) > f(n) if and only if n+1 n+1 introduces a new prime factor or a higher power of an existing prime factor that was not already included in f(n) f(n) .

2. Strictly Increasing Sequence:
For f(n) f(n) to be strictly increasing over a set of consecutive integers, each integer in the set must introduce a new prime factor or a higher power of an existing prime factor. This happens when each integer in the set is a prime or a power of a prime.

3. Maximum Cardinality:
The maximum possible cardinality of such a set is 2. This is because if we have three consecutive integers, at least one of them will not be a prime or a power of a prime (since primes and their powers are not consecutive except for the trivial case of 2 and 3).

4. Example Sets:
The sets {2,3}\{2, 3\} and {3,4}\{3, 4\} are examples where f f is strictly increasing:
f(2)=lcm(1,2)=2 f(2) = \text{lcm}(1, 2) = 2
f(3)=lcm(1,2,3)=6 f(3) = \text{lcm}(1, 2, 3) = 6
f(4)=lcm(1,2,3,4)=12 f(4) = \text{lcm}(1, 2, 3, 4) = 12

The final answer is 2 \boxed{2} for the maximum possible cardinality of a set of consecutive positive integers on which f f is strictly increasing.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.