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)

Given a multiset A = {a1, ..., an} of n real numbers (not necessarily distinct), define the sumset S(A) of A to be {ai + aj: 1 ≤ i < j ≤ n}, a multiset with n(n - 1)/2 not necessarily distinct elements. For instance, if A = {1, 1, 2, 3}, then S(A) = {2, 3, 3, 4, 4, 5}.
  1. When n is a power of 2 with n ≥ 2, show that there are two distinct multisets A1 and A2 such that S(A1) = S(A2).
  2. When n is a power of 2 with n ≥ 4, show that if r distinct A1, ..., Ar all have the same sumset, then r ≤ n - 2.
  3. 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.

  1. We recursively construct multisets Am and Bm of size 2m for m ≥ 0. For such m, choose arbitrary positive cm. Let A0 = {0} and B0 = {c0}. For m > 0, let Am = Am-1 ∪ {b + cm: b∈Bm} and Bm = Bm-1 ∪ {a + cm: a∈Am}. Inductively, |Am| = |Bm| = 2m and S(Am) = S(Bm). Also min(Am) = 0 < min(Bm), which yields Am ≠ Bm.

  2. First we prove three claims. Let A = {a1, ..., an} with a1 ≤ a2 ≤ ... ≤ an, and let S(A) = {s1, ..., sn(n-1)/2} with s1 ≤ s2 ≤ ... ≤ sn(n-1)/2.

    Claim 1: a2 + a3 ∈ {s3, ..., sn(n-1)/2}. Since a1 + a2 ≤ a1 + a3 ≤ a2 + a3, we have a2 + a3 ≥ s3. Also, the only sums that can be strictly smaller than a2 + a3 are {a2 + ai: 2 ≤ i ≤ n}. Thus a2 + a3 ≤ sn.

    Claim 2: Let B = {b1, ..., bn} with b1 ≤ b2 ≤ ... ≤ bn. If a1 = b1 and S(A) = S(B), then A = B. We prove that ai = bi by induction on i. Let A(i) = {a1, ..., ai} and B(i) = {b1, ..., bi}. If A(i - 1) = B(i - 1), then a1 + ai and b1 + bi are both minimal among S(A) - S(A(i - 1)). Thus ai+1 = bi+1.

    Claim 3: Let B = {b1, ..., bn} with b1 ≤ ... ≤ bn. If a2 + a3 = b2 + b3 and S(A) = S(B), then A = B. Since the two smallest sums from the two sets are equal, a1 + a2 = s1 = b1 + b2 and a1 + a3 = s2 = b1 + b3. With the hypothesis a2 + a3 = b2 + b3, we have a1 = b1. Claim 2 now applies.

    Given these claims, let A1, ..., An-1 be multisets of size n having the same sumset. Write Ak = {a1(k), ..., an(k)} with a1(k) ≤ ... ≤ an(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 that a2(k) + a3(k) = a2(m) + a3(m). By Claim 3, Ak = Am. Thus at most n - 2 multisets can have the same sumset.

  3. 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 A1 be the set of nonnegative integers less than 2n whose binary expansion has an even number of ones and setting A2 = {0, 1, 2, ..., 2n - 1} - A1. This results from the construction given above by setting cm = 2m.

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

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

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

Copyright © 1996-2017 Alexander Bogomolny

 62034226

Search by google: