Maths Olympiad Prep

Library / /6 of 33

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Turkey

In how many ways every unit square of a 2018×20182018 \times 2018 board can be colored in red or white such that number of red unit squares in any two rows are distinct and number of red unit squares in any two columns are distinct.

Solution

The answer is 2(2018!)22(2018!)^2. We consider the problem for an n×nn \times n board. Let rir_i be the number of red squares in the ii-th row for i=1,,ni = 1, \dots, n and cjc_j be the number of red squares in the jj-th column for j=1,,nj = 1, \dots, n. Since rirjr_i \neq r_j for every iji \neq j, we see that {r1,,rn}={0,1,,n}{a}\{r_1, \dots, r_n\} = \{0, 1, \dots, n\} \setminus \{a\} for some number aa. Similarly, we have {c1,,cn}={0,1,,n}{b}\{c_1, \dots, c_n\} = \{0, 1, \dots, n\} \setminus \{b\} for some number bb. On the other hand, the number of red squares on the board is both i=1nri\sum_{i=1}^n r_i and j=1ncj\sum_{j=1}^n c_j. Thus, we get a=ba=b.

Note that if ri=0r_i = 0 for some ii, then cjn1c_j \le n-1 for every jj and hence, a=na = n. Moreover, if ri=nr_i = n for some ii, then cj1c_j \ge 1 for every jj and hence, a=0a = 0. Therefore, the missing number is either 00 or nn.
If a=0a = 0, then ri=cj=nr_i = c_j = n for some ii and jj and removing the ii-th row and jj-th column gives us the problem for (n1)×(n1)(n-1) \times (n-1) board with the missing number n1n-1. Similarly, If a=na = n, then ri=cj=0r_i = c_j = 0 for some ii and jj and removing the ii-th row and jj-th column gives us the problem for (n1)×(n1)(n-1) \times (n-1) board with the missing number 00. Therefore, at the beginning we can decide on the missing number in 22 ways but later on it is uniquely determined. We can choose a row and a column to remove in nnn \cdot n ways. Finally, the answer is
2nn(n1)(n1)2211=2(n!)2. 2 \cdot n \cdot n \cdot (n-1) \cdot (n-1) \cdots 2 \cdot 2 \cdot 1 \cdot 1 = 2(n!)^2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.