A set $A$ of positive integers is called uniform if, after any of its elements removed, the remaining ones can be partitioned into two subsets with equal sum of their elements. Find the least positive integer $n>1$ such that there exist a uniform set $A$ with $n$ elements.
Problem
Source: Bulgarian MO 2003: P4
Tags: combinatorics unsolved, combinatorics
22.05.2014 11:58
Suppose we have such uniform set. If all its elements are even, we can divide $2$ from all elements and still have a uniform set, so we can suppose at least one element is odd. The sum of the remaining elements must be even as we're dividing it into two equal sums, so the sum of all elements is odd. Thus if there is an even element, removing this leaves an odd sum of the remaining elements, and we can't divide it into two equal sums. Thus we can suppose that all elements are odd. Clearly $3$ doesn't work. After removing any integer, the remaining two integers clearly can't be partitioned. $5$ also doesn't work, for a less obvious reason. Let's suppose the numbers are $a,b,c,d,e$ in that order, increasing. When we remove $d$, we are left with $a,b,c,e$. Look at the set containing $e$. Suppose $e$ contains $c$. Then $e+c > b+a$, so the sums won't be equal. Similarly, suppose $e$ contains $b$. Then $e+b > c+a$, so the sums won't be equal either. The set containing $e$ can only be either $\{e\}$ or $\{e,a\}$. The same reasoning can be applied to removing $b$ or $c$; in all cases, the set containing $e$ can only be either $\{e\}$ or $\{e,a\}$. But there are three such sets, corresponding to when $b,c,d$ is removed, and they must be pairwise different, contradiction. So $n=5$ is impossible. On the other hand, $n=7$ is trivial: take $A = \{1,3,5,7,9,11,13\}$. - Removing $1$, we have $\{11,13\}$ and $\{3,5,7,9\}$. - Removing $3$, we have $\{1,9,13\}$ and $\{5,7,11\}$. - Removing $5$, we have $\{9,13\}$ and $\{1,3,7,11\}$. - Removing $7$, we have $\{3,5,13\}$ and $\{1,9,11\}$. - Removing $9$, we have $\{7,13\}$ and $\{1,3,5,11\}$. - Removing $11$, we have $\{1,5,13\}$ and $\{3,7,9\}$. - Removing $13$, we have $\{7,11\}$ and $\{1,3,5,9\}$.
23.05.2014 01:56
A slightly harder problem containing this one as a subset: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=224623&
27.10.2021 19:06
The problem is quite straightforward .For $7$,consider the first 7 odds. Then just do casework for number less.