MathDB

Find the maximal cardinality

Source: IMO LongList 1979 - P15

September 15, 2010

graph theorynumber theorymaximizationExtremal Graph TheoryExtremal combinatoricsIMO ShortlistIMO Longlist

Problem Statement

Let

n \geq 2

be an integer. Find the maximal cardinality of a set

M

of pairs

(j, k)

of integers,

1 \leq j < k \leq n

, with the following property: If

(j, k) \in M

, then

(k,m) \not \in M

for any

m.