Tuesday, July 19, 2005

International Math Olympiad

Here is an interesting problem from this year's International Math Olympiad:

In a mathematical competition 6 problems were posed to the contestants. Each pair of problems was solved by more than 2/5 of the contestants. Nobody solved all 6 problems. Show that there were at least 2 contestants who each solved exactly 5 problems.
(HT: Ars Mathematica)
Posted by Suresh Venkatasubramanian at 7/19/2005 06:15:00 PM

1 comment:

  1. Anonymous8/22/2005 08:10:00 AM

    Here's a possible proof:
    First some notation:

    Let P_i be the set of all students who solve problem i.

    and define P_ij = P_i n P_j (n is for intersection)

    Likewise P_ijk... = P_i n P_j n P_k...

    N(S) be the number of elements in set S.

    5k+r -> be the number of students (0<= r < 5)

    for different r in 5k+r , let s(r) = minimum of N(P_ij) for each r
    ( more than 2/5 students are in P_ij i.e.)

    r | s(r)
    _______________________________
    0 | 2k+1
    1 | 2k+1
    2 | 2k+1
    3 | 2k+2
    4 | 2k+2
    _______________________________

    N(P_ij) >= s(r) --------------(0)

    The set we are interested in the problem is

    P = P_12345 U P_12346 U P_12356 U P_12456 U P_13456 U P_23456

    which can rewritten as

    P = P_123 n ( P_45 U P_56 U P_46 ) U P_456 n ( P_12 U P_23 U P_31 )

    Proof is by contradiction :
    suppose that there are less than 2 students in P
    .This means either

    (
    N( P_123) + N( P_45 U P_56 U P_46 ) <= 5k+r+1 ------------(1)
    and
    N(P_456) + N( P_12 U P_23 U P_31 ) <= 5k+r -----------(2)
    )
    or
    (
    N( P_123) + N( P_45 U P_56 U P_46 ) <= 5k+r ------------(1.1)
    and
    N(P_456) + N( P_12 U P_23 U P_31 ) <= 5k+r+1 ------------(2.1)
    )



    from high school

    N( P_ij U P_jk U P_ik ) = N( P_ij)+ N(P_jk) + N(P_ik ) - 2N(P_ijk )

    (1) becomes

    N( P_123) + N( P_45 ) +N( P_56) +N(P_46 ) - 2N(P_456) <= 5k+r+1

    but since each N( P_ij) > 2/5 of students = s(r)

    N( P_45)+ N(P_56) + n(P_46 ) >= 3 s(r)
    N( P_12)+ N(P_23) + n(P_31 ) >= 3 s(r)

    and so (1) & (2) reduce to ,
    N( P_123) + 3 s(r) - 2N(P_456) <= 5k+r+1 ---------------(3)
    N( P_456) + 3 s(r) - 2N(P_123) <= 5k+r ------------(4)

    (3) + 2*(4) gives

    -3*N(P_123) + 9 s(r) < 3*(5k+r) + 1

    N(P_123) >= 3*s(r) -5k-r-1/3
    and so N(P_456) >= 3*s(r) -5k-r-2/3

    similarily (1.1) and (2.1) reduce to

    N(P_123) >= 3*s(r) -5k-r-2/3
    and so N(P_456) >= 3*s(r) -5k-r-1/3

    in both cases since we are dealing with integers , we can remove terms
    1/3 and 2/3 in RHS

    N(P_123) >= 3*s(r) -5k-r
    N(P_456) >= 3*s(r) -5k-r

    Since there is nothing special about P_123 and P_456
    N(P_ijk) >= 3*s(r) - 5k - r -----------------------(5)

    Now consider P_12 n (P_345 U P_346 U P_456 U P_356 ) --(a)
    which contains all set of the form P_ijklm except two of them
    again by the assumption we made(less than 2 students solve 5)

    pigeonhole princeple gives

    N(P_12) + N(P_345) + N(P_346) + N(P_456) + N(P_356) - 3*N(P_3456) <= 5k+r+1

    from (0) and (5)

    s(r) + 4* (3*s(r) - 5k - r) - 3 N( P_3456 ) <= 5k+r+1

    13*s(r) - 5*(5k+r) -1 <= 3 *N(P_3456)

    again since there is nothing special about the set P_3456 we choose

    N( P_ijkl ) >= 1/3*( 13*s(r) - 25k - 5r - 1 ) ----------(6)

    r | 13*s(r) - 25k-5r-1
    ___________________________
    0 | 1/3*( k+12 )
    1 | 1/3*( k+7 )
    2 | 1/3*( k+2 )
    3 | 1/3*( k+10 )
    4 | 1/3*( k+5 )
    _____________________________

    We will consider the case r = 2 because the RHS in (6) :13*s(r) - 25k-5r-10 is the lowest then.

    N(P_ijkl) >= 1/3*(k+2)


    Now consider set of all students who solve 4 or more problems

    (U P_ijkl) for all 1<= i,j,k,l <= 6

    surely its size is less than eq 5k+r

    and we also know that

    N(U P_ijkl) = Sigma N(P_ijkl) - Sigma N( P_ijkl n P_pqrs ) + Sigma N(P_ijkl n P_pqrs n P_stuv) - other terms of size

    zero


    Consider RHS first ,

    there are 15(=6C2) sets of the type P_ijkl each of size atleast 1/3*(k+2)

    In sets of form ( P_ijkl n P_pqrs ) , P_ijklm appears 5C2=10 times and we ignore other terms like (P_ijklmn) since

    there is no student who solved all 6.

    In sets of form ( P_ijkl n P_pqrs n P_stuv ) each (P_ijklm) appears 5C3=10 times and other terms like (P_ijklmn) whose size= 0

    Note that since N(P_ijklm) appear equal number of times(10 times) in Sigma N( P_ijkl n P_pqrs ) as well as in

    Sigma N(P_ijkl n P_pqrs n P_stuv) they cancel each other.

    So N(U P_ijkl) = Sigma N(P_ijkl)

    there are 15(=6C2) sets of the type P_ijkl each of size atleast 1/3*(k+2)

    Sigma N(P_ijkl) >= 5k+10

    but wait a second.. we know that that the LHS N(U P_ijkl) <= 5k+r <=5k+4

    contradiction.




     

    Posted by enu

    ReplyDelete

Subscribe to: Post Comments (Atom)

Disqus for The Geomblog