MathDB

2011^2 lattice points (x, y), subset with >= 4x2011x\sqrt{2011} points

Source: New Zealand NZMOC Camp Selection Problems 2011 Seniors 6

September 18, 2021

combinatoricscombinatorial geometry

Problem Statement

Consider the set

G

2011^2

points

(x, y)

in the plane where

x

and

y

are both integers between

1

and

2011

inclusive. Let

A

be any subset of

G

containing at least

4\times 2011\times \sqrt{2011}

points. Show that there are at least

2011^2

parallelograms whose vertices lie in

A

and all of whose diagonals meet at a single point.