2
$\begingroup$

Can such a set $A=$ {$a_1,.. a_k$} exist, such that:

  1. $\sum_i a_i = 1$ and $a_i $ are rational positive numbers
  2. $k$ is and odd number, and is at least $3$.
  3. We can partition $A$ in two parts of value $ \frac{1}{2}$ each
  4. $\forall a_j \in A$, let $B_j := A - a_j$. We can partition $B_j$ into two groups of value $\frac{1-a_j}{2}$.

Examples:
{$\frac{1}{3} , \frac{1}{3}, \frac{1}{9}, \frac{1}{9}, \frac{1}{9}$} respect property 1, 2 4 but not 3.
{$\frac{1}{4}, \frac{1}{4}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}$} respect 1, 2, 3 but not 4: removing any element yields an infeasible problem.
{$\frac{1}{3}, \frac{1}{3}, \frac{1}{6} ,\frac{1}{6} $} respect properties 1, 3, 4, but not 2.

I suppose it should be impossible that such a partition exist. What are your thoughts? By the way, I don't think it is important but $\forall a_j, \quad a_j \le \frac{1}{3}$

$\endgroup$
1
  • 1
    $\begingroup$ A detailed discussion of this problem, and its extension to the reals and to the complex numbers, together with many links to further discussions, can be found at mathoverflow.net/questions/105400/… $\endgroup$ Commented Mar 29, 2022 at 22:33

2 Answers 2

7
$\begingroup$

Multiply by the least common multiple $M$ of the denominators to get the equivalent problem:

  1. The $a_i$ are positive integers.
  2. $k$ is an odd number.
  3. We can partition $A$ into two parts of equal sum.
  4. If we remove any element of $A$, we can partition the remaining elements into two parts of equal sum.

In the rescaled problem, at least one of the $a_i$ is odd, since otherwise we could have rescaled by $\tfrac M2$ to get integers, contradicting $M$ being the least common multiple of the denominators.

Property 3 tells us that the sum of the elements of $A$ is even. Therefore if we remove an odd $a_i$ in step 4, each of the parts needs to sum to a non-integral total, despite being made of integers.

Therefore by contradiction there is no such set $A$.

$\endgroup$
4
  • $\begingroup$ That's simpler that I expected. It's interesting to notice that it all because the $a_i$ are rationals. $\endgroup$
    – Qise
    Commented Mar 28, 2022 at 12:33
  • $\begingroup$ @Qise, nothing I can see in my answer proves that there are solutions with irrational $a_i$. $\endgroup$ Commented Mar 28, 2022 at 14:18
  • 4
    $\begingroup$ 1973 Putnam exam, question B-1: Let $a_1,a_2,\dots,a_{2n+1}$ be a set of integers such that, if any one of them is removed, the remaining ones can be divided into two sets of $n$ integers with equal sums. Prove $a_1=a_2=\cdots=a_{2n+1}$. $\endgroup$ Commented Mar 29, 2022 at 22:19
  • $\begingroup$ A very nice proof, and thus true also for reals (I think). But what if we just say two sets of integers with equal sum and do not require that they be the same size? $\endgroup$ Commented Mar 30, 2022 at 2:00
1
$\begingroup$

In fact it follows from the proof by @PeterTaylor that there are no solutions over the reals. Indeed, if we drop condition 3 then we can have solutions, $k$ is odd and all the $a_i$ are equal. But that is all.

I suspected that the following was true (But I was wrong as shown in the comments):

Suppose $a_1,a_2,\cdots,a_k$ are elements of an abelian group and , if any one is omitted, the other $k-1$ can be split into two sets of equal sum. Then all $k$ elements are equal.

The condition 2, that the numbers be positive is not used, only that they are not (all) zero. This means that the condition that $k$ is odd is not needed since we can just add an $a_{k+1}=0$. Also, it is not used in the proof. The suggested example $\{\frac13,\frac13,\frac16,\frac16\}$ does not satisfy the other conditions: one can't partition $\{\frac13,\frac13,\frac16\}$ into two parts with sum $\frac5{12}.$

We can replace condition 3 by the condition that they are not all equal.

So merely assume

1: $A=\{a_1,\cdots,a_k\}$ is a set of reals, not all equal.

4: If we remove any element of $A$, we can partition the remaining elements $B_i=A-\{a_i\}$ into two parts of equal sum.

Then condition 4 means that there is a homogeneous system of $k$ simultaneous linear equations in $k$ unknowns, with integer coefficients (in fact just $0,\pm1$). If there are any non-trivial solutions then there are rational (and hence integer) solutions. And there could be integer solutions, the $a_i$ could all be equal with $k$ odd. But that is all: if we do add one more equation, as implied by condition $3,$ then we get a system of $k+1$ equations in $k$ variables which, as the proof shows, has no integer solutions. Hence there are no real solutions.

I am not fully satisfied with that. It seems that it should be true in any abelian group. The tags graph-theory and equitable-partition also lead one to hope for a graph-theoretic proof.

$\endgroup$
5
  • 1
    $\begingroup$ The proposed generalization doesn't work. Take $A = \mathbb{Z}/3 \mathbb{Z}$ and $(a_1, a_2, a_3, a_4) = (1,1,2,2)$. Then we have $1+2=1+2$, $1=2+2$ and $1+1=2$. $\endgroup$ Commented Mar 29, 2022 at 21:11
  • $\begingroup$ Quite true. Still, it seems as if something stronger should be true. Maybe total sum zero? $\endgroup$ Commented Mar 29, 2022 at 22:15
  • $\begingroup$ For something strong, see Gerry Myerson's comment on the question. $\endgroup$ Commented Mar 29, 2022 at 23:06
  • $\begingroup$ It is a good reference, but I think I showed more since I did not assume equal size for the two parts. $\endgroup$ Commented Mar 30, 2022 at 3:18
  • $\begingroup$ On the question, not on my answer. He links to mathoverflow.net/q/105400 which also discusses generalisations to abelian groups with no nontrivial element of odd order. I haven't tried to find the relevant article to see exactly what assumptions it makes. $\endgroup$ Commented Mar 30, 2022 at 7:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .