MathDB

29 different sequences of positive integers

Source: IMO LongList 1988, Israel 1, Problem 46 of ILL

November 3, 2005

combinatorics unsolvedcombinatorics

Problem Statement

A_1, A_2, \ldots, A_{29}

are

29

different sequences of positive integers. For

1 \leq i < j \leq 29

and any natural number

x,

we define

N_i(x) =

number of elements of the sequence

A_i

which are less or equal to

x,

and

N_{ij}(x) =

number of elements of the intersection

A_i \cap A_j

which are less than or equal to

x.

It is given for all

1 \leq i \leq 29

and every natural number

x,

N_i(x) \geq \frac{x}{e},

where

e = 2.71828 \ldots

Prove that there exist at least one pair

i,j

(

1 \leq i < j \leq 29

) such that

N_{ij}(1988) > 200.

Back to Problems View on AoPS