# Help needed on IMO 1990 question

• Mar 26th 2009, 10:46 PM
muditg
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 = (…a…b…), then we call ordered pair (a, b) appeared in x.) Prove
that P has at most 800 elements.
• Mar 27th 2009, 06:53 AM
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
(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 = (…a…b…), 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, 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?

• Mar 27th 2009, 10:14 AM
muditg
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.
• Mar 27th 2009, 10:20 AM
muditg
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.)
• Mar 27th 2009, 11:14 AM
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!

• Mar 28th 2009, 03:55 AM
Quote:

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!

It somehow looks correct to me (Thinking)

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 (Happy)

• Mar 28th 2009, 07:36 AM
Opalg
Quote:

Originally Posted by muditg
(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.