Maths Olympiad Prep

Library / IRL ABooklet /159 of 191

IRL ABooklet

Combinatorics Difficulty 7.0 National Olympiad Prove it Ireland

Each square of an n × n grid is coloured either blue or red, where n is a positive integer. There are k blue cells in the grid. Pat adds the sum of the squares of the numbers of blue cells in each row to the sum of the squares of the numbers of blue cells in each column to form SBS_B. He then performs the same calculation on the red cells to compute SRS_R.
If SB−SR=50S_B - S_R = 50, determine (with proof) all possible values of kk.

Solution

If the ii-th row of the grid has bib_i blue cells, then the contribution to SB−SRS_B - S_R
from this row is bi2−(n−bi)2=2nbi−n2b_i^2 - (n - b_i)^2 = 2nb_i - n^2. Adding these contributions over
all rows yields 2nk−n32nk - n^3 and similarly the columns also contribute 2nk−n32nk - n^3;
thus we have
SB−SR=2(2nk−n3)=2n(2k−n2). S_B - S_R = 2(2nk - n^3) = 2n(2k - n^2).
Next, denote the number of red cells by ℓ\ell, and suppose that there are tt more
blue cells than red cells. Then k+ℓ=n2k+\ell = n^2 and k−ℓ=tk-\ell = t, which implies n2≥tn^2 \ge t.
When we add these two equations we obtain 2k=t+n22k = t+n^2, hence t=2k−n2t = 2k-n^2
and
SB−SR=2n(2k−n2)=2nt. S_B - S_R = 2n(2k - n^2) = 2nt.
Since we are given that SB−SR=50S_B - S_R = 50, this implies that nt=25nt = 25 and so
(n,t)=(5,5)(n,t) = (5,5) or (n,t)=(25,1)(n,t) = (25,1). Note that (n,t)=(1,25)(n,t) = (1,25) is not possible as
n2≥tn^2 \ge t. Using 2k=t+n22k = t+n^2, in the first case, we get k=15k = 15 and in the second
case, k=313k = 313.
The equation SB−SR=2n(2k−n2)S_B - S_R = 2n(2k - n^2) shows that SB−SRS_B - S_R only depends on
the size of the grid and the number of blue cells, but not on the position
of the blue cells. Therefore, making any 15 of the 25 cells of a 5 × 5 grid
blue gives a colouring which satisfy the conditions of the problem for k=15k = 15.
Also, making any 313 of the 625 cells of a 25 × 25 grid blue gives a colouring
which satisfy the conditions of the problem for k=313k = 313.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.