In the $200\times 200$ table in some cells lays red or blue chip. Every chip "see" other chip, if they lay in same row or column. Every chip "see" exactly $5$ chips of other color. Find maximum number of chips in the table.
Problem
Source: All Russian Olympiad 2017,Day2,grade 11,P6
Tags: combinatorics
MellowMelon
02.05.2017 04:48
The answer is 3800.
Let any row or column which contains chips of both colors be called purple. Suppose there are $R$ purple rows and $C$ purple columns. Divide the board into four quadrants: $X$ is all cells in both a purple row and column, $Y$ is all cells in only a purple row, and $Z$ is all cells in only a purple column. (The fourth quadrant can't have chips and will be ignored.)
The construction for 3800 is to set $R = C = 190$, leave $X$ empty, put exactly 5 reds and blues in each row of $Y$, and put 5 reds and blues in each column of $Z$.
Now suppose there are at least 3800 chips; we'll show there are exactly 3800. A purple row or column contains at most 10 chips, since more than 5 chips of either color in a purple row or column would violate the condition. So the number of chips is at most $10R + 10C$, meaning that for at least 3800 chips we have $\max(R,C) \geq 190$. WLOG $R \geq C$ and $R \geq 190$. Then $Z$ has size $(200-R)C$, so it can't have more chips than that, and $X$ and $Y$ together are $R$ purple rows and have at most $10R$ chips. So the total number of chips is at most
\[ 10R + (200-R)C \leq 210R - R^2 \leq 3800. \]The first bound is $R \geq C$, and the second is the result of plugging $R = 190$ in since the quadratic is decreasing on $R \geq 190$.
RagvaloD
02.05.2017 14:04
Answer is right. Additional question : what about $N\times N$ table with same conditions ?
GGPiku
02.05.2017 14:16
RagvaloD wrote: Answer is right. Additional question : what about $N\times N$ table with same conditions ? Isn't it $20(n-10)$ with like the same argument for $n=200$?
idkk
12.11.2024 06:51
Probably same as above:- Answer is $3800$ . Construction:- To prove the bound say we have $>3800$ chips. Call a column or row "fulfilled" if it has both blue and red coloured chips . Call a column "red fullfilled" if it contains only red chips[empty ones are not considered] and blue fulfilled similarly. Claim: No two non fullfillied row and columns share a chip. Assume WLOG both are red fullfilled if they share a red chip it will not be able to see any blue chip. Now Then observe if we pick any chip in a non fulfilled row , the column going containing it is fulfillied . similarly for a non fullfilled column Now consider this say we pick a row $R_1$ and $R_2$, $R_2$ is towards right side [not necessarily immeidate right] of $R_1$ containing only red chips and in a column $R_1$ contains a chip but not $R_2$ then we always move the chip to $R_2$. . At the end of this algorithm there will be a max of $5$ red fullfilled rows as we have "Then observe if we pick any chip in a non fulfilled row , the column going containing it is fulfillied . similarly for a non fullfilled column" Similarly do for red fullfilled columns and blue fullfilled ones.hence in each category we have max of $5$ . Claim: Any non fullfilled row / column has a max of $189$ chips. Proof: Pick the non fulfilled row/column with most number of chips say $M$ WLOG say its a row, now count the total number of chips as the sum of number of chips in each column , columns which contain a chip from that non fullfilled row will contain max $10$ chips otherwise max $M$ , so $M(200-M)+10M > 3801 \implies M<190$. Now as there exists a max of $10$ non fullfilled rows , each has max $189$ chips and the fullfilled ones have a max of $10$ So max no of chips $<10*190+190*10=3800$ which is a contradiction