1981 IMO Problems/Problem 4

Revision as of 09:43, 28 March 2012 by Bappa1971 (talk | contribs) (Alternate Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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