Given $m,n\geq 2$.Paint each cell of a $m\times n$ board $S$ red or blue so that:for any two red cells in a row,one of the two columns they belong to is all red,and the other column has at least one blue cell in it.Find the number of ways to paint $S$ like this.
Problem
Source: 2022 China Southeast Grade 10 P4
Tags: combinatorics
03.08.2022 17:13
I am Chinese,too.The answer is (n+1)^m+n^{m+1}-n^2
06.08.2022 04:07
It's funny how they put P4 as the easiest problem. (when it is the last problem) Case 1: Each row has at most one cell. It's clear that they all satisfy the criteria. Each row can either be all blue or have one red, which gives $(n+1)^m$ possibilities. Case 2: Some row has at least 2 red cells. This means one column is all red and any other column cannot be all red. There are $n$ ways to pick that one column and for the rest $m\times (n-1)$ board that doesn't contain the all red column, no two cells on the same row are red. Hence each of the $m$ rows has $n$ possibilities. As there are $n$ ways to pick the all red column, this gives $n^{m+1}$ colorings. Now we deal with overcounts. The first case is when one column has all red cells and everything else is blue. This case is overcounted once and there are $n$ such boards. The second case is two fully red columns and everything else blue. This is counted twice in case 2, but this is not valid. Therefore I have overcounted $n+(n^2-n)=n^2$. All in all, the answer is $(n+1)^m+n^{m+1}-n^2$