Maths Olympiad Prep

Library / /39 of 65

Combinatorics Difficulty 6.1 National Olympiad Prove it Bulgaria

Problem:
A set of at least three positive integers is called uniform if removing any of its elements the remaining set can be disjoint into two subsets with equal sums of elements. Find the minimal cardinality of a uniform set.

Solution

Solution:
Let A={a1,a2,,an}A=\{a_{1}, a_{2}, \ldots, a_{n}\} be a uniform set. Set S=a1+a2++anS=a_{1}+a_{2}+\cdots+a_{n}. It follows from the given condition that SaiS-a_{i} is an even number for any i=1,2,,ni=1,2, \ldots, n. Suppose that the number SS is even. Then all the numbers aia_{i} are even. Set ai=2bi,i=1,2,,na_{i}=2 b_{i}, i=1,2, \ldots, n. Then it is easy to see that the set B={b1,b2,,bn}B=\{b_{1}, b_{2}, \ldots, b_{n}\} is uniform, too. So, we may assume that SS is an odd number and whence a1,a2,,ana_{1}, a_{2}, \ldots, a_{n} and nn are also odd numbers.

We shall prove that n=7n=7. It is not difficult to check that {1,3,5,7,9,11,13}\{1,3,5,7,9,11,13\} is a uniform set. It remains to show that there are no uniform sets with 5 elements, since it is obvious that the sets with 3 elements are not uniform.

Suppose that A={a1,a2,a3,a4,a5}A=\{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}\} is a uniform set and let a1<a2<a3<a4<a5a_{1}<a_{2}<a_{3}<a_{4}<a_{5}. Considering the set A{a1}A \setminus\{a_{1}\} we see that either a2+a5=a3+a4a_{2}+a_{5}=a_{3}+a_{4} or a2+a3+a4=a5a_{2}+a_{3}+a_{4}=a_{5}. Considering the set A{a2}A \setminus\{a_{2}\} we get that either a1+a5=a3+a4a_{1}+a_{5}=a_{3}+a_{4} or a1+a3+a4=a5a_{1}+a_{3}+a_{4}=a_{5}.

- If a2+a5=a3+a4a_{2}+a_{5}=a_{3}+a_{4} and a1+a5=a3+a4a_{1}+a_{5}=a_{3}+a_{4}, then a1=a2a_{1}=a_{2}.
- If a2+a5=a3+a4a_{2}+a_{5}=a_{3}+a_{4} and a1+a3+a4=a5a_{1}+a_{3}+a_{4}=a_{5}, then a1=a2a_{1}=-a_{2}.
- If a2+a3+a4=a5a_{2}+a_{3}+a_{4}=a_{5} and a1+a5=a3+a4a_{1}+a_{5}=a_{3}+a_{4}, then a1=a2a_{1}=-a_{2}.
- If a2+a3+a4=a5a_{2}+a_{3}+a_{4}=a_{5} and a1+a3+a4=a5a_{1}+a_{3}+a_{4}=a_{5}, then a1=a2a_{1}=a_{2}.

Since all the above possibilities lead to a contradiction, we conclude that there are no uniform sets with 5 elements.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.