Thread: 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.

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 .

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

The number of ordered pairs, , that can be formed from the elements of the set S is .

Each element is an ordered sequence made up of elements of S. The number of ordered pairs , that can be made from elements of S is . So (if I am understanding the question correctly) this is the number of ordered pairs of that each element 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 is:



This appears to show that , not the of which the question speaks.

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

Grandad

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.

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

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

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

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 . The number of ways of selecting an ordered pair from an (unordered) set of 1990 elements is . But , so there can be at most 799 of the 100-element sets with all their ordered-pair subsets disjoint.