MathDB

subset of lattice points , 1 <= x <= 12 and 1 <= y <= 13

Source: Austrian Polish 1987 APMC

April 30, 2020

latticeparallelcombinatorial geometrycombinatorics

Problem Statement

Let

M

be the set of all points

(x,y)

in the cartesian plane, with integer coordinates satisfying

1 \le x \le 12

and

1 \le y \le 13

. (a) Prove that every

49

-element subset of

M

contains four vertices of a rectangle with sides parallel to the coordinate axes. (b) Give an example of a

48

-element subset of

M

without this property.