IMO 1985 LL GDR35

Origin: GDR

Problem

We call a coloring f of the elements in the set M = {(x, y) | x = 0, 1, . . . , kn −1; y = 0, 1, . . ., ln −1} with n colors allowable if every color appears exactly k and l times in each row and column and there are no rectangles with sides parallel to the coordinate axes such that all the vertices in M have the same color. Prove that every allowable coloring f satisfies kl \leqn(n + 1).