MathDB

Very nice one

Source: IMC 1999 day 1 problem 5

November 19, 2005

graph theorylinear algebralinear algebra unsolved

Problem Statement

Suppose that

2n

points of an

n\times n

grid are marked. Show that for some

k > 1

one can select

2k

distinct marked points, say

a_1,...,a_{2k}

, such that

a_{2i-1}

and

a_{2i}

are in the same row,

a_{2i}

and

a_{2i+1}

are in the same column,

\forall i

, indices taken mod 2n.

Back to Problems View on AoPS