MathDB

Good Problem.

Source: IMO ShortList 2004, combinatorics problem 6

March 23, 2005

linear algebramatrixcombinatoricsExtremal combinatoricsIMO Shortlist

Problem Statement

For an

{n\times n}

matrix

A

, let

X_{i}

be the set of entries in row

i

, and

Y_{j}

the set of entries in column

j

,

{1\leq i,j\leq n}

. We say that

A

is golden if

{X_{1},\dots ,X_{n},Y_{1},\dots ,Y_{n}}

are distinct sets. Find the least integer

n

such that there exists a

{2004\times 2004}

golden matrix with entries in the set

{\{1,2,\dots ,n\}}

.

Back to Problems View on AoPS