Sizes of a pair of sequences with identical sums of pairs

Question

I am currently collecting various problems for an exam for my students. While looking through old homework assignments of my colleagues I came upon the following problem (marked as difficult):

Given two sequences of natural numbers $\{a_k\}$ and $\{b_k\}$, $k=1,\ldots,n$ (with non-identical sets of elements) such that the sets of their pairwise sums $$\{a_1+a_2,a_1 + a_3,\ldots, a_{n-1}+a_n\}$$ and $$\{b_1+b_2,b_1 + b_3,\ldots, b_{n-1}+b_n\}$$ coincide, show that $n=2^m,\ m\in\mathbb{N}.$

Of course, I am not going to assign a problem I couldn't solve myself to the students, but I would like to see a solution to this. This problem was accompanied with the following tip:

"Use the fact that if for two polynomials $F(x)$ and $G(x)$ if $F(1)=G(1)$, then $F(x)-G(x)=(x-1)^kH(x)$, where $H(1)\neq 0$".

Answer 1

I will show that the statement is true with the condition that

• The two multisets $A=\{a_i+a_j:1 \le i<j\le n\}$ and $B=\{b_i+b_j:1 \le i<j\le n\}$ are the same (i.e. if $x \in A$ appears $k$ times in $A$ then $x$ appears $k$ times in $B$).

• Two sets $\{a_i\}$ and $\{b_i\}$ are not the same.

Let $A(x)=\sum_{i=1}^n x^{a_i}$ and $B(x)=\sum_{i=1}^n x^{b_i}$ then we have $A^2(x)=A(x^2)+2\sum_{i\in A} x^i$ and similarly, $B^2(x)=B(x^2)+2\sum_{i\in B} x^i$. Therefore, $$A(x^2)-B(x^2)=A^2(x)-B^2(x)=[A(x)+B(x)][A(x)-B(x)].$$ Since $A(1)=B(1)=n$ so $A(x)-B(x)=(x-1)^kG(x)$ where $G(1)\ne 0, k \ge 1$.This follows $$(x^2-1)^k G(x^2)=A(x^2)-B(x^2)=[A(x)+B(x)]\cdot (x-1)^k G(x).$$ Therefore, $(x+1)^k G(x^2)=[A(x)+B(x)]G(x)$. Substituting $x=1$ into this and note that $A(1)+B(1)=2n$ and $G(1)\ne 0$, we obtain $n=2^{k-1}$, as desired.

Answer 2

Consider the sequence $(a_k)=(2,4,4)$ and the sequence $(b_k)=(3,3,5)$. Then the two sequences have non-identical sets of elements, but the sets of their pairwise sums are as follows: $$ A=\{2+4,2+4,4+4\}=\{6,8\} $$ $$ B=\{3+3,3+5,3+5\}=\{6,8\} $$

It would then seem that we need to alter the language to make the statement true... maybe it should be a multiset? Maybe the sequences can't have repeated values?

EDIT: Some quick and dirty coding indicates the following question rewrite has a better chance of being true:

Given two sets of natural numbers $A$ and $B$ where $A\neq B$ and $|A|=|B|=n$ such that the restricted sumsets $2^\wedge A$ and $2^\wedge B$ are equal, show that $n=2^m$ for some natural number $m$.

To answer @coffeemath's comment in the OP, you can take $A=\{1,4,5,6\}$ and $B=\{2,3,4,7\}$ as examples of the case $n=4$.