Board with dimesions $2018 \times 2018$ is divided in unit cells $1 \times 1$. In some cells of board are placed black chips and in some white chips (in every cell maximum is one chip). Firstly we remove all black chips from columns which contain white chips, and then we remove all white chips from rows which contain black chips. If $W$ is number of remaining white chips, and $B$ number of remaining black chips on board and $A=min\{W,B\}$, determine maximum of $A$
Problem
Source: Regional Olympiad - Federation of Bosnia and Herzegovina 2018
Tags: board, Chips, maximum, combinatorics
04.04.2019 11:03
We observe that in the end configuration, the chips should be placed in the cells such that no two chips with same colour should be place in the same row and column. And since we want maximum no. of chips for the colour with minimum chips. All rows and columns must have atleast one chip. Hence if the white chips are placed in intersection of $x$ columns and $y$ rows, then for maximum no. of chips, black chips should be placed in the intersection of $2018-x$ columns and $2018-y$ rows I claim the following end configuration is desired. Let us choose 1009 distinct columns and rows. And place the white chips in the intersection of these rows and columns. And in the intersection of the other column and rows, we place the black chips. So in this configuration, the no. of chips of both the colours are equal and this value is $1009\times 1009=\boxed{1018081}$. Now let us prove that this is maximum. For the sake of contradiction let us think of another configuration which is even greater. So atleast one of the number of rows and columns must be greater than 1009. If both the columns and rows of one colour is more then one of the colours will have more no. of chips. So the other colour would have lesser number of chips then $1009\times 1009$. Hence, the minimum of the colour of both chips must be less than $1009\times1009$. Now, if both rows and columns are less than 1009, then already it is less than $1009\times1009$. So either of the rows and columns of one of the colour must be more and the other for the same colour must be less. In short, if the no. of rows and columns is $x$ and $y$ respectively, then, we want the maximum of $A=min\{xy,(2018-x)(2018-y)\}$ which is greater than 1018081. But if anyone of $xy,(2018-x)(2018-y)$ are greater than 1018081, then their would be one colour which has less than 1018081 chips. So they must be equal. Hence $y=2018-x$. But in all such cases except when $x=1009$, $x(2018-x)$ is less than $1018081$. So contradiction. Hence the answer is $\boxed{1018081}$