16
$\begingroup$

This is an interesting question which I haven't found anyone addressing it.

Let $N$ be a fixed natural number, $(a_1, \cdots, a_N), (b_1, \cdots, b_N)$ two $N$-tuples of natural numbers with $a_i, b_j \in \{1, 2. \cdots, N\}$. Does there exist a subcollection $(a_{i_1}, \cdots, a_{i_k})$, $(b_{j_1}, \cdots, b_{j_l})$ so that $$a_{i_1} + \cdots + a_{i_k} = b_{j_1} + \cdots + b_{j_l}?$$

Example : say $N=3$. Consider $(1,1,2)$ and $(1,3,3)$. Obviously there are equal partial sums. Take $1, 2$ from the first triples and $3$ from the second, we got $1+2 =3$.

Or , you can find another equal sum: Take $1 =1$ for example.

For example for $N=4$. Similarly we can always find an equal sum. Let's check this with a few trials. Say we have
$$(4, 4,4,4), (3,3,3,2).$$ We can find at least one equal sum as follows: $4+4 =3+3+2$.

Another trial : $(1,1,1,1)$, $(2,3,2,3)$. We can find easily even more than one equal sum: $1+1=2$, $1+1+1 =3$ etc...

I always found equal partial sums. I couldn't find a counter example. I am asking either for a counter example or a proof.

Remark: I know that the statement is true for two $2N$-tuples with numbers ranged from $1$ to $N$. In this case the proof is easy with the pigeonhole principle. You must get two subgroups which are equal. Moreover you would get sequences which are equal.

But would that hold true for sets of length $N$? The simple proof that works for $2N$ wouldn't hold here. On the other hand I couldn't find any counter example for $N$.

Is it true or not? Is it possible to prove one way or the other?

$\endgroup$
  • $\begingroup$ This is not clear. There is only one set of $N$ numbers from $\{1,\cdots, N\}$. Maybe a numerical example with small $N$ will help clarify. $\endgroup$ – lulu May 11 '18 at 11:11
  • $\begingroup$ No. I mean, the numbers could range from 1 to N. Repetition allowed too. $\endgroup$ – bilanush May 11 '18 at 11:14
  • 1
    $\begingroup$ Hi, I have (quite extensively) edit your question, Please check if it is still what you want to ask. Using $N$-tuples seems to be clearer than multisets IMO. In any case you can just rollback the edit. $\endgroup$ – user99914 May 11 '18 at 23:49
  • 1
    $\begingroup$ OK. Thanx. Not familiar with the name tuples as English isn't my mother tongue. But I believe you know what you are saying. $\endgroup$ – bilanush May 12 '18 at 0:14
  • 1
    $\begingroup$ Can you add or reference the easy proof by pigeonhole principle for $2N$-tuples to the question? $\endgroup$ – mjqxxxx May 21 '18 at 4:07
12
+50
$\begingroup$

Let $a=(a_1,a_2,\ldots,a_n)$ and $b=(b_1,b_2,\ldots,b_n)$ be sequences drawn from $\{1,2,\ldots,n\}$. Assume w.n.l.g. that $a_1 \ge b_1$. Starting with $a'=b'=()$, and keeping track of $S=\sum a' - \sum b'$, repeat the following step (*) $n+1$ times: (1) append the next element of $a$ to $a'$, or (2) append the next element of $b$ to $b'$, or (3) do both; you must choose (1) on the first step and (2) on the second, and your choices must keep $S\in[0,n]$. Since $S$ has now assumed $n+2$ values (counting its initial value of $0$), by the pigeonhole principle it must have assumed the same value twice, say before step $k$ and after step $l\ge k$. Then the elements appended to $a'$ and $b'$ on steps $k$ through $l$ must have equal sums.

This proves that $a$ and $b$ have not only subsets, but contiguous subsequences, with equal sums.

(*) Of course, the proof rests on showing that you can successfully repeat this step -- i.e., that one of the three choices satisfies the constraint on $S$ -- the required number of times. Suppose $a$ and $b$ have elements remaining, and $a_i$ and $b_j$ are their next elements. Choice (1) succeeds unless $S+a_i > n$, and choice (2) succeeds unless $S-b_j < 0$. If both fail, then, choice (3) must succeed, because we have $0 \le n-b_j < S+a_i-b_j <a_i\le n$. So we can repeat the step until either $a$ or $b$ is exhausted: at least $n-1$ additional times after the first two steps, which were forced to choose (1) and (2) respectively, for a total of at least $n+1$ times.

$\endgroup$
  • 1
    $\begingroup$ This is a beautiful combination of dynamic programming and the pigeonhole principle. Well done! $\endgroup$ – Steven Stadnicki May 23 '18 at 18:16

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.