3n Problem

Posted on January 31, 2015 by Sumant Sumant

I found this in Mathematical miniatures by Titu Andreescu. Suppose we have \{1,2,3,..,3n \} integers divided into three sets of n each. Then one can alway pick an element from each of the three sets such that one can be expressed as the sum of the remaining two.

To begin with lets assume the three sets to be A,B,C such that a \in A, b \in B, c \in C.  Let 1 \in A then 2 either belongs to A or some other set. Let us call that set B.

Let’s assume that there are no good triples, which means if x \in C then (x-1) \in A. Let C contains its n elements as c_1,c_2,c_3,...,c_n. Now suppose c_1-1,c_2-1,c_3-1,...,c_n-1 cannot belong to set B because then we can pick c_n \in C,c_n-1 \in B,1 \in A. Thus all these elements c_1-1,c_2-1,c_3-1,...,c_n-1 should belong to set A, however this would mean A has n+1 elements. So its not possible.

Let us prove the statement if x \in C then (x-1) \in A. Let’s suppose it is not true which means there is a number x \in C such that x-1 \notin A. Clearly x-1 \notin B since otherwise (x,x-1,1) will become the requisite triple. Hence x-1 \in C. Thus if x \in C \Rightarrow x-1 \in C. We know that k is the least element outside A such that k \in B. We will show that if x-k \in C \Rightarrow x-k-1 \in C. Because if x-k \in A then (x-k,k,x) form a triple. If x-k \in B then (k-1,x-k,x-1) is a good triple. Similarly the relation x-k-1 in A means (x-k-1,k,x-1) or if x-k-1 \in B then (1,x-k-1,x-k). We can repeat this argument as many times as possible, concluding that all numbers x-ik and x-ik-1 \in C for i = 1,2,...,k for some i. So it will be an element either in A or B a contradiction showing that x \in C implies x-1 \in A and proving if x \in C then (x-1) \in A.

About Sumant Sumant

I love Math and I am always looking forward to collaborate with fellow learners. If you need help learning math then please do contact me.
This entry was posted in Famous Problem, Number Theory and tagged . Bookmark the permalink.

Leave a comment