An assignment of either a $ 0$ or a $ 1$ to each unit square of an $ m$x$ n$ chessboard is called $ fair$ if the total numbers of $ 0$s and $ 1$s are equal. A real number $ a$ is called $ beautiful$ if there are positive integers $ m,n$ and a fair assignment for the $ m$x$ n$ chessboard such that for each of the $ m$ rows and $ n$ columns , the percentage of $ 1$s on that row or column is not less than $ a$ or greater than $ 100-a$. Find the largest beautiful number.
Problem
Source: Turkey NMO 2003 Problem 6
Tags: combinatorics unsolved, combinatorics
02.03.2009 15:14
I'm not sure that I understand this correctly. It seems too easy. $ 100-a\ge a$, so $ a\le50$. Now, consider a $ 2\times2$ chessboard, such that A1, B2 contain 1; A2, B1 contain 2. This assignment satisfies the condition with $ a=50$. So 50 is the largest beautiful number.
24.03.2018 23:55
We claim that the largest such number is $75$. It is very easy to cook up a $4\times 4$ chessboard where, the percentage of $1$s on each row/column, is either $\geq 75\%$, or, $\leq 25\%$: $$ \begin{bmatrix}1110 \\0100 \\ 0111 \\ 0010\end{bmatrix}. $$We will now prove that, $a=75$ is the largest beautiful number. For this, we will proceed as follows. Suppose, for the sake of contradiction, that there is a beautiful number $a>75$. Let, $m_1$ be the number of rows, where $1$s are majority; and $m_0$ be the number of rows with $0$s being majority; and define $n_1,n_0$ analogously (for the columns). Next, consider the following counts table, where, $a,b,c,d$ stands for the number of $1$s (for instance, $a$ is the total number of ones, which is sitting at the intersection of $m_1$ rows and $n_1$ columns). \begin{tabular}{ c| c | c | c |} row/column & $n_1$ & $n_0$ \\ \hline $m_1$ & $a$ & $b$ \\ \hline $m_0$ & $c$ & $d$ \\ \hline \end{tabular} First, the givens of the problem encodes as, $a+b > \frac{3m_1n}{4}$, $a+c>\frac{3n_1m}{4}$, $b+d<\frac{n_0m}{4}$, $c+d<\frac{m_0n}{4}$, and, $a+b+c+d = \frac{mn}{2}$. From here, $$ 2m_1n_1 \geq 2a+b+c >\frac{3m_1n+3mn_1}{4} \implies b+c>\frac{3m_1n+3mn_1}{4}-2m_1n_1. $$Next, $b+c+2d<\frac{m_0n+mn_0}{4}$, and therefore, $$ \frac{m_0n+mn_0}{4} = \frac{m_0n_1+2m_0n_0+m_1n_0}{4}>b+c+2d>\frac{3m_1n+3mn_1}{4}-2m_1n_1, $$hence, $$ \frac{m_0n_1+2m_0n_0+m_1n_0}{4}>\frac{3m_1n_0 +3m_0n_1-2m_1n_1}{4}, $$which, after a bit of algebra, gives us, $$ m_1n_1+m_0n_0 > m_1n_0+m_0n_1 \implies \boxed{(m_1-m_0)(n_1-n_0)>0.} $$ \noindent Now, let's return back to the problem, with this inequality in mind. The total number of ones in $m_1$ rows, that is, $a+b$, satisfies, $$ a+b>\frac{3m_1n}{4} \implies c+d<\frac{mn}{2} - \frac{3m_1n}{4}. $$Hence, we have found an upper bound on the total number of $1$s in $m_0$ rows. Subtracting this, from $m_0n$; we get a lower bound on the total number of zeros, in $m_0$ rows (which, together with the ones in $m_0$ rows, add up to $m_0n$; namely, the total number of elements on those rows): \begin{align*} \text{number of zeroes on $m_0$ rows}&> m_0n - \frac{mn}{2}+\frac{3m_1n}{4}\\ &= \frac{n(2m_0+m_1)}{4}=\frac{2m_0n_0+2m_0n_1+m_1n_0+m_1n_1}{4}. \end{align*}Now, some of these zeroes are on $n_0$ columns, and some of them are on $n_1$ columns. We know an upper bound on the total number of zeroes on $n_1$ columns, therefore, it is wise to try to get rid of the possible zeroes, that are living at the intersection of $m_0$ rows and $n_0$ columns: \begin{align*} \text{number of zeros on $m_0 \cap n_1$}& > \frac{2m_0n_0+2m_0n_1+m_1n_0+m_1n_1}{4}- m_0n_0\\ &=\frac{-2m_0n_0+2m_0n_1+m_1n_0+m_1n_1}{4}. \end{align*}Now, all such zeros, that are at the intersection of $m_0$ rows and $n_1$ columns are also living on $n_1$ columns, hence, is upper bounded by the total number of zeros in $n_1$ columns, that is, $$ \frac{mn_1}{4}=\frac{m_0n_1+m_1n_1}{4} > \frac{-2m_0n_0+2m_0n_1+m_1n_0+m_1n_1}{4}, $$which, after some algebra, yields $$ -2m_0n_0+m_0n_1 +m_1n_0<0\implies m_0(n_1-n_0)<n_0(m_0-m_1). $$Now, recall the earlier inequality, $(m_1-m_0)(n_1-n_0)>0$. If, $n_1> n_0$; so do $m_1>m_0$; but in this case, $$ 0>n_0(m_0-m_1)>m_0(n_1-n_0)>0, $$giving us a contradiction. Therefore, $n_1<n_0$; and, $m_1<m_0$. Now, to finish the problem, we will look at the ones on $m_1$ rows. The total number of ones on $m_0$ rows are upper bounded by $\frac{m_0n}{4}$, hence, $$ \text{number of ones in $m_1$ rows}>\frac{mn}{2}-\frac{m_0n}{4}=\frac{(m_0+2m_1)n}{4}. $$Now, some of these ones are on $n_1$ columns, and some on $n_0$ columns. At most $m_1n_1$ of them are on $n_1$ columns, and therefore, \begin{align*} \text{number of ones in $m_1 \cap n_0$}&>\frac{(m_0+2m_1)n}{4}-m_1n_1 \\ &=\frac{m_0n_0 + m_0n_1 +2m_1n_0-2m_1n_1}{4}. \end{align*}Finally, all such ones are also on $n_0$ columns, and therefore, must be upper bounded by the total number of ones on $n_0$ columns, which is known to be upper bounded by $\frac{mn_0}{4}$. If we execute the piece of information, we get, $$ \frac{mn_0}{4}=\frac{m_1n_0+m_0n_0}{4}>\frac{m_0n_0+m_0n_1+2m_1n_0-2m_1n_1}{4}, $$which, after a bit of algebra, gives, $$ m_1n_0+m_0n_1-2m_1n_1<0 \implies m_1(n_0-n_1)<n_1(m_1-m_0). $$Now, using what has been found earlier, we have, $m_1-m_0<0$, and, $n_0-n_1>0$, which, gives us a contradiction. Hence, the largest beautiful number is $\boxed{a=75.}$