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)

Ruminations on computational geometry, algorithms, theoretical computer science and life

## Tuesday, July 19, 2005

### International Math Olympiad

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

Subscribe to:
Post Comments (Atom)

Here's a possible proof:

enu

ReplyDeleteFirst 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