Results 1 to 7 of 7

Math Help - Help needed on IMO 1990 question

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Help needed on IMO 1990 question

    (IRN 2) Let S be a set with 1990 elements. P is the set such that its elements are the ordered
    sequences of 100 elements of S. Knowing that any ordered element pair of S appears at most in
    one element of P. (If x = (ab), then we call ordered pair (a, b) appeared in x.) Prove
    that P has at most 800 elements.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello muditg

    It would be helpful if we could see the exact wording of the original question, since this one, as you have punctuated it, does not have a very clear meaning.
    Quote Originally Posted by muditg View Post
    (IRN 2)P is the set such that its elements are the ordered sequences of 100 elements of S. Knowing that any ordered element pair of S appears at most in one element of P. (If x = (ab), then we call ordered pair (a, b) appeared in x.)
    The words I have marked in red do not form a complete sentence, so I can only guess that this should perhaps be part of the definition of the set P.

    Although I have some thoughts which may be helpful, I can't see quite where the 800 comes from. So I am open to corrections or further suggestions/information. My thoughts are these:

    The number of ordered pairs, (a, b), a < b, that can be formed from the elements of the set S is \tfrac{1}{2}1990 \times 1989.

    Each element x \in P is an ordered sequence made up of 100 elements of S. The number of ordered pairs (a,b), a<b, that can be made from 100 elements of S is \tfrac{1}{2}100\times 99. So (if I am understanding the question correctly) this is the number of ordered pairs of S that each element x will 'consume', if each ordered pair can be used at most once in this way. So it would appear that a maximum value on the number of possible elements x \in P is:

    \frac{\tfrac{1}{2}1990 \times 1989}{\tfrac{1}{2}100 \times 99} = 399.8

    This appears to show that |P| < 400, not the 800 of which the question speaks.

    Am I misinterpreting something? Is there something wrong with my reasoning?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    I copied and pasted that question from IMO 1990 longlist verbatim (see attachment). However, the same question appears in a text on Combinatorics in a different, and I hope clear, language. It is question number 106 on the image of the page attached with this message.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Attachments

    Sorry, I pressed the submit button too early. Attachments are with this message. (See problem no. 33 in the longlist for the problem in its original wordings.)
    Attached Thumbnails Attached Thumbnails Help needed on IMO 1990 question-concerned-problem.jpg  
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello muditg

    Thanks for clarifying that you have stated the question exactly as it was set on the paper. I note that it was translated from the Chinese. Perhaps something has been lost in the translation!

    Grandad
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Like a stone-audioslave ADARSH's Avatar
    Joined
    Aug 2008
    From
    India
    Posts
    726
    Thanks
    2
    Quote Originally Posted by Grandad View Post
    Hello muditg

    Thanks for clarifying that you have stated the question exactly as it was set on the paper. I note that it was translated from the Chinese. Perhaps something has been lost in the translation!

    Grandad
    It somehow looks correct to me

    An example
    I consider S having 6 elements and P as 3-ary

    S= {A1,A2,A3,A4,A5,A6}

    p={ (A1,A2,A3), (A1,A5,A6)
    ,.......}

    It means that Ai & Aj can be used only once
    in P I have made , (A1,A3,A4) won't be a member
    as A1 & A3 appeared earlier in (A1,A2,A3)
    ----------------------------------------------------------
    If this was the question than we had to prove that

    no. of elements in p <= something (was 800 in question)


    Please correct me if this was not similar to the question
    Adarsh


    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by muditg View Post
    (IRN 2) Let S be a set with 1990 elements. P is a set whose elements are ordered
    sequences of 100 elements of S. Given that any ordered element pair of S appears at most in
    one element of P (if x = (…a…b…), then we say that the ordered pair (a, b) appeared in x), prove
    that P has at most 800 elements.
    [I have edited the wording to try to clarify what I think the question is asking.]

    The number of ways of selecting an ordered pair from an ordered set of 100 elements is {\textstyle{100\choose2}}=4950. The number of ways of selecting an ordered pair from an (unordered) set of 1990 elements is 1990\times1989=3958110. But \tfrac{3958110}{4950} = 799.618\ldots, so there can be at most 799 of the 100-element sets with all their ordered-pair subsets disjoint.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help needed for question on circles
    Posted in the Geometry Forum
    Replies: 5
    Last Post: November 3rd 2010, 11:42 PM
  2. Help needed with combinatorics question.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 01:56 AM
  3. Putnam 1990 A1
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 20th 2010, 11:23 AM
  4. Help needed for a probablilty question
    Posted in the Statistics Forum
    Replies: 3
    Last Post: February 19th 2010, 11:56 AM
  5. Help needed on function question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 26th 2009, 04:26 PM

Search Tags


/mathhelpforum @mathhelpforum