Color a $m\times n$ matrix with black and white color. There is the same number of white squares and black squares. Is it possible to color in a way such that on each row and each column, the number of squares of one color exceeds $\frac{3}{4}$?
I figured out that rearranging the rows and columns wouldn't change anything, but I'm not sure if that would help. Can someone provide a hint on starting this problem?
No, it's not possible.
First, let's sort the rows and columns, as you observed we can do; we'll put all the majority-black rows on top, and all the majority-black columns on the left, so that the matrix gets partitioned into four blocks: the cells whose row and column are both majority-black, the cells where the rows are but the columns aren't, the cells where the columns are but the rows aren't, and the cells whose row and column are both majority-white.
I'll scale everything down to a $1\times 1$ square, which will contain some black and white sub-rectangles with the property that every horizontal and vertical line is more than $3/4$ a particular color and the total black area is exactly $0.5$. This will make the numbers a bit easier. We'll call the areas of the four regions above $A,B,C,$ and $D$.
Now, what do we know about this setup?
Let $b(R)$ be the area of all black cells in a region $R$. We know the following things (abusing notation somewhat between the regions and their areas):
$$b(A\cup B) > 0.75(A+B)$$ $$b(A\cup C) > 0.75(A+C)$$ $$b(A) \leq A$$ $$b(A\cup B\cup C) = b(A\cup B) + b(A\cup C) - b(A) > 0.5A+0.75B+0.75C$$ $$0.5 = b(A\cup B\cup C\cup D) = b(A\cup B\cup C) + b(D) \ge b(A\cup B\cup C) > 0.5A+0.75B+0.75C$$
Since $A+B+C+D=1$, we can go from $0.5 > 0.5A+0.75B+0.75C$ to $0 > 0.25B + 0.25C - 0.5D$, or equivalently $B+C < 2D$.
We get similarly for the white areas that $B+C < 2A$.
But observe that since $B/A = D/C$ (as is obvious from the diagram), $BC = AD$, so we have
$$4BC = 4AD = (2A)\cdot(2D) > (B+C)^2 = B^2 + 2BC + C^2$$
$$2BC > B^2 + C^2$$
$$B^2 - 2BC + C^2 < 0$$
$$(B-C)^2 < 0$$
which is a contradiction!
