Given an integer $ n > 3.$ Prove that there exists a set $ S$ consisting of $ n$ pairwisely distinct positive integers such that for any two different non-empty subset of $ S$:$ A,B, \frac {\sum_{x\in A}x}{|A|}$ and $ \frac {\sum_{x\in B}x}{|B|}$ are two composites which share no common divisors.
Problem
Source: Chinese National Olympiad 2009 P6
Tags: induction, number theory, greatest common divisor, combinatorics proposed, combinatorics
15.01.2009 16:26
Fang-jh wrote: Given an integer $ n > 3.$ Prove that there exists a set $ S$ consisting of $ n$ pairwisely distinct positive integers such that for any two different non-empty subset of $ S$:$ A,B, \frac {\sum_{x\in A}x}{|A|}$ and $ \frac {\sum_{x\in B}x}{|B|}$ are two composites which share no common divisors. Here is my solution (may be this solution has some mistakes , because it so long !) Lemma : Exist a set $ S=\{k_1,...,k_n\}$ , the numbers $ \frac{\sum_{x\in A}x}{|A|}$ are different for all subset $ A$ of S . This statement can be prove by induction base on the set $ \{2^k|k\in N\}$ Let $ m$ be an integer great than $ n$ . Consider the set : $ x_i=t k_i.m!+1$ where $ k_i$ are positive integers . Let $ T=\{k_i\}$ and $ {A^{*}}$ is a corresponding of $ A$ Let \[ G(A*)=\sum_{k\in A*}k . \] Thus \[ f(A)=\frac{\sum_{x\in A}x}{|A|}=\frac{t.m!.G(A*)}{|A|}+1 \] For any subset $ A,B$ then we have $ \gcd(f(A),f(B))=\gcd(\frac{t.m!.G(A*)}{|A|}+1,tm!.(\frac{G(A*)}{|A|}-\frac{G(B*)}{|B|}))$ If we choose $ m$ is larger enough then all prime divisor of $ tm!.(\frac{G(A*)}{|A|}-\frac{G(B*)}{|B|}$ is also prime divisor of $ \frac{tm!}{n!}$ , that is also prime divisor of $ tm!.\frac{G(X*)}{|X|}$ for all subset $ X$ . It means that exist an positive integer $ m_0$ such that $ \gcd(f(A),f(B))=1$ for all different subset of S . Choose $ m!.\sum_{x\in S}x <p_1<...<p_{2^n}$ and use chinese remainder theorem ,we can find an integer $ t$ that all $ f(A)$ are composites . Thus problem has been proved .
10.07.2009 05:33
That's China MO 2009 Problem 6
30.12.2010 17:28
I really don't understand the solution of TTSphn ( I know him and I have asked him to verify his solution ) Here is one correct solution for your reference : If we call $ f(A)$ the avarage of all elements of a non- empty set $A$ Lemma : There exists a set $ S$ of positive integers with $ |S| = n \ge 3$ has the propety : if $A ; B $ are diffrent non-empty sets of $S$ then $f(A) ; f(B)$ are different positive integers . proof : Choose $n $ different primes : $ n < p_1 < p_2 < ...<p_n$ and define the set $S$ as follows: $ S = \{ \frac{ \prod_{i=1}^{n} p_i}{p_j} | j = \overline{1;n } \}$ if $A ; B $ are different non-empty subsets of $S$ then there exists at least one index $j ; 1 \le j \le n$ with $ p_j | S(A) ; p_j \not | S(B)$ . Forgive me ; Mathlinkers ; I have a marketing exam tomorrow:D ; I will come back soon.... Ok ; here is the next part : Since $ n! f(A) ; n! f(B)$ are multiple of $ S(A) ; S(B)$ respectively ; and $ n < p_j$ it's easy to see that : $ p_j | n! f(A) ; p_j \not | n! f(B)$ And the consequence is : $f(A) ; f(B)$ are different positive rational numbers $(*)$ Define the set $S_1$ as : $S_1 = \{ n! x | x \in S \}$ If $A ; B $ are two different non-empty subsets of $S_1$ then exists two different non-empty subsets $ A_1 ; B_1 $ of $S$ such that : $ f(A) = n! f(A_1) ; f(B) = n! f (B_1) $ .And as the above claim $(*)$ ; we conclude that $f(A) ; f(B)$ are different positive integers . The lemma was proved completely . The next part will come tomorrow Ok ; Now ; with the set $S$ as desired in the lemma ; we call $k$ - the maximum of all the numbers $f(A)$ ; $A$ maybe an arbitary non-empty subsets of $S$ Define : $ S_2 = \{ k!x +1| x \in S \}$ and with $ A ; B $ are two different non-empty subsets of $S_2$ then exists two different non-empty subsets $ A_1 ; B_1 $ of $S$ such that : $ f(A) = k! f(A_1) +1 ; f(B)= k! f(B_1) +1$ . We will prove that $f(A); f(B)$ are coprime positive integers which lager than $1$ Indeed ; if $ p \in \mathbb{P} ; p | gcd( f(A) ; f(B)) \implies p | k! | f(A_1) - f(B_1)| $ But notice that : $ 1 \le | f(A_1) - f(B_1)| \le k \implies p \le k \implies p| k! \ \ (1)$ But $ p | f(A) ; f(A) = k! f(A_1) +1 \implies p|1 $ ; Absurd !! So ; our claim have also been proved . The last part : Call $l$ - the maximum of all the numbers $f(A)$ ; $A$ maybe an arbitary non-empty subsets of $S_2$ Define : $S_3 = \{ l! + x | x \in S_2 \} $with $ A ; B $ are two different non-empty subsets of $S_3$ then exists two different non-empty subsets $ A_1 ; B_1 $ of $S_2$ such that : $ f(A) = l! +f(A_1) ; f(B)= l!+ f(B_1) $ Of course $ f(A_1) | f(A) $ ; $f(A_1) < f(A) $ and $f(A_1)$ is a positive greater than $1$ ; so $f(A)$ is a composite number ; the similiarity with $f(B)$ Moreover if $ p \in \mathbb{P} ; p | gcd( f(A) ; f(B)) \implies p | | f(A_1) - f(B_1)|$ But $ 1 \le | f(A_1) - f(B_1)| \le l \implies p| l!$ Thus ; $ p| f(A_1) ; f(B_1)$ ; this contradicts with the previous claim . and $fA) ; f(B) $ are two coprime composite number . $ S_3$ is the desired set Done!