Results 1 to 8 of 8

Math Help - Sequence LHS element > RHS element

  1. #1
    Newbie
    Joined
    Oct 2013
    From
    AUS
    Posts
    5

    Sequence LHS element > RHS element

    Hello,

    Basically I have to construct a sequence that maximises the number of times such that given any pair of numbers, the left-hand one will be greater than the right-hand one. The sum of the positive integer sequence must be 2014.
    An example is 7,4,1,3,2
    We can select (7,4) ; (7,1) ; (7,3) ; (7,2) ; (4,1) ; (4,3) ; (4,2) ; (3,2) such that the number occurring first is greater than the number occurring last (i.e. LH number > RH number)
    So far I figure it will be {2,2......,2,2} (504 2s) and then {1,1,.....,1,1} (1006 1s). \
    The two reasons for this are that we should keep a maximum difference at one between numbers otherwise we are unnecessarily adding numbers. The second is that the use of only 2s and 1s will assist in keeping the sum small.
    Is this correct and is there a formal way of writing what I have said if it is correct?

    Thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,838
    Thanks
    707

    Re: Sequence LHS element > RHS element

    That depends on what you mean by pairs of numbers. If the only numbers you have are 1 and 2, then the only pairs are (1,1), (2,2), (1,2) and (2,1). That would certainly not be maximized. The left number is greater than the right number only once.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2013
    From
    AUS
    Posts
    5

    Re: Sequence LHS element > RHS element

    I mean if you have a sequence such as 2,2,2,2,1,1,1,1 then the first two can be paired with all of the four ones because it is greater than all of them. The same can be said for the second, third and fourth 2s. The pairs need not be distinct pairs either. So we can have (2,1) repeated 16 times - thus 16 pairs with the earlier number being greater than the later number.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,838
    Thanks
    707

    Re: Sequence LHS element > RHS element

    Suppose you have x_1 1's, x_2 2's, x_3 3's, etc.

    Then \sum_{n \ge 1} nx_n = 2014. Let's count the pairs where the left number is bigger than the right. There are x_i\cdot x_j pairs (j,i) with i<j. So, there are \sum_{i<j}x_i\cdot x_j total pairs of the form you want. Try solving for one variable, plugging it into the formula, taking partial derivatives with respect to one variable, setting it equal to zero and solving for that variable. Plugging it back into the formula, etc.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2013
    From
    AUS
    Posts
    5

    Re: Sequence LHS element > RHS element

    The solution is supposed to not utilise calculus
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,838
    Thanks
    707

    Re: Sequence LHS element > RHS element

    Ok, then I will tell you that you are correct. That is one possible solution, and the other is 503 2's, 1008 1's.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2013
    From
    AUS
    Posts
    5

    Re: Sequence LHS element > RHS element

    haha, so do you think careful reasoning would suffice?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,838
    Thanks
    707

    Re: Sequence LHS element > RHS element

    You could also say that 2014 = a + 2x and you are trying to maximize y = ax (where y is the number of pairs where the left number is bigger than the right, a is the number of 1's, x is the number of 2's). Solving for a, you get a = 2014-2x. So, you are trying to maximize y = (2014-2x)x = 2014x-2x^x. If x is a real number, this is a parabola, so it rises, then falls. Since x=503 and x=504 give the same value for y, it reaches its maximum between those two points. So, using only integers, either is valid.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory basics: an element of an element
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: February 14th 2013, 08:33 PM
  2. Replies: 3
    Last Post: December 15th 2012, 07:08 PM
  3. Orbits of an element and the Stabilizer of the element
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: December 24th 2011, 05:41 AM
  4. Replies: 4
    Last Post: September 21st 2010, 11:35 AM
  5. Replies: 3
    Last Post: March 23rd 2010, 07:05 PM

Search Tags


/mathhelpforum @mathhelpforum