algorithm: weighted sums under rotation

Question

Sorry, I hope this is not too far off topic for stackoverflow. I have an algorithm that I'd like to prove is correct, or find a counter example if it's not.

Here is the problem. I have a set of strictly positive weights: w1, w2, w3, ... wn.

I have a vector of booleans of length m, where m>n. The vector must have exactly n true values and m-n false values.

For example, if m=5 and n=3, then v could be (1, 1, 0, 1, 0)

Next, we have function which maps v vectors to natural numbers:

int f(vector v) {
  sum=0, wIndex=1, pow=1;

  // v must have exactly n ones
  for(int index=0;index<m;index++) {
    if(v[index]==1)
      sum=sum + w[wIndex++]*pow;
    pow=pow*2;
  }
  return sum;
}

where w[wIndex] is gives the weights, w1, w2, w3 ... wn.

EXAMPLE: 
   suppose v=(0, 1, 1, 0, 1) and w1=3, w2=4, w3=6
   f(v) would be 3*2 + 4*4 + 6*16 = 118.

Next Consider circular rotations of v, for example, if v=(0, 1, 1, 0, 1) then rotate(v, 3) is v rotated 3 positions to the left, or (0, 1, 0, 1, 1). Circular rotations preserve m (length) and n (number of ones).

We define the minF(v) to be the minimum f value over all possible circular rotations of v. It could be implemented as follows:

int minF(vector v) {
  int min=f(v);

  for(int amount=1; amount<m; amount++) {
    if(f(rotate(v, amount))<min)
      min=f(rotate(v, amount));
  }
  return min;
}

where rotate(v, k) rotates v by circularly by k places

EXAMPLE:
  suppose v=(0, 1, 1, 0, 1) and all weights are 3
  The rotation that has the minimum f is v=(1, 1, 0, 1, 0),
  Thus minF(v)=3 + 6 + 24 = 33

And now finally we get to the question:

Prove or disprove optimum(m, n) produces the vector such that minF(optimum(m, n)) >= minF(w) for all possible vectors w, of length m with n ones, where optimum is defined as follows:

vector optimum(int m, int n) {
  vector opt=new vector[m];
  int    ones=n, zeros=m-n, balance=0;

  for(int index=0; index<m; index++)
    if(balance<ones) {
      opt[index]=1;
      balance=balance + zeros;
    }
    else {
      opt[index]=0;
      balance=balance - ones;
    }
  }
  return opt;
}

Finally, here are some examples of runs of optimum:

optimum(10, 1) -->  1000000000
optimum(10, 2) -->  1000010000
optimum(10, 3) -->  1001001000
optimum(10, 4) -->  1010010100
optimum(10, 5) -->  1010101010
optimum(10, 6) -->  1101011010
optimum(10, 7) -->  1110110110
optimum(10, 8) -->  1111011110
optimum(10, 9) -->  1111111110

Optimum essentially spreads the ones as far apart as possible.

I've done many empirical tests and this algorithm always seems to work, but I really need a proof that it's correct.

PS If you solve this, I'll buy you a pizza.

Answer 1

Ive found this unexpectedly interesting ... This is what i got after 2 or so hours yesterday. Its not a proof yet, but its a framework for reasoning -- Right now its enough for a proof with a little massaging where n=2 and I think I can build it out to n > 2 but not quite there yet. Alas I have a day job so I have to put it down for a bit.

Hope it helps -- sorry if it doesn't.

---

The weights are not rotate-able. The max pattern for m=9, n=3 is always 000000111, the min pattern is alway 111000000. Generalization of this is trivial.

Consder m=6, n=2 and look at the table. w1_k means the location of w1 is a offset k.

        w1_5,   w1_4,   w1_3,   w1_2,   w1_1,   w1_0 
w2_5     --    000011  000101  001001  010001  100001 
w2_4     --      --    000110  001010  010010  100010
w2_3     --      --      --    001100  010100  100100
w2_2     --      --      --      --    011000  101000
w2_1     --      --      --      --      --    110000
w2_0     --      --      --      --      --      --

Since the value of w1 is constant then we can make simple conclusion about a row it that it is strictly increasing as w1 increases.

        w1_5,    w1_4,    w1_3,    w1_2,    w1_1,    w1_0 
w2_5     --     000011 > 000101 > 001001 > 010001 > 100001 
w2_4     --       --     000110 > 001010 > 010010 > 100010
w2_3     --       --       --     001100 > 010100 > 100100
w2_2     --       --       --       --     011000 > 101000
w2_1     --       --       --       --       --     110000
w2_0     --       --       --       --       --       --

And the same conclusion about a column and w2.

        w1_5,    w1_4,    w1_3,    w1_2,    w1_1,    w1_0 
w2_5     --     000011 > 000101 > 001001 > 010001 > 100001 
                            V        V        V        V
w2_4     --       --     000110 > 001010 > 010010 > 100010
                                     V        V        V
w2_3     --       --       --     001100 > 010100 > 100100
                                              V        V
w2_2     --       --       --       --     011000 > 101000
                                                       V
w2_1     --       --       --       --       --     110000

w2_0     --       --       --       --       --       --

We can see that the rings correspond to the diagonals. This example has three distinct rings. Ive marked with (), [], {}.

        w1_5,    w1_4,    w1_3,    w1_2,    w1_1,    w1_0 
w2_5     --    [000011]>(000101)>{001001}>(010001)>[100001]
                            V        V        V        V
w2_4     --       --    [000110]>(001010)>{010010}>(100010)
                                     V        V        V
w2_3     --       --       --    [001100]>(010100)>{100100} <- minF(100100)
                                              V        V
w2_2     --       --       --       --    [011000]>(101000) <- minF(010100)
                                                       V
w2_1     --       --       --       --       --    [110000] <- minF(000011)

w2_0     --       --       --       --       --       --

What do the rings have in common? It is the distance of the gaps between the 1.

[] = {All sets with 4 continuos 0's and an adject one}  
   = { 100001, 000011, 000110, 001100, 011000, 110000 }
   = ((0,4))

() = {All sets with 3 continuos 0's and one single 0} 
   = { 000101, 001010, 001010, 010100, 101000, 010001, 100010 }
   = ((1,3)) 

{} = {All sets with 2 strings of 2 0's.}
   = { 100100, 010010, 001001 }
   = ((2,2))

I will call ((g_1,g_2)) the gap set for a ring, which describes the gaps between strings. The ring described by {} is the center most ring. In a oddly sized string length the center ring is 1 wide. in an even string length the center ring is 2 wide.

        w1_6,   w1_5,      w1_4,     w1_3,     w1_2,     w1_1,     w1_0 
w2_6     --   [0000011]>(0000101)>{0001001}>{0010001}>(0100001)>[1000001]
                            V         V         V         V         V
w2_5     --      --     [0000110]>(0001010)>{0010010}>{0100010}>(1000010)
                                      V         V         V         V
w2_4     --      --        --     [0001100]>(0010100)>{0100100}>{1000100}
                                                V         V         V
w2_3     --      --        --        --     [0011000]>(0101000)>{1001000}
                                                          V         V
w2_2     --      --        --        --        --     [0110000]>(1010000)
                                                                    V
w2_1     --      --        --        --        --        --     [1100000]

w2_0     --      --        --        --        --        --        --    

{} = ((3,2))
() = ((4,1))
[] = ((5,0))

From the gap set it can be deduced that the distance from the center line is equal to the distance between the 2 gap indicators divided by 2 to the next highest int.

dist_from_center( ((2,2)) ) = ceil(| 2 - 2 | * .5 ) = 0
dist_from_center( ((3,1)) ) = ceil(| 3 - 1 | * .5 ) = 1
dist_from_center( ((4,0)) ) = ceil(| 4 - 0 | * .5 ) = 2

dist_from_center( ((3,2)) ) = ceil(| 3 - 2 | * .5 ) = 1
dist_from_center( ((4,1)) ) = ceil(| 4 - 1 | * .5 ) = 2
dist_from_center( ((5,0)) ) = ceil(| 5 - 0 | * .5 ) = 3   

So then bringing it back to the thereom then if the dist between the elements in gap_set a is greater than the dist in gap_set b then there must be an element in gap set a that is less than some element in gap set b.

dist_from_center( ((a_1,a_2)) ) > dist_from_center( ((b_1,b_2)) ) 
    ==Implies==> minF( ((a_1, a_2)) ) < minF( ((b_1, b_2)) ) 

Which supports you thereom that spreading the 1's as much as possible results in the maximum minF for a set of strings.