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)

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 A_m and B_m of size 2^m for m ≥ 0. For such m, choose arbitrary positive c_m. Let A₀ = {0} and B₀ = {c₀}. For m > 0, let A_m = A_m-1 ∪ {b + c_m: b∈B_m} and B_m = B_m-1 ∪ {a + c_m: a∈A_m}. Inductively, |A_m| = |B_m| = 2^m and S(A_m) = S(B_m). Also min(A_m) = 0 < min(B_m), which yields A_m ≠ B_m.

2. First we prove three claims. Let A = {a₁, ..., a_n} with a₁ ≤ a₂ ≤ ... ≤ a_n, and let S(A) = {s₁, ..., s_n(n-1)/2} with s₁ ≤ s₂ ≤ ... ≤ s_n(n-1)/2.

   Claim 1: a₂ + a₃ ∈ {s₃, ..., s_n(n-1)/2}. Since a₁ + a₂ ≤ a₁ + a₃ ≤ a₂ + a₃, we have a₂ + a₃ ≥ s₃. Also, the only sums that can be strictly smaller than a₂ + a₃ are {a₂ + a_i: 2 ≤ i ≤ n}. Thus a₂ + a₃ ≤ s_n.

   Claim 2: Let B = {b₁, ..., b_n} with b₁ ≤ b₂ ≤ ... ≤ b_n. If a₁ = b₁ and S(A) = S(B), then A = B. We prove that a_i = b_i by induction on i. Let A(i) = {a₁, ..., a_i} and B(i) = {b₁, ..., b_i}. If A(i - 1) = B(i - 1), then a₁ + a_i and b₁ + b_i are both minimal among S(A) - S(A(i - 1)). Thus a_i+1 = b_i+1.

   Claim 3: Let B = {b₁, ..., b_n} with b₁ ≤ ... ≤ b_n. If a₂ + a₃ = b₂ + b₃ and S(A) = S(B), then A = B. Since the two smallest sums from the two sets are equal, a₁ + a₂ = s₁ = b₁ + b₂ and a₁ + a₃ = s₂ = b₁ + b₃. With the hypothesis a₂ + a₃ = b₂ + b₃, we have a₁ = b₁. Claim 2 now applies.

   Given these claims, let A¹, ..., A^n-1 be multisets of size n having the same sumset. Write A^k = {a₁^(k), ..., a_n^(k)} with a₁^(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 that a₂^(k) + a₃^(k) = a₂^(m) + a₃^(m). By Claim 3, A_k = A_m. 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⁽³⁾, 6⁽³⁾, 8⁽³⁾, 10⁽¹⁰⁾, 12⁽³⁾, 14⁽³⁾, 16⁽³⁾}.

Note: The GCHQ Problem Solving Group solved part (a) by letting A₁ be the set of nonnegative integers less than 2n whose binary expansion has an even number of ones and setting A₂ = {0, 1, 2, ..., 2n - 1} - A₁. This results from the construction given above by setting c_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

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|