Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
For things like sigma notation, try latex (meta.math.stackexchange.com/questions/107/…) –  Cam Sep 17 '10 at 20:59
    
@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. –  Dan Moore Sep 20 '10 at 20:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.