MathDB

We wish to color the cells of a

n \times n

chessboard with

k

different colors such that for every

i\in \{1,2,...,n\}

, the

2n-1

cells on

i

. row and

i

. column have all different colors.
a) Prove that for

n=2001

and

k=4001

, such coloring is not possible.
b) Show that for

n=2^{m}-1

and

k=2^{m+1}-1

, such coloring is possible.

Problem Statement