positive real $C$ is $n-vengeful$ if it is possible to color the cells of an $n \times n$ chessboard such that: i) There is an equal number of cells of each color. ii) In each row or column, at least $Cn$ cells have the same color. a) Show that $\frac{3}{4}$ is $n-vengeful$ for infinitely many values of $n$. b) Show that it does not exist $n$ such that $\frac{4}{5}$ is $n-vengeful$.
Problem
Source: 25th Olympic Revenge
Tags: combinatorics, Chessboard
xcubex
04.08.2022 07:11
a) For $n=4$, consider the following chessboard $T$. [asy][asy] unitsize(0.5cm); for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { fill(box((i, j), (i + 1, j + 1)), ((i, j) == (0,0) || (i, j) == (0,1) || (i, j) == (0,2) || (i, j) == (3,1) || (i, j) == (3,2) || (i, j) == (3,3) || (i, j) == (1,1) || (i, j) == (2,2)) ? black : white); } } for (int i = 0; i <= 4; ++i) { draw((i, 0)--(i, 4)); draw((0, i)--(4, i)); draw((i, 0)--(i, 4)); draw((0, i)--(4, i)); } [/asy][/asy] For $n = 4k$, just take a $k \times k$ formed by $k^2$ copies of $T$. b) We will prove that $\frac{3}{4}$ is the best possible constant $C$. Let $A$ and $B$ be the two colors and $UV$ be the sub-table induced by taking the rows with at least $Cn$ cells of the color $U$ and the columns with at least $Cn$ cells of the color $V$, for $U,V \in \{A,B\}$. Let $x$ and $y$ be the proportions of rows and columns with at least $Cn$ cells of the color $A$, respectively. From now on, we will count the proportion of cells that are of a given color (so $z$ cells should be interpreted as $zn^2$ cells). Taking $AB$, $AA$, and $BA$, there are at least $Cx$ $A$ cells in the first two, $Cy$ in the last two, but at most $xy$ in their intersection $AA$. So there are at least $Cx+Cy-xy$ $A$ cells in total and $Cx+Cy-xy\leq \frac{1}{2}\iff C\leq\frac{\frac{1}{2}+xy}{x+y}\leq\frac{\frac{1}{2}+(\frac{x+y}{2})^2}{x+y}\leq\frac{3}{4}\iff 2+(x+y)^2\leq3(x+y)\iff (x+y-1)(2-x-y)\geq 0$, and we are done (WLOG $x +y\geq1$, otherwise change $A$ and $B$).