Given is a square board with dimensions $2023 \times 2023$, in which each unit cell is colored blue or red. There are exactly $1012$ rows in which the majority of cells are blue, and exactly $1012$ columns in which the majority of cells are red. What is the maximal possible side length of the largest monochromatic square?
Problem
Source: JBMO Shortlist 2023, C1
Tags: square grid, JBMO, JBMO Shortlist, combinatorics
Assassino9931
02.07.2024 00:32
1011
If there is a square of side length $1012$, then if it is red (blue), there are $1012$ rows (columns) with majority red (blue) and hence at most $1011$ rows (columns) with majority blue (red), contradiction.
Colour the cell $(i,j)$ in red if and only if either $i \leq 1011$ and $j \leq 1011$ OR $i\geq 1013$ OR $i=j=1012$.
crezk
02.07.2024 02:06
generalization for $(2n+1)^2$ is $n$
ItsBesi
29.01.2025 13:46
Finally did a combi Answer: $2011$ Bounding: Let $X$ be the length of the largest monochromatic square. FTSOC assume $X \geq 2012$ Assume that the color in the monochromatic square is blue so if $X \geq 2012$ note that because of the square there should be $1012$ rows which are blue and also $1012$ columns that are also blue hence there are $2023-1012=1011$ columns that the majority of cells are red but this is a contradiction by our condition . $\rightarrow \leftarrow$ Hence $X <2012 \iff X \leq 2011$ Now we just show that $X=2011$ works: Construction
Attachments:
Mhremath
30.01.2025 23:25
easy Let's say this square AZ Square now Let's AZ square side be $A$ $\textcolor{red}{Claim:}$ There is no way that $A\geq 1012$ proof: that's easy to show according to the our AZ square includes oly the same colored unit cells and we know that majority of the rows and columns $A>1012$ is Absurd and$A=1012$ contradict majority then A=1011 is our answer and there is no any contradiction and here is some cells