1981 IMO Problems/Problem 4

Problem

(a) For which values of $n>2$ is there a set of $n$ consecutive positive integers such that the largest number in the set is a divisor of the least common multiple of the remaining $n-1$ numbers?

(b) For which values of $n>2$ is there exactly one set having the stated property?

Solution

Let $k = \prod p_i^{e_i}$ be the greatest element of the set, written in its prime factorization. Then $k$ divides the least common multiple of the other elements of the set if and only if the set has cardinality at least $\max \{ p_i^{e_i} \}$ , since for any of the $p_i^{e_i}$ , we must go down at least to $k-p_i^{e_i}$ to obtain another multiple of $p_i^{e_i}$ . In particular, there is no set of cardinality 3 satisfying our conditions, because each number greater than or equal to 3 must be divisible by a number that is greater than two and is a power of a prime.

For $n > 3$ , we may let $k = \mbox{lcm} (n-1, n-2) = (n-1)(n-2)$ , since all the $p_i^{e_i}$ must clearly be less than $n$ and this product must also be greater than $n$ if $n$ is at least 4. For $n > 4$ , we may also let $k = \mbox{lcm} (n-2, n-3) = (n-2)(n-3)$ , for the same reasons. However, for $n = 4$ , this does not work, and indeed no set works other than $\{ 3,4,5,6 \}$ . To prove this, we simply note that for any integer not equal to 6 and greater than 4 must have some power-of-a-prime factor greater than 3.

Q.E.D.

Alternate Solution

Let, for some $n$ and $m$ with $m>n$ , $m\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)\ |\ (m-1)(m-2)\cdots(m-n+1)$ .

We can trivially check that, there is no such $m$ for $n=3$ , only $m=3$ works for $n=4$ and $m=3,8$ works for $n=5$ .

Now, consider, $n>5$ . By Bertrand's postulate there is a prime $p$ such that $2 \le \left\lfloor\frac{n}{2}\right\rfloor < p < 2\left\lfloor\frac{n}{2}\right\rfloor$ .

Which implies, $p< n \le 2p$ .

As, $n-1 \ge p,3,2$ , there must be a multiple of $p$ , a multiple of $3$ and a multiple of $2$ in the set, $\{m-1,m-2,\cdots,m-n+1\}$ .

So, $2p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)$ and $3p\ |\ \mbox{lcm}(m-1,m-2,\cdots,m-n+1)$ .

So, $m=2p$ and $m=3p$ both work for $n>5$ .

So,

There exists solution for all $n>3$ ,

Only one Solution for $n=4$ .

Q.E.D.

1981 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions

Page

Toolbox

Search

1981 IMO Problems/Problem 4

Problem

Solution

Alternate Solution