Maths Olympiad Prep

Library / /11 of 18

Number theory Difficulty 7.2 National olympiad, round 2 Prove it China

Given an integer n3n \ge 3, prove that there exists a set SS of nn distinct positive integers such that for any two distinct nonempty subsets AA and BB of SS, the numbers
xAx,xBx \sum_{x \in A} x, \quad \sum_{x \in B} x
are two coprime composite integers, and xXx\sum_{x \in X} x denotes the sum of all elements of a finite set XX, and X|X| denotes the cardinality of XX.

Solution

Let f(X)f(X) be the average of elements of the finite number set XX.

First of all, make nn different primes p1,p2,,pnp_1, p_2, \dots, p_n which are all bigger than nn, and we prove that for any different nonempty subsets AA, BB of the set S1={(1/pj):1jn}S_1 = \{ \prod (1/p_j) : 1 \le j \le n \}, f(A)f(B)f(A) \ne f(B) always holds.

In fact, we can suppose that i=1npiA\prod_{i=1}^{n} p_i \in A and i=1npiB\prod_{i=1}^{n} p_i \notin B without loss of generality. Every element of BB can be divided by p1p_1, so p1n!f(B)p_1 \mid n! f(B). But AA has exactly one element which cannot be divided by p1p_1, so we find that n!f(A)n! f(A) cannot be divided by p1p_1 (note that p1>np_1 > n), and therefore n!f(A)n!f(B)n!f(A) \ne n!f(B), which follows f(A)f(B)f(A) \ne f(B).

Second, let S2={n!x:xS1}S_2 = \{ n! x : x \in S_1 \}. Then f(A)f(A) and f(B)f(B) are different positive integers when A,BA, B are different nonempty subsets of S2S_2.

In fact, it is easy to see that there exist two sets A1,B1A_1, B_1 which are different nonempty subsets of S1S_1, and f(A)=n!f(A1)f(A) = n! f(A_1), f(B)=n!f(B1)f(B) = n! f(B_1) holds. We get f(A)f(B)f(A) \ne f(B) from f(A1)f(B1)f(A_1) \ne f(B_1), and f(A),f(B)f(A), f(B) are positive integers from A,Bn|A|, |B| \le n and their elements are all positive.

Then, let KK be the largest element of S2S_2. We prove that for every two distinct subsets A,BA, B of the set S3={K!x+1:xS2}S_3 = \{ K! x + 1 : x \in S_2 \}, f(A)f(A) and f(B)f(B) are coprime integers which are both larger than 11.

In fact, it is easy to see that there exist two sets A1,B1A_1, B_1 which are different nonempty subsets of S2S_2, and f(A)=K!f(A1)+1f(A) = K! f(A_1) + 1, f(B)=K!f(B1)+1f(B) = K! f(B_1) + 1 holds. Obviously, f(A)f(A) and f(B)f(B) are different integers which are both larger than 11. If they have common divisors, let pp be a prime common divisor of them without loss of generality. Clearly, we have p(K!f(A1)f(B1))p \mid (K! \cdot |f(A_1) - f(B_1)|). We get 1f(A1)f(B1)K1 \le |f(A_1) - f(B_1)| \le K by 0<f(A1),f(B1)K0 < f(A_1), f(B_1) \le K and f(A1)f(B1)f(A_1) \ne f(B_1), so pKp \le K, which follows pK!f(A1)p \mid K! f(A_1), and then p1p \mid 1 — a contradiction.

Lastly, let LL be the largest element of S3S_3. We prove that for every two distinct nonempty subsets A,BA, B of the set S4={L!+x:xS3}S_4 = \{ L! + x : x \in S_3 \}, f(A)f(A) and f(B)f(B) are two composites which share no common divisors.

In fact, it is easy to see that there exist two sets A1,B1A_1, B_1 which are different nonempty subsets of S3S_3, and f(A)=L!+f(A1)f(A) = L! + f(A_1), f(B)=L!+f(B1)f(B) = L! + f(B_1) holds. Obviously, f(A)f(A) and f(B)f(B) are different integers which are both larger than 11. Because of that, LL is the largest element of S3S_3, and we have f(A1)L!f(A_1) \mid L! and f(A1)f(A)f(A_1) \mid f(A). We find that f(A)f(A) is composite by f(A1)<f(A)f(A_1) < f(A). For a similar reason, f(B)f(B) is composite too. If they have common divisors, let pp be a prime common divisor of them without loss of generality. It is obvious that p(L!f(A1)f(B1))p \mid (L! \cdot |f(A_1) - f(B_1)|). We get 1f(A1)f(B1)L1 \le |f(A_1) - f(B_1)| \le L by 0<f(A1),f(B1)L0 < f(A_1), f(B_1) \le L and f(A1)f(B1)f(A_1) \ne f(B_1), so pLp \le L, which follows pf(A1)p \mid f(A_1) and pf(B1)p \mid f(B_1) — a contradiction of the fact that f(A1)f(A_1) and f(B1)f(B_1) are coprime. This completes the proof.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.