AoPS - Problem

Source: JBMO Shortlist 2023, C1

Tags: square grid, JBMO, JBMO Shortlist, combinatorics

Orestis_Lignos

28.06.2024 09:11

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?

Assassino9931

02.07.2024 00:32

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