Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta
    • Thread Starter
    Offline

    10
    ReputationRep:
    I'm doing a question which has lead to this statement which I'm trying to prove (I think this is correct):

    If m,n are positive integers and \displaystyle (x_i)_{i=1}^{mn+1}, \displaystyle (y_i)_{i=1}^{mn+1} are sequences of positive integers with (x_i,y_i) distinct and for all i\in\mathbb{N}

    x_i+y_i=mn+2

    then there exists an x_{i_k} and a y_{i_k} such that

    x_{i_k}\geq m+1 or y_{i_k} \geq n+1.

    It looks like I need to use induction to prove this. The case n=1,m=1 is clearly true so assume true for n=p, m=q. The case n=p+1, m=q+1 gives the equation

    x_i +y_i = pq+2+p+q

    but I'm not sure where to go from here. Can someone help?
    Online

    17
    ReputationRep:
    I don't see that the case n=m=1 is true.

    Take x_1 = x_2 = 1, y_1 = y_2 = 2

    For what k is x_k = m+1?
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    I don't see that the case n=m=1 is true.

    Take x_1 = x_2 = 1, y_1 = y_2 = 2

    For what k is x_k = m+1?
    Oops I forgot to say that the pairs (x_i,y_i) must be distinct.
    • Thread Starter
    Offline

    10
    ReputationRep:
    I've also edited my OP to use 'or' instead of 'and'. I think (hope) it's correct now.
    Online

    17
    ReputationRep:
    If all the x_i are distinct, and you have mn+1 of them, then at least one x_i >= mn+1 (pigeonhole) and so x_i >= m+1.

    (I suspect you are still not asking the right question...)
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    If all the x_i are distinct, and you have mn+1 of them, then at least one x_i >= mn+1 (pigeonhole) and so x_i >= m+1.

    (I suspect you are still not asking the right question...)
    The initial question is

    Prove that in any sequence a_1, a_2, ..., a_{mn+1} of mn+1 distinct real numbers, there are either m + 1 numbers (not necessarily consecutive) that occur in increasing order, or n + 1 that occur in decreasing order.

    For each a_i, I set the pair (x_i,y_i) as the longest increasing and decreasing subsequences ending with a_i. I then developed the assumptions in my statement (OP) which I thought were correct and then thought that proving the statement would prove the above theorem.
    Online

    17
    ReputationRep:
    I don't see where your assumptions in the OP come from, and (knowing the standard proof of the problem you've just posted), they seem a lot stronger than are usually used to complete the proof. So I am inclined to think you've gone wrong somewhere, to be honest.

    But if your assumptions are correct, I believe my post #5 is a valid proof.
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    I don't see where your assumptions in the OP come from, and (knowing the standard proof of the problem you've just posted), they seem a lot stronger than are usually used to complete the proof. So I am inclined to think you've gone wrong somewhere, to be honest.

    But if your assumptions are correct, I believe my post #5 is a valid proof.
    Does the standard proof you speak of use the idea of x_i and y_i (defined above) because I was given a hint which uses them.

    'x_i +y_i =mn+2' came from looking at small values of m and n and noticing that the pairs (x_i,y_i) would be a list of the ways of summing to mn+2 with each (x_i,y_i) appearing once e.g. m=1,n=4 the pairs are

    (2,4),(4,2),(1,5),(3,3),(5,1)
    Online

    17
    ReputationRep:
    What you have is close, but not the same. Can you post your hint, using the exact wording?
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    What you have is close, but not the same. Can you post your hint, using the exact wording?
    For each term a_i, consider the ordered pair (x_i, y_i), where x_i and y_i are the lengths of the longest increasing and decreasing subsequences ending with a_i. The conclusion holds if there is an i for which x_i ≥ m + 1 or y_i ≥ n + 1.

    Edit: Oh I noticed that I didn't use the word 'lengths' earlier. Is this what you mean by it almost being correct? Sorry about all the mistakes.
    Online

    17
    ReputationRep:
    In the proof I'm familiar with, x_i is the length of the longest ascending sequence starting with a_i, but y_i is the length of the longest descending sequence ending with a_i. (You can swap ascending and descending etc., but you need one sequence to start with a_i and one to end with a_i).
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    In the proof I'm familiar with, x_i is the length of the longest ascending sequence starting with a_i, but y_i is the length of the longest descending sequence ending with a_i. (You can swap ascending and descending etc., but you need one sequence to start with a_i and one to end with a_i).
    Hmmm but with that definition, wouldn't that make x_i equal to y_i for all i?
    Online

    17
    ReputationRep:
    a_1 =1, a_2 =2, a_3 = 3.

    x_1 = 3 (longest ascending sequence starting with a_1 is a_1, a_2, a_3).
    y_1 = 1 (longest descending sequence ending with a_1 is a_1. (Since a_1 is the first element, the only possible sequence ending in a_1 is a_1 itself).

    [Note: you do realise that when we find these sequences a_i a_j a_k (etc.) we need i < j < k (etc.) don't you?]
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    [Note: you do realise that when we find these sequences a_i a_j a_k (etc.) we need i < j < k (etc.) don't you?]
    No I didn't realise that. Why do you need to assume this?

    I thought a_3,a_2,a_1 would be the longest descending sequence ending in a_1.
    Offline

    0
    ReputationRep:
    From what exam board is this?
    Online

    17
    ReputationRep:
    (Original post by 0-))
    No I didn't realise that. Why do you need to assume this?

    I thought a_3,a_2,a_1 would be the longest descending sequence ending in a_1.
    Because you're looking for a subsequence, and by definition, the indices in a subsequence are increasing.

    To put it another way, a_3, a_2, a_1 is NOT a subsequence of a_1, a_2, a_3.
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by DFranklin)
    Because you're looking for a subsequence, and by definition, the indices in a subsequence are increasing.

    To put it another way, a_3, a_2, a_1 is NOT a subsequence of a_1, a_2, a_3.
    OK I should have known that.

    Now I'm thinking that there's a mistake in the question. Another hint says to find (x_i,y_i) for the sequence e.g. 2,4,1,3,5. This doesn't really show anything if I use the proper subsequence definition. Maybe my lecturer also got confused and meant any sequence with elements taken from the original sequence (in any order)? Or maybe he should have written the question like you did.
    • Thread Starter
    Offline

    10
    ReputationRep:
    (Original post by Straightpath)
    From what exam board is this?
    University maths.
    Online

    17
    ReputationRep:
    I think it's very unlikely he got confused, although the hint doesn't really fit in with the proof I have in mind either. (Obviously, if you do it, you'll find that there's an x_i or y_i that is at least 3, since otherwise the result you're trying to prove would be false).

    What's more revealing is to think what would have to happen if every x_i and y_i was < 3. (or more generally, if the result you're trying to prove was false).

    [N.B. 3 nested spoilers - I've given away most of the answer by the end, but as I'm going to bed now... It's not too difficult to find a solution by googling, as well].

    Spoiler:
    Show
    In that case, there are at most mn values for the pairs (x_i, y_i), so if there are mn+1 pairs, we can find two identical ones. That is, we can find distinct i, j with x_i = x_j and y_i = y_j.

    Spoiler:
    Show
    Now, translate that back into the terms of the original problem. We have two elements a_i and a_j and for both of them, the longest ascending subsequence starting with them is x_i and the longest descending subsequence ending with them has length x_j.

    Spoiler:
    Show
    Now show that we can always use one of a_i, a_j to extend one of the sequences involving the other one. Which contradicts that we had the longest subsequence. So we have a contradiction, so our assumption that the result was false was incorrect and we're done.
    • Thread Starter
    Offline

    10
    ReputationRep:
    Thank you for your help. I have one more question but I'll make a new thread.
 
 
 
Reply
Submit reply
Turn on thread page Beta
Updated: February 2, 2010
Poll
Do you like carrot cake?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.