RMO 1994 Questions, Solutions, Discussions
(RMO 1994 P3, AoPS) Find all \(6\)-digit natural numbers \(a_1 a_2 a_3 a_4 a_5 a_6\) formed by using the digits \(1, 2, 3, 4, 5, 6\), once each such that the number \(a_1a_2 \dots a_k\) is divisible by \(k\), for \(1 \leq k \leq 6\).
Click here for the spoiler!
- Show that \(a_2, a_4, a_6\) are equal to \(2, 4, 6\) in some order.
- Prove that \(a_5 = 5\), and \(a_1, a_3\) are equal to \(1, 3\) in some order.
- Using that \(3\) divides \(a_1 a_2 a_3\), determine \(a_2\).
- Using the divisibility condition by \(4\), show that \(a_4 = 6\), and conclude that \(a_6 = 4\).
Click here for the spoiler!
Since \(a_1a_2, a_1a_2a_3a_4, a_1a_2a_3a_4a_5a_6\) are divisible by \(2\), it follows that \(a_2, a_4, a_6\) are even, and hence they are equal to \(2, 4, 6\) in some order. Using that \(a_1a_2a_3a_4a_5\) is divisible by \(5\), we get that \(a_5 = 5\). So \(a_1, a_3\) are equal to \(1, 3\) in some order. Using that \(a_1a_2a_3\) is a multiple of \(3\), we obtain \[ a_1+ a_2+ a_3\equiv 0 \bmod 3, \] which yields \[ a_2 \equiv 2 \bmod 3, \] and hence, \(a_2 = 2\) holds. Note that \(1234, 3214\) are not divisible by \(4\). This shows that \(a_4 = 6\), and hence \(a_6 = 4\). It follows that \(a_1a_2a_3a_4a_5a_6\) is equal to \(321654\), or \(123654\). Note that the integers \(321654, 123654\) satisfy the required conditions too. This proves that \(321654, 123654\) are precisely all the \(6\)-digit numbers satisfying the given condition.
(RMO 1994 P5, AoPS) Let \(A\) be a set of \(16\) positive integers with the property that the product of any two distinct numbers of \(A\) will not exceed \(1994\). Show that there are two numbers \(a\) and \(b\) in \(A\) which are not relatively prime.
Observe that the above argument shows that if a set of \(16\) positive integers violates the conclusion of the problem, then it does not satisfy the given condition. Convince yourself that doing so does prove that if a set of \(16\) positive integers satisfy the given condition, then there is no way that it would fail to satisfy the conclusion.
Further, also convince yourself that establishing that the failure of the conclusion forces the failure of the given condition is equivalent to establishing that the given condition implies the stated conclusion.
When there are more than one condition, the given conditions are to be considered together, and the failure of the totality of the given conditions means the failure of at least one of the given conditions.
Click here for the spoiler!
- Suppose \(\mathcal{A}\) is a set of \(16\) positive integers, and assume that \(\mathcal{A}\) does not satisfy the conclusion of the problem, that is, it is false that some two numbers in \(\mathcal{A}\) are not relatively prime. In other words, \(\mathcal{A}\) has the property that any two numbers in \(\mathcal{A}\) are relatively prime.
- Prove that such a set \(\mathcal{A}\) would fail to satisfy the given condition, which states that the product of any two distinct elements of \(\mathcal{A}\) is smaller than \(1994\). In other words, show that the product of some two elements of \(\mathcal{A}\) is greater than or equal to \(1994\).
Click here for the spoiler!
Note that if \(n \geq 1\), and \(a_1, \dots, a_n\) are distinct and pairwise coprime positive integers such that \(a_i \geq 2\) for all \(i\), then one of them admits a prime factor which is at least as large as the \(n\)-th prime. Indeed, for each \(i\), if we fix a prime divisor \(p_i\) of \(a_i\), then using that \(a_1, \dots, a_n\) are pairwise coprime, it follows that \(p_1, \dots, p_n\) are distinct primes, and hence the largest among them is at least as large as the \(n\)-th prime. Consequently, if \(n \geq 2\), and \(a_1, \dots, a_n\) are distinct and pairwise coprime positive integers, then at least \((n - 1)\) of them are greater than \(1\), and hence one of them is divisible by a prime at least as large as the \((n-1)\)-st prime.
If possible, let us assume that the elements of \(A\) are pairwise coprime. Hence, \(A\) contains an element \(x\) which is divisible by a prime at least as large as the \(15\)th prime. Similarly, the set \(A\setminus \{x\}\) contains an element \(y\) which is divisible by a prime at least as large as the \(14\)th prime. Since the \(14\)th and \(15\)th primes are \(43, 47\) respectively, it follows that \(x\geq 47, y \geq 43\), and consequently, \[ xy \geq 47 \cdot 43 = 2021 >1994, \] which contradicts the hypothesis. This proves that there are two numbers \(a\) and \(b\) in \(A\) which are not relatively prime.
For a set \(A\) of consisting of positive integers, let \(\ell(A)\) denote the largest integer which can be expressed as the product of two distinct elements of \(A\). What is the smallest element of the set which consists of the integers of the form \(\ell(A)\) as \(A\) runs over the sets of size \(16\) and consisting of positive integers?
Since \(\ell(A)\) is to be minimized as \(A\) runs over the sets \(16\) pairwise coprime integers and \(\ell(A)\) denotes the maximum of the products of the pairs of elements of \(A\), it follows that the minimum value of \(\ell(A)\) is achieved precisely when the elements of \(A\) are as small as possible. This shows that the minimum value of \(\ell(A)\) occurs when \[ A = \left\{ 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 \right\} . \] Hence, the minimum value of \(\ell(A)\) is \(43 * 47 = 2021\).
Lecture notes for Math Olympiad (IOQM, RMO, INMO)
Click on the icons below to download.
Topics Links Algebra Combinatorics Geometry Number Theory INMO Training Camp 2025, MP IMO Training Camp MOPSS Resources