MathDB

2

Part of 2012 Dutch Mathematical Olympiad

Problems(1)

numbers from 1 to n in each column and row of a nxn board, grey cells

Source: Dutch NMO 2012 p2

9/6/2019
We number the columns of an n×nn\times n-board from 11 to nn. In each cell, we place a number. This is done in such a way that each row precisely contains the numbers 11 to nn (in some order), and also each column contains the numbers 11 to nn (in some order). Next, each cell that contains a number greater than the cell's column number, is coloured grey. In the figure below you can see an example for the case n=3n = 3.
[asy] unitsize(0.6 cm);
int i;
fill((0,0)--(1,0)--(1,1)--(0,1)--cycle, gray(0.8)); fill(shift((1,0))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), gray(0.8)); fill(shift((0,2))*((0,0)--(1,0)--(1,1)--(0,1)--cycle), gray(0.8));
for (i = 0; i <= 3; ++i) { draw((0,i)--(3,i)); draw((i,0)--(i,3)); }
label("11", (0.5,3.5)); label("22", (1.5,3.5)); label("33", (2.5,3.5)); label("33", (0.5,2.5)); label("11", (1.5,2.5)); label("22", (2.5,2.5)); label("11", (0.5,1.5)); label("22", (1.5,1.5)); label("33", (2.5,1.5)); label("22", (0.5,0.5)); label("33", (1.5,0.5)); label("11", (2.5,0.5)); [/asy]
(a) Suppose that n=5n = 5. Can the numbers be placed in such a way that each row contains the same number of grey cells? (b) Suppose that n=10n = 10. Can the numbers be placed in such a way that each row contains the same number of grey cells?
boardsquare gridColoringcombinatorics