7
$\begingroup$

Given a positive integer $n$. Your friend selects numbers $x_1,x_2,\ldots,x_n\ge 0$, not necessarily distinct. You are allowed to ask him the sum of any subset of numbers that you want. At the end, you should answer whether the numbers can be partitioned into two subsets $A,B$ (that is, $A\cup B$ is the set of all numbers, and $A\cap B$ is empty) such that the sum of the numbers in $A$ is the same as in $B$.

What is the minimum number of questions that always suffice? If you ask for every number separately, this takes $n$ questions. Is it the best you can do?

$\endgroup$
1
+50
$\begingroup$

$n$ questions are required. The following proof could use some polishing, but I think it's essentially correct.

Alice choose $n$ real numbers $x_1, ..., x_n$ and Ben asks the sums of various subsets of $\{x_1, ..., x_n\}.$ After $k$ questions, Ben must state whether can the set be partitioned into two subsets with equal sums. I claim that the minimum value of $k$ that will guarantee success is $k=n$. This is clear when $n=2$, so I will be assuming $n>2.$

Allow me to modify the rules slightly to say that if Alice ever answers incorrectly, Ben wins. This is no real change, since the OP is implicitly assuming Alice always answers correctly. Now suppose that Alice adopts an adversarial approach. She doesn't decide on the numbers in advance, but chooses them (or rather the subset sums) as the game goes along. I claim that if Ben asks only $n-1$ questions, then Alice can find $n$ numbers, consistent with her previous answers, that makes Ben's answer incorrect. This will show that $n$ questions are required, as the numbers Alice comes up with might have been the numbers she came up with in advance if she were playing naively.

Let $\mathbf x = (x_1,...,x_n)^T$ and let $\mathbf {e_1},..., \mathbf{e_n}$ be the natural basis vectors in $\mathbb R^n.$ When Ben asks question number $i$, he is asking for the value of $\mathbf v_i \cdot \mathbf x,$ where $\mathbf v_i$ is the sum of some of the $\mathbf e_k.$ I will call the $\mathbf v_i$ the "question vectors."

To say there is a partition whose two parts have equal sums is to say there exist $a_i \in \{-1,1\}, 1 \le i \le n,$ not all equal, such that $\mathbf p \cdot \mathbf x = 0$ where $\mathbf p = \sum{a_i \mathbf e_i}$. I will call such $\mathbf p$ "partition vectors."

Alice must choose her answers to be consistent, and so that they do not force the existence of an admissible partition. She can choose any number she likes as the answer to the first question. At question number $i,$ if $\mathbf v_i \in \langle \mathbf v_1, ..., \mathbf v_{i-1} \rangle,$ then she must choose the value determined by linearity as her answer. On the other hand, if $\mathbf v_i \in \langle \mathbf v_1, ..., \mathbf v_{i-1} \rangle \ne \langle \mathbf v_1, ..., \mathbf v_{i-1}, \mathbf v_i,\rangle$, then for each partition vector $\mathbf p$ newly in the span, there is a unique answer $s$ that will force $\mathbf p \cdot \mathbf x = 0.$ As there are only finitely many partition vectors, Alice can choose an answer different from all such $s$.

Now when Bob has asked $n-1$ questions, we may assume that the question vectors span a subspace of dimension $n-1.$ (If they do not, Alice generously volunteers the answers for sufficiently many independent question vectors to bring the dimension up to $n-1.$) This gives a system of $n-1$ linearly independent equations in $n$ unknowns. Solving the system gives a polynomial of degree at most one in some parameter $t$ for each of the $x_k.$

Now there must be a partition vector not in the span of the question vectors. Indeed, for $n>2,$ it is easy to see that the $n$ partition vectors with exactly one $-1$ among the $a_i$ are linearly independent, so they can't all be in the span. For each such partition vector $\mathbf p,$ Alice solves the system of equations formed by adjoining $\mathbf p \cdot \mathbf x = 0$ to the system described above, getting a value of $t$ in each case. Now if Ben guesses that there is no admissible partition, Alice chooses the $\mathbf x$ corresponding to one of these $t,$ and if he guesses that there is such a partition, she chooses at $t'$ different from all these finitely many $t$ and computes $\mathbf x.$ In either case, Bob loses.

I've tried to extend this argument to the case where Alice must choose unique numbers, but so far, I've failed. We can add finitely many vectors of the form $\mathbf e_i - \mathbf e_j$ to the partition vectors, and ensure that solutions exist with no equal numbers, but if Alice says there's no admissible partition, how can we be sure that there exists an admissible partition with no duplicated number?

I've also failed at extending this to the case where Alice must choose integers (with repetitions allowed). I have been trying to do it modulo some large prime $p$. The proof carries through in the $n-dimensional$ vector space of the field with $p$ elements, but if we have to exhibit a partition, all we know is that the sums are congruent modulo $p$. My idea was to show that Alice could choose some large (compared to $n$) prime, and then choose her answers as small as possible. I had hoped to be able to show that in this case, the only was the sums can be congruent is if they are equal. I don't think this can be made to work, but I'm not certain.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.