IMO 1979 SL 5

Origin: CZS

Problem

Let n \geq2 be an integer. Find the maximal cardinality of a set M of pairs (j, k) of integers, 1 \leqj < k \leqn, with the following property: If (j, k) \inM, then (k, m) ̸\inM for any m.

Solution

Let A = {x | (x, y) \inM} and B = {y | (x, y) \inM. Then A and B are disjoint and hence |M| \leq|A| \cdot |B| \leq(|A| + |B|)2 \leq n2

. These cardinalities can be achieved for M = {(a, b) | a = 1, 2, . . . , [n/2], b = [n/2] + 1, . . . , n} .