Thread: Help needed on IMO 1990 question

1. 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.

2. 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.
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 $\displaystyle P$.

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

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

Each element $\displaystyle x \in P$ is an ordered sequence made up of $\displaystyle 100$ elements of S. The number of ordered pairs $\displaystyle (a,b), a<b$, that can be made from $\displaystyle 100$ elements of S is $\displaystyle \tfrac{1}{2}100\times 99$. So (if I am understanding the question correctly) this is the number of ordered pairs of $\displaystyle S$ that each element $\displaystyle 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 $\displaystyle x \in P$ is:

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

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

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

Grandad

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.

4. 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.)

5. 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

6. Originally Posted by Grandad
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

7. 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 $\displaystyle {\textstyle{100\choose2}}=4950$. The number of ways of selecting an ordered pair from an (unordered) set of 1990 elements is $\displaystyle 1990\times1989=3958110$. But $\displaystyle \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.