In how many ways every unit square of a $2018$ x $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 squares in any two columns are distinct.
Problem
Source: Turkey EGMO TST 2018 #3
Tags: combinatorics, Coloring, counting
EulersTurban
07.04.2020 17:45
So this problem was a mouthful.....
I will solve a generalization of the problem for a table $n$ side length
First off I will state an invariant in the problem:
"No matter how we swap the rows and columns the configuration is still valid"
This is easily seen when we start experimenting with $n=3,4,5$
We can establish independently that we can the maximum that we can fill in is $n$ and that the minimum is $0$.
So now we divided the problem into cases ($s(n)$ is the number of empty columns,while $v(n)$ will be the number of empty rows):
1.CASEThis case covers when we have $s(n) > 1$ and $v(n) > 1$, so obviously this ain't possible because we have two or more with the same number of red coloured ones in both rows and columns.So it fails.....
2.CASEThis case covers $s(n) > 1$, which obviously isn't possible.....
3.CASEThis case covers $v(n) > 1$, which obviously isn't possible.....
4.CASEThis case covers $v(n) = 1$, so now we have something that works.
So we shall show that $s(n)=1$.So now we design an algorithm that helps us with the covering:
So suppose that $v(n)=1$,so that means that somewhere we have a row that is filled to the brim,so that means one row is colored all red.
The algorithm will keep track of the number of columns with the same number of red ones.Now the algorithm, for $k$ red ones,the next row will have $k-1$ red ones.So if we go forth with our algorithm we see that in the end we will have 2 columns that have the same number of red ones,thus we have that $s(n)=1$
So because we have a row and a column that are white,we see that a maximal number we can color in a row or a column is $n-1$.
So using our invariant we see that we can reorganize any board into the following one:
0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0 0
1 1 1 1 1 1 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 1 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0
(1-red color, 0 -white color, this is an example)
So now we start with our calculations: the empty row can move $n$ times, the other rows will be permutated $(n-1)!$ times and by our algorithm we will have ${n \choose n-1}.{n-1 \choose n-2}.....{3 \choose 2}.{2 \choose 1}= n!$.
Thus by the multiplicative principle we have that the total number of ways is $(n!)^2$
The case where $s(n)=1$ won't be need because in this case as well we have that $v(n)=1$
5. CASEThis case examines $s(n)=0$ and $v(n)=0$
Now by our invariant we have a table of this type:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 0
1 1 1 1 1 0 0 0
1 1 1 1 0 0 0 0
1 1 1 0 0 0 0 0
1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
(1-red color,0-white color,this is an example)
So let's start the calculating procedure is the same as in the 4.CASE (just examine the row with $n$ red ones)
So the number of ways is $(n!)^2$
FINAL STATEMENTSo now by the additive principle we see that the total number of ways is $(n!)^2+(n!)^2=2(n!)^2$.
So now placing this into the context of the problem we get that the total number of ways for $n=2018$ is $2.(2018!)^2$ ........
kris_001
07.04.2020 21:54
electrovector wrote: In how many ways every unit square of a $2018$ x $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 squares in any two columns are distinct.
We consider $n\in \mathbb{N}$ instead of $2018.$
Firstly, we have to prove the following lemma.
\textbf{Lemma:} The $n$ distinct numbers of rows and columns must be ${1,2,\cdots,n}$ or ${0,1,2,\cdots,n-1}.$
\textbf{Proof of the Lemma:} Clearly, totally $n+1$ distinct numbers ${0,1,\cdots,n}$ may occur in $n$ rows and $n$ columns. Suppose some $1<i<n$ does not contained in rows (resp. columns), which implies both $0$ and $n$ are contained in rows (resp. columns), therefore, the $n$ distinct numbers of red squares for each column (resp. rows), says $c(i), 1\leq i\leq n,$ satisfies $1\leq c(i) \leq n-1,$ which is $n-1$ distinct numbers in total. Obviously, it is impossible.
It is obvious to see that the ways for ${1,2,\cdots,n}$ is equal to the ways for ${0,1,2,\cdots,n-1}.$ (By considering white instead of red.) So we only sovle the first case.
Next, we denote $(r_1,r_2,\cdots,r_n; c_1,c_2,\cdots,c_n)$ some possible way for coloring, where $r_i$ denotes the numbers of red squares of the $i-th$ row, and $c_i$ denotes the $i-th$ column.
Finally, we only need to prove that there exists the unique way satisfying $r_i=a_i,$ $c_i=b_i,$ for any distinct $1\leq a_i,b_i\leq n.$
\textbf{The proof of existence:} Consider the original way $(m_{ij})_{1\leq i,j\leq n}$(the $i-th$ row and $j-th$ column) satisfying $m_{ij}$ is $red$ if $i\leq j$. Now we rearrange each rows and columns so that the way satisfies $(a_1,a_2,\cdots,a_n; b_1,b_2,\cdots,b_n).$ Then it's easy to check the new way is as desire. (NOTE: When swapping, the number of blocks in rows and columns does not affect each other.)
\textbf{The proof of uniqueness:} $n=1$ works. We assume it also works for any $i<n.$ For the case $n$, WOLG, the first row's number is $n$ and the first column's is $1$, now we throw away these two lines and we obtain the uniqueness for $n-1.$ Due to each line we just throw away, which is full of red squares, is also unique for any possible way, we finish the proof.
Therefore, the answer is $$2\times\left|\left\{(r_1,r_2,\cdots,r_n; c_1,c_2,\cdots,c_n)|, 1\leq r_i\neq r_j\leq n, 1\leq c_i\neq c_j\leq n, 1\leq i,j\leq n\right\}\right|=2\cdot (n!)^2.$$
[/quote]