Results 1 to 2 of 2

Math Help - Finding the biggest sum in a set

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Türkiye
    Posts
    5

    Finding the biggest sum in a set

    Hi, I'm trying to create an algorithm, and I'm stuck at one point. Say I have a set of N items, all have their points, and ordered by their ranks.
    For example:
    list1 = { // N = 4
    1: (item1, points: 100, rank:1),
    2: (item2, points:55, rank:2),
    3: (item3, points:55, rank:2),
    4: (item4, points:45, rank:3) }
    and so on.

    list2 is another list of these 4 (N) items, but with different points, thus different ranks. I'm trying to do a comparison for these two lists, like the sum of the differences of item ranks in two lists.For example:

    list2 = {
    1: (item4, points: 10, rank:1),
    2: (item3, points:9, rank:2),
    3: (item2, points:8, rank:3),
    4: (item1, points:7, rank:4) }

    in this case the sum of differences S = (item1 rank difference + item2 " " + ....) S= 3 + 1 + 0 + 2 = 6
    in order to compare it with the worst case, I need this sum's worst value for different N's.
    so, what is the maximum value of S in terms of N? S_max (N) =?
    Thanks for any help.

    - Notes:
    My solution was assuming the two lists were reversely-ordered for the worst-case sum. Which yielded this solution:
    if (N is even)
    Smax=(N^2)/4 ;
    else (N is odd)
    Smax =((N^2)-1)/4 ;

    But this solution seems to be wrong, since sometimes it yields negativepercent similarity, which means the current sum (S) is greater than Smax.
    Last edited by publicvoid; September 19th 2012 at 05:47 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Finding the biggest sum in a set

    Just so I understand the problem, shouldn't your two lists make S = 3 + 1 + 1 + 3 = 8?
    item 1: positions 1 and 4 difference = 3
    item 2: positions 2 and 3 difference = 1
    item 3: positions 3 and 2 difference = 1
    item 4: positions 4 and 1 difference = 3

    If I've understood, then my guess is that this inversion is the worst case, but I haven't thought about how to prove it.

    Is this the correct statement of your problem (Sym(A) is the set of bijections from A onto itself)?

    Let A = \{1, 2, ..., N\}. For f, g \in Sym(A), define \Delta(f, g) = \Sigma_{a \in A} |f(a)-g(a)|.

    Find the upper bound of \Delta as a function of N = |A|.

    ----

    The one thing I can see quickly is that to exploit that the sum over a set, that includes a bijection of that set, can be permuted to order things in a simplier way. This is exploiting that addition is commutative and that you're summing over everything in the set. When you do that, the order in which you do the summing doesn't matter - you can permute it however you like.

    \Delta(f, g) = \Sigma_{a \in A} |f(a)-g(a)| = \Sigma_{a = 1}^N |f(a)-g(a)| = \Sigma_{b = 1}^N |f(g^{-1}(b))-b| using, generically, a = g^{-1}(b).

    Note that's saying that \Delta(f, g) = \Delta(f \circ g^{-1}, identity).

    This simplfies the the problem to looking for just one function, not two.

    The problem becomes: Find the f \in Sym(A) that maximizes \Sigma_{k = 1}^N |f(k)-k|.

    And, yeah, I bet f(k) = N+1 - k gives the maximum for that sum. With that f, the sum becomes:

    \Sigma_{k = 1}^N |f(k)-k| = \Sigma_{k = 1}^N |(N+1 - k) - k| = \Sigma_{k = 1}^N |N+1 - 2k|

    = \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} |N+1 - 2k| + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N |N+1 - 2k|

    = \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1 - 2k) + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (2k - N- 1)

    = \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1)  - 2\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + 2\Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1)

    = \left(\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1) - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1) \right) + 2 \left( - \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k \right).

    Looking at just the k sums:

    - \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N k

    = -\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \left( -\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1}^N k \right)

    = -2\Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} k + \Sigma_{k = 1}^N k

    = -2q(\lfloor \frac{N+1}{2}\rfloor) + q(N), where q(n) = \frac{n(n+1)}{2}.

    Looking at just the constant sums:

    \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} (N+1) - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N (N+1) \right}

    = (N+1) \left( \Sigma_{k = 1}^{\lfloor \frac{N+1}{2} \rfloor} 1 - \Sigma_{k = 1 + \lfloor \frac{N+1}{2} \rfloor}^N 1 \right)

    = (N+1) \left( \lfloor \frac{N+1}{2} \rfloor - (N + 1 - (1 + \lfloor \frac{N+1}{2} \rfloor) \right)

    = (N+1) \left( 2\lfloor \frac{N+1}{2} \rfloor - N \right).

    Thus when f(k) = N+1 - k, have:

    \Sigma_{k = 1}^N |f(k)-k| =  (N+1) \left( 2\lfloor \frac{N+1}{2} \rfloor - N \right) + 2 \left( -2q(\lfloor \frac{N+1}{2} \rfloor + q(N) \right) ,

    where q(n) = \frac{n(n+1)}{2}.

    Note that \left( 2\lfloor \frac{N+1}{2} \rfloor - N \right) = 1 when N is odd, and 0 when N is even.

    If N even, then \lfloor \frac{N+1}{2} \rfloor = N/2, and so

    q(\lfloor \frac{N+1}{2} \rfloor ) = q(N/2) = (N/2)((N/2)+1)/2 = N(N+2)/8, so

    \Sigma_{k = 1}^N |f(k)-k| =  (N+1)(0) + 2 \left( -2( \frac{N(N+2)}{8} ) + ( \frac{N(N+1)}{2} ) \right)

    = -\frac{N(N+2)}{2} + \frac{2N(N+1)}{2}

    = (\frac{N}{2}) ( -(N+2) + 2(N+1) ) = (\frac{N}{2}) ( N ) = \frac{N^2}{2}.

    If N odd, \lfloor \frac{N+1}{2} \rfloor = (N+1)/2, and so

    q(\lfloor \frac{N+1}{2} \rfloor ) = q((N+1)/2)

    = ((N+1)/2)((N+1)/2)+1)/2 = (N+1)(N+3)/8, so

    \Sigma_{k = 1}^N |f(k)-k| =  (N+1)(1) + 2 \left( -2( \frac{(N+1)(N+3)}{8} ) +  ( \frac{N(N+1)}{2} ) \right)

    =  N+1 + \left( -\frac{(N+1)(N+3)}{2} +  \frac{2N(N+1)}{2} \right)

    =  N+1 + \frac{(N+1)}{2}( -(N+3) + 2N )=  N+1 + \frac{(N+1)}{2}( N-3 )

    =  (N+1) (1 + \frac{N-3}{2}) =  (N+1) \frac{N-1}{2} = \frac{N^2-1}{2}.

    Thus the S = \Delta(f, identity) for that f is \frac{N^2}{2} when N is even, and \frac{N^2-1}{2} when N is odd.
    Last edited by johnsomeone; September 19th 2012 at 09:20 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One biggest subgroup
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 24th 2012, 04:16 PM
  2. Finding the biggest possible value of n
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 11th 2012, 02:52 PM
  3. the biggest area
    Posted in the Geometry Forum
    Replies: 4
    Last Post: September 2nd 2009, 12:30 AM
  4. Replies: 1
    Last Post: April 29th 2009, 08:20 AM
  5. Replies: 1
    Last Post: September 10th 2008, 02:59 PM

Search Tags


/mathhelpforum @mathhelpforum