2
$\begingroup$

Define a binary step-order set as a finite set S of positive integers si, i = 0 to n-1, where si ≡ 2i (mod 2i+1) for each i from 0 to n-1. So, i is the power of 2 appearing in the prime factorization of si. It’s elementary that binary step-order sets have distinct subset sums.

What is the least upper bound on the number of pairs of disjoint subsets of an n-element binary step-order set S whose sums differ by 1?

1 Answers 1

1

The answer is Fn+1, where {Fi} is the Fibonacci sequence.

Lemma – Let S be a binary step-order set with n elements. For any positive integer k, Fn+1 is an upper bound for the number of pairs of disjoint subsets of S whose sums differ by k, where {Fi} is the Fibonacci sequence.

Proceeding by math induction, first prove the cases n = 1 and n = 2. For n = 1, the only possible pair of disjoint subsets is (S, φ); thus, F2 = 1 is an upper bound for the number of pairs of disjoint subsets with sums differing by k.

For n ≥ 2, observe that finding a pair of disjoint subsets whose sums differ by k is equivalent to finding an n-tuple of coefficients d ∊ {-1, 0, 1}n such that ∑ disi = k – the elements of the higher-sum subset have coefficients 1, the elements of the lower-sum subset (if any – this may be φ) have coefficients -1, and the elements in neither subset have coefficients 0.

For n = 2, we have s0 odd and s1 even. So, there are two cases; s0 > s1 and s0 < s1. For s0 > s1, the only possible coefficient ordered pairs d are (1, 0), (0, 1), (1, -1) and (1, 1); otherwise ∑ disi is not positive. Furthermore, these all yield distinct values of ∑ disi, because s0 + s1 > s0 > s1, and because s1 ≠ s0 – s1 because the former is even and the latter is odd. So, in this case, 1 is an upper bound for the number of disjoint subset pairs whose sums differ by k. For s1 > s0, the only possible coefficient ordered pairs d are (1, 0), (0, 1), (-1, 1) and (1, 1); otherwise ∑ disi is not positive. We have s0 + s1 > s1 > s0, so the only possible way to have ∑ disi = k for two distinct d is if s0 = s1 – s0; i.e., s1 = 2s0. So, in this case, F3 = 2 is an upper bound for this case and the general n = 2 case of the number of disjoint subset pairs whose sums differ by k.

Now, assume that the lemma is true for all positive integers from 1 through n ≥ 2. Consider an n+1 element binary step-order set Sn+1. Let Sn be the n-element set obtained by omitting the odd element of Sn+1 and dividing all the other elements by 2 – clearly Sn is a binary step-order set. Let Sn-1 be the n-1 element set obtained by omitting the odd element of Sn and dividing all the other elements by 2 – clearly Sn-1 is also a binary step-order set. So sn,i = sn+1,i+1 / 2 and sn-1,i = sn,i+1 / 2.

Consider the case where k is even. The coefficient of sn+1,0 must be 0 for any d in the solution set; otherwise ∑ disi is odd and ≠ k. Each solution d = (0, dn+1,1, …, dn+1,n) corresponds to a solution dn for k/2 in Sn via bijection, where dn,i = dn+1,i for i = 0 through n – 1. So, Fn+1 is an upper bound for the number of disjoint subset pairs of Sn+1 whose sums differ by an even k.

Consider the case where k is odd. The coefficient dn+1,0 of sn+1,0 must be either 1 or -1 for any d in the solution set; otherwise ∑ disi is even and ≠ k. Now, for both of k and sn+1,0, we have cases ≡ 1 (mod 4) and ≡ 3 (mod 4); as a consequence, exactly one of k + sn+1,0 and k - sn+1,0 is ≡ 2 (mod 4), and the other is ≡ 0 (mod 4). Say k + sn+1,0 ≡ 0 (mod 4), and k - sn+1,0 ≡ 2 (mod 4); the other case is similar & will be omitted.

Each solution d = (1, dn+1,1, …, dn+1,n) corresponds to a solution dn for |( k - sn+1,0)/2| in Sn via bijection, where

-If k > sn+1,0, dn,i = dn+1,i+1 for i = 0 through n – 1.

-If k < sn+1,0, dn,i = -dn+1,i+1 for i = 0 through n – 1.

So, Fn+1 is an upper bound for the number of disjoint subset pairs of Sn+1 whose sums differ by k with dn+1,0 = 1.

Consider the solutions d where dn+1,0 = -1. We have ∑ disi = k, so ∑ disi + sn+1,0 ≡ 0 (mod 4). Hence, for the ordered n+1 tuple d’ where d’n+1,0 = 0 and d’n+1,i = dn+1,i for i = 1 through n, we have ∑ d’isi ≡ 0 (mod 4). Therefore, d’n+1,1 = dn+1,1 = 0; otherwise ∑ d’isi ≡ 2 (mod 4). Each solution d = (-1, 0, dn+1,2, …, dn+1,n) corresponds to a solution dn-1 for( k + sn+1,0)/4 in Sn-1 via bijection, where dn-1,i = dn+1,i+2 for i = 0 through n – 2. So, Fn is an upper bound for the number of disjoint subset pairs of Sn+1 whose sums differ by k with dn+1,0 = -1. As we have exhausted the two cases for dn+1,0, Fn+2 = Fn+1 + Fn is an upper bound for the total number of disjoint subset pairs of Sn+1 whose sums differ by an odd k, or any positive integer k./

Applying the lemma to k = 1, conclude that Fn+1 is an upper bound on the number of pairs of disjoint subsets of an n-element binary step-order set S whose sums differ by 1. To show that Fn+1 is the least upper bound, we’ll construct a sequence of binary step-order sets where this upper bound is realized.

Let S1 = {1}, S2 = {1,2}, and S3 = {3,2,4}. Given Sn for n ≥ 2, Sn+1 is constructed by setting sn+1,0 = 3, and sn+1,i = 2sn,i-1for i = 1 to n. (The set elements are listed in the order of increasing power of 2 in the prime factorization of the element.) There are 2 solutions for d for S2; namely (1,0) and (-1,1). There are 3 solutions for d for S3; namely (1,-1,0), (1,1,-1) and (-1,0,1). (Because the 0 term of the sum is either 3 or -3, the subtotal of the other terms must be either -2 or 4 to have the sum of 1.) The Fn+2 solutions for Sn+1 are:

-The Fn+1 n+1 tuples d defined by setting dn+1,0 = 1 and dn+1,i = -dn,i-1 for i = 1 to n from all the solutions dn for Sn; plus

-The Fn n+1 tuples d defined by setting dn+1,0 = -1, dn+1,1 = 0 and dn+1,i = dn-1,i-1 for i = 1 to n from all the solutions dn-1 for Sn-1.

Note: I couldn't work out fully how to do sigma notation; hopefully the sum limits are clearly implied.

  • 0
    For things like sigma notation, try latex (http://meta.math.stackexchange.com/questions/107/what-should-go-in-the-math-stackexchange-faq/117#117)2010-09-17
  • 0
    @Cam, thanks. I especially like the tip to look for a question with markup similar to what you want to use, right-click & select show source.2010-09-20