IMO 1967 LL SWE51

Origin: SWE

Problem

A subset S of the set of integers 0, . . . , 99 is said to have property A if it is impossible to fill a crossword puzzle with 2 rows and 2 columns with numbers in S (0 is written as 00, 1 as 01, and so on). Determine the maximal number of elements in sets S with property A.

Solution

If there exist two numbers ab, bc \inS, then one can fill a crossword puzzle as  a b b c  . The converse is obvious. Hence the set S has property A if and only if the set of first digits and the set of second digits of numbers in S are disjoint. Thus the maximum size of S is 25.