# Distinct Multisets with the Same Pairwise Sum

A combinatorial result due to Paul Erdös and John Selfridge has been discussed by R. Honsberger in his *In Pólya's Footsteps*. The problem was also included by Savchev and Andreescu in the wonderful *Mathematical Miniatures*. I reported these results elsewhere. More recently an extension of the discussion was posted in the problem section of the *American Mathematical Monthly* (2008, 758, proposed by Elizabeth R. Chen and Jeffrey C. Lagarius)

_{1}, ..., a

_{n}} of n real numbers (not necessarily distinct), define the sumset S(A) of A to be

_{i}+ a

_{j}: 1 ≤ i < j ≤ n},

- When n is a power of 2 with n ≥ 2, show that there are two distinct multisets A
_{1}and A_{2}such thatS(A _{1}) = S(A_{2}). - When n is a power of 2 with n ≥ 4, show that if r distinct A
_{1}, ..., A_{r}all have the same sumset, thenr ≤ n - 2. - When n is a power of 2 with n ≥ 4, can there be as many as 3 distinct multisets with the same sumset?

A solution by BSI Problems Group, Bomm, Germanny, appeared in Monthly 117, October 2010, pp.747-748 without references to either P. Erdös, R. Honsberger, or S. Savchev.

We recursively construct multisets A

_{m}and B_{m}of size 2^{m}form ≥ 0. For such m, choose arbitrary positive c_{m}. LetA and_{0}= {0}B For_{0}= {c_{0}}.m > 0, letA and_{m}= A_{m-1}∪ {b + c_{m}: b∈B_{m}}B Inductively,_{m}= B_{m-1}∪ {a + c_{m}: a∈A_{m}}.|A and_{m}| = |B_{m}| = 2^{m}S(A Also_{m}) = S(B_{m}).min(A which yields_{m}) = 0 < min(B_{m}),A _{m}≠ B_{m}.First we prove three claims. Let A = {a

_{1}, ..., a_{n}} with a_{1}≤ a_{2}≤ ... ≤ a_{n}, and let S(A) = {s_{1}, ..., s_{n(n-1)/2}} with s_{1}≤ s_{2}≤ ... ≤ s_{n(n-1)/2}.*Claim 1*: a_{2}+ a_{3}∈ {s_{3}, ..., s_{n(n-1)/2}}. Since a_{1}+ a_{2}≤ a_{1}+ a_{3}≤ a_{2}+ a_{3}, we havea Also, the only sums that can be strictly smaller than_{2}+ a_{3}≥ s_{3}.a are_{2}+ a_{3}{a Thus_{2}+ a_{i}: 2 ≤ i ≤ n}.a _{2}+ a_{3}≤ s_{n}.*Claim 2*: Let B = {b_{1}, ..., b_{n}} with b_{1}≤ b_{2}≤ ... ≤ b_{n}. Ifa and_{1}= b_{1}S(A) = S(B), thenA = B. We prove thata by induction on i. Let_{i}= b_{i}A(i) = {a and_{1}, ..., a_{i}}B(i) = {b If_{1}, ..., b_{i}}.A(i - 1) = B(i - 1), thena and_{1}+ a_{i}b are both minimal among S(A) - S(A(i - 1)). Thus_{1}+ b_{i}a _{i+1}= b_{i+1}.*Claim 3*: Let B = {b_{1}, ..., b_{n}} with b_{1}≤ ... ≤ b_{n}. Ifa and_{2}+ a_{3}= b_{2}+ b_{3}S(A) = S(B), thenA = B. Since the two smallest sums from the two sets are equal,a and_{1}+ a_{2}= s_{1}= b_{1}+ b_{2}a With the hypothesis_{1}+ a_{3}= s_{2}= b_{1}+ b_{3}.a we have_{2}+ a_{3}= b_{2}+ b_{3},a Claim 2 now applies._{1}= b_{1}.Given these claims, let A

^{1}, ..., A^{n-1}be multisets of size n having the same sumset. Write A^{k}= {a_{1}^{(k)}, ..., a_{n}^{(k)}} with a_{1}^{(k)}≤ ... ≤ a_{n}^{(k)}. By Claim 1, there are at most n - 2 values for the sum of the second and third smallest elements. By the pigeonhole principle, there exist distinct k and m such thata By Claim 3,_{2}^{(k)}+ a_{3}^{(k)}= a_{2}^{(m)}+ a_{3}^{(m)}.A Thus at most n - 2 multisets can have the same sumset._{k}= A_{m}.The answer is yes. Let A = {0, 4, 4, 4, 6, 6, 6, 10}, B = {2, 2, 2, 4, 6, 8, 8, 8, }, and C = {1, 3, 3, 3, 7, 7, 7, 9}. With exponents denoting multiplicity, S(A), S(B), and S(C) all equal {4

^{(3)}, 6^{(3)}, 8^{(3)}, 10^{(10)}, 12^{(3)}, 14^{(3)}, 16^{(3)}}.

**Note**: The GCHQ Problem Solving Group solved part (a) by letting A_{1} be the set of nonnegative integers less than 2n whose binary expansion has an even number of ones and setting A_{2} = {0, 1, 2, ..., 2n - 1} - A_{1}. This results from the construction given above by setting _{m} = 2^{m}.

For part (c), Daniele Degiorgi gave the example A = {0, 6, 7, 9, 11, 13, 14, 20}, B = {1, 5, 6, 8, 12, 14, 15, 19}, and C = {2, 4, 5, 9, 11, 15, 16, 18}, showing that it can be solved with sets (i.e., multisets with no repeated elements).

It remains open whether there are quadruples of multisets of size greater than 2 with the same sumset, or whether there are triples of multisets of any size greater than 2 other than 8 with the same sumset. Richard Stong showed that the search for such triples can be restricted to multisets whose size is an odd power of 2.

### References

- R. Honsberger,
*In Pólya's Footsteps*, MAA, 1999, pp. 243-246. - S. Savchev, T. Andreescu,
*Mathematical Miniatures*, MAA, 2003, pp. 193-196

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny