Determine the largest natural number $ N $ having the following property: every $ 5\times 5 $ array consisting of pairwise distinct natural numbers from $ 1 $ to $ 25 $ contains a $ 2\times 2 $ subarray of numbers whose sum is, at least, $ N. $ Demetres Christofides and Silouan Brazitikos
Problem
Source: BMO 2019, Shortlist
Tags: linear algebra, matrix, Balkan, number theory
rmtf1111
01.10.2019 16:04
Ahhh, theoretically it is not allowed for this problem to be posted. HOWEVER, at the IMO, the italians gave out a small book with their competitions, olympiads from 2019, in which this problem appeared as a TST one, so I think moderators should not delete this post to give a clear message that this problem is leaked and no one uses it.
Pathological
02.10.2019 06:04
Equivalently, over all $5 \times 5$ matrices with distinct entries from $1$ to $25$, we wish to find the minimum possible value of the maximum sum of the values of any $2 \times 2$ subarray of the $5 \times 5$ matrix. The answer is $\boxed{45}$. First, we will show that anything $\le 44$ is unattainable. Let our matrix (call it $M$) be: $$\begin{bmatrix} a & b & c & d & e \\ f & g & h & i & j \\ k & l & m & n & o \\ p & q & r & s & t \\ u & v & w & x & y \end{bmatrix}$$ where $a, b, c, d, \cdots, y$ are $1$ to $25$ in some order. Let $z$ be the maximum sum of any $2 \times 2$ subarray of $M.$ Observe from the definition of $z$ that: $$(a+b+f+g)+(d+e+i+j)+(s+t+x+y)+(p+q+u+v) \le 4z, \qquad (1)$$ and $$(b+c+h+g)+(c+d+i+h)+(i+j+o+n)+(n+o+t+s)+(r+s+x+w)+(q+r+w+v)+(k+l+q+p)+(f+g+l+k)+(g+h+l+m)+(h+i+m+n)+(m+n+s+r)+(l+m+r+q) \le 12z. \qquad(2)$$ By $3 \cdot (1) + (2),$ we obtain that: $$24z \ge 4(a + b + c + \cdots + y) - 2(c+o+w+k) - (a+e+y+u) +2(g+i+s+q), \qquad (3)$$ which yields that: $$24z \ge 4 \cdot 325 - 2(22 + 23 + 24 + 25) - (18 + 19 + 20 + 21) + 2(1 + 2 + 3 + 4). \qquad (4) $$ This implies that $24z \ge 24 \cdot 44 - 2.$ So we've shown that $z \ge 44$, but we haven't yet shown that $z > 44.$ So let's now investigate what must be true when $z = 44.$ Call the $2 \times 2$ subarrays of $M$ which have sum less than $44$ suboptimal. First of all, it's easy to see that at most two $2 \times 2$ subarrays of $M$ can be suboptimal, as otherwise we can strengthen the LHS of $(4)$ to $24z - 3$ and it would no longer hold. Hence, it's now easily seen that there exists a $3 \times 3$ "corner" of $M$ with no suboptimal $2 \times 2$ subarrays. WLOG, the top-left corner of $M$ has no suboptimal $2 \times 2$ subarray (else just rotate the array). Then, we know that $a+b+g+f = b+c+h+g = g+h+m+l = f+g+l+k = 44.$ This implies that $a+m = c+k$. We will show that $a+m = c+k$ is actually inconsistent with the results we have thus obtained. Indeed, we know from $(3)$ and $(4)$ that: $$24z \ge 4(a + b + c + \cdots + y) - 2(c+o+w+k) - (a+e+y+u) +2(g+i+s+q) \ge 4 \cdot 325 - 2(22 + 23 + 24 + 25) - (18 + 19 + 20 + 21) + 2(1+2+3+4) = 24z - 2. \qquad (5)$$ This yields that: $$2(22+23+24+25 - c - o - w - k) + (18 + 19 + 20 + 21 - a - e - y - u) + 2(g+i+s+q - 1 - 2 - 3 - 4) \le 2. \qquad (6)$$ Now, $(6)$ is easily seen to imply that $\{c, o, w, k\} = \{22, 23, 24, 25\}$ or $\{21, 23, 24, 25\}.$ Hence, it's clear that $c+k \ge 21 + 23$ while $a \le 22.$ From $a+m = c+k$, we get that $m = c+k - a \ge 21+23 - 22 = 22.$ Since $\{23, 24, 25\} \subseteq \{c, k, w, o\}$, we have that $m \notin \{23, 24, 25\}$. Hence, this implies that $m = 22.$ However, this means that equality must hold for both of the inequalities $c+k \ge 21 + 23$ and $a \le 22$, which implies that $a = 22.$ But then $a = m = 22$, which is absurd. From the above logic, we conclude that $z = 44$ is unattainable, and so we've shown that $z \ge 45.$ Muriatic the Builder will now construct an example which shows that $z \le 45$:
Muriatic
02.10.2019 06:04
\[ \begin{bmatrix} 23 & 13 & 19 & 12 & 24 \\ 7 & 2 & 9 & 4 & 5 \\ 18 & 16 & 17 & 15 & 21 \\ 8 & 1 & 10 & 3 & 6 \\ 22 & 14 & 20 & 11 & 25 \end{bmatrix} \]
skrublord420
02.01.2020 20:00
kingofgeedorah wrote: Huh where'd posts #3-9 go Good question. Can anyone resolve the mystery of the missing posts?
alexiaslexia
15.11.2020 06:56
The answer is $\boxed{45}$. Firstly, we will prove that among any $5 \times 5$ matrix with distinct naturals in its cells must have a $2 \times 2$ which sum is at least $45$ (say the maximum $2 \times 2$ subarray sum of a $5 \times 5$ matrix to be $z$), implying $z \geq 45$ and we will prove that $z \leq 45$ by directly providing a construction of which any $2 \times 2$ subarray has sum at most $45$. $\textcolor{green}{\textbf{\text{Introduction}.}}$ For notational convenience, we construct the $5 \times 5$ by the $12$ lines $x = i (0 \leq i \leq 5)$ and $y = j (0 \leq j \leq 5)$, we define the $i^{th}$ cell as usual, and we define the centers of each $2 \times 2$ by its location in the two of the twelve lines. For example, the $2 \times 2$ subarray with center $(3,2)$ covers the $13^{th}, 14^{th}, 18^{th}$ and $19^{th}$ cells. Then, by $\textit{toggling}$ the centers $(i_1,j_1), \ldots (i_k, j_k)$ we mean summing all cells (counting multiplicity) of the cells of the subarrays with those centers. $\textcolor{blue}{\textbf{\text{Part 1}.}}$ First, we toggle the subarrays $(1,4), (2,4), (4,4), (1,3), (2,3), (4,3), (1,1), (2,1),$ and $(4,1).$ Then, the multiplicity of each cell is illustrated as in: $$\begin{bmatrix} 1 & 1 & 1 & \textcolor{blue}{2} & 1 \\ 1 & 1 & 1 & \textcolor{blue}{2} & 1 \\ 1 & 1 & 1 & \textcolor{blue}{2} & 1 \\ \textcolor{blue}{2} & \textcolor{blue}{2} & \textcolor{blue}{2} & \textcolor{green}{4} & \textcolor{blue}{2} \\ 1 & 1 & 1 & \textcolor{blue}{2} & 1 \end{bmatrix}$$So, we obtain that by substracting by $1+2+\ldots+25 = \text{sum of all 25 cells}$, we get that the sum of the numbers in the fourth column + fourth row + $19^{th}$ cell is at most $9 \cdot 44 - 325 = 71$. Repeating symmetrically (i.e. rotating our procedure with $90^{\circ}$, $180^{\circ}$ and $270^{\circ})$, we get the expression \[ 2 \cdot (2^{nd} \text{row} + 4^{th} \text{row} + 2^{nd} \text{column} + 4^{th} \text{column}) + 7^{th} \text{cell} + 9^{th} \text{cell} + {17}^{th} \text{cell} + {19}^{th} \text{cell} \leq 4 \cdot 71 = 284 \]which is impossible, as the sum is at least $2 \cdot (1+2+\ldots+16+1+2+3+4)+ 1+2+3+4 = 302$ (the extra $1,2,3,4$ is due to those numbers belonging to both to the $2^{nd}$ row and column, etc). $\textcolor{blue}{\textbf{\text{Part 2}.}}$ We provide two different constructions (a third construction can be found on post $\#11$.) \[ \begin{bmatrix} 17 & 10 & 20 & 7 & 23 \\ 16 & 1 & 14 & 3 & 12 \\ 18 & 9 & 21 & 6 & 24 \\ 15 & 2 & 13 & 4 & 11 \\ 19 & 8 & 22 & 5 & 25 \\ \end{bmatrix} \begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array} \begin{array}{cccc} 44 & 45 & 44 & 45 \\ 44 & 45 & 44 & 45 \\ 44 & 45 & 44 & 45 \\ 44 & 45 & 44 & 45 \\ \end{array} \]\[ \begin{bmatrix} 25 & 11 & 19 & 13 & 23 \\ 7 & 2 & 9 & 4 & 5 \\ 18 & 16 & 17 & 15 & 21 \\ 8 & 1 & 10 & 3 & 6 \\ 22 & 14 & 20 & 12 & 24 \\ \end{bmatrix} \begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array} \begin{array}{cccc} 45 & 41 & 45 & 45 \\ 43 & 44 & 45 & 45 \\ 44 & 44 & 45 & 45 \\ 45 & 45 & 45 & 45 \\ \end{array} \]where the array on the right represents each of the sums in the $4^2$ $2 \times 2$ subarrays.
A first constructional idea I had was "filling out the corners", then spacing out the rest of the big numbers as following:
\[
\begin{bmatrix}
25 & & \textcolor{red}{19} & \textcolor{blue}{16} & 22 \\
\textcolor{blue}{13} & & & & \\
\textcolor{red}{18} & & \textcolor{green}{17} & & \textcolor{red}{21} \\
& & & & \textcolor{blue}{14} \\
23 & \textcolor{blue}{15} & \textcolor{red}{20} & & 24 \\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
25 & \textcolor{red}{5} & 19 & 16 & 22 \\
13 & \textcolor{red}{4} & \textcolor{green}{11} & \textcolor{red}{1} & \textcolor{red}{8} \\
18 & \textcolor{green}{12} & 17 & \textcolor{green}{10} & 21 \\
\textcolor{red}{6} & \textcolor{red}{3} & \textcolor{green}{9} & \textcolor{red}{5} & 14 \\
23 & 15 & 20 & \textcolor{red}{7} & 24 \\
\end{bmatrix}
\begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array}
\begin{array}{cccc}
47 & 39 & 47 & 47 \\
47 & 44 & 39 & 39 \\
39 & 39 & 38 & 47 \\
47 & 47 & 38 & 47 \\
\end{array}
\]With quite a lot of $47$s, but with a vast room of improvement. Here I first considered some faulty and not-so-strong arrays, such as the collection $(1,4),(1,3),(1,1),(2,1),(4,1),(4,2),(4,4),(3,4)$. The simple-minded $(1,4),(1,1),(4,1),(4,4)$ (so close though) did not work, because that prompted me to consider something like
\[
\begin{bmatrix}
25 & & \textcolor{green}{19} & & 22 \\
& & \textcolor{green}{16} & & \\
\textcolor{green}{18} & \textcolor{green}{17} & & \textcolor{green}{15} & \textcolor{green}{21} \\
& & \textcolor{green}{14} & & \\
23 & & \textcolor{green}{20} & & 24 \\
\end{bmatrix}
\]where there is no room left to input any $13$ into the table. From this observation, I deduced that the "9 special squares" ($1,3,5,11,13,15,21,23,25)$ are crucial, as $\textbf{any}$ $2 \times 2$ subarray must contain each of them. (Also, $7,9,17,19$ is special in their own way -- these four squares are part of any subarray as well! I realised their importance too late, however ...)
Here I shifted perspective to relax a bit on the large numbers $22,23,24,25$ so that they do not have to be put on the four corners, but in doing so I realized that these $\textbf{still need to be paired with small numbers}$, as $25$ does with $13,5,4$ in the first configuration. The densest closure I could think of was
\[
\begin{bmatrix}
\textcolor{cyan}{25} & 8 & \textcolor{red}{24} & 7 & \textcolor{green}{23} \\
\textcolor{cyan}{?} & 1 & \textcolor{red}{?} & 2 & \textcolor{green}{?} \\
& & & & \\
\textcolor{magenta}{?} & 3 & \textcolor{yellow}{?} & 4 & \textcolor{blue}{?} \\
\textcolor{magenta}{22}& 6 & \textcolor{yellow}{21} & 5 & \textcolor{blue}{20} \\
\end{bmatrix}
\]of which I thought that three big numbers $23,24,25$ can be covered with only two pairs of numbers $(8,1),(7,2)$. The first configuration of $45$ was then obtained by accident, with me wondering "why don't I just go all the way and instead of considering partial-columns, and just fill all 5 columns with alternating big/small numbers?
But, all of my "global-summing ways" was out of the door after realizing that when the first column is switched with the third, it becomes
\[
\begin{bmatrix}
\textcolor{cyan}{17} & 10 & \textcolor{cyan}{20} & 7 & \textcolor{red}{23} \\
\textcolor{cyan}{16} & 1 & \textcolor{cyan}{15} & 3 & \textcolor{red}{12} \\
\textcolor{cyan}{18} & 9 & \textcolor{cyan}{21} & 6 & \textcolor{red}{24} \\
\textcolor{cyan}{15} & 2 & \textcolor{cyan}{13} & 4 & \textcolor{red}{11} \\
\textcolor{cyan}{19} & 8 & \textcolor{cyan}{22} & 5 & \textcolor{red}{25} \\
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\textcolor{cyan}{20} & 10 & \textcolor{cyan}{17} & 7 & \textcolor{red}{23} \\
\textcolor{cyan}{15} & 1 & \textcolor{cyan}{16} & 3 & \textcolor{red}{12} \\
\textcolor{cyan}{21} & 9 & \textcolor{cyan}{18} & 6 & \textcolor{red}{24} \\
\textcolor{cyan}{13} & 2 & \textcolor{cyan}{15} & 4 & \textcolor{red}{11} \\
\textcolor{cyan}{22} & 8 & \textcolor{cyan}{19} & 5 & \textcolor{red}{25} \\
\end{bmatrix}
\begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array}
\begin{array}{cccc}
45 & 44 & 43 & 45 \\
45 & 44 & 43 & 45 \\
45 & 44 & 43 & 45 \\
45 & 44 & 43 & 45 \\
\end{array}
\]when there are lots of $45$ constructed (which further strengthen my belief that it's 45) with some pesky small $43$s which downs the global sum.
Knowing that there probably is lots more constructions than I initially realized, I searched more by reverting back to the first $47$ configuration, in which I tried some ideas such as setting cells $1 \rightarrow 25$, $3 \rightarrow 22$, $11 \rightarrow 23$, $13 \rightarrow 24$, but I discarded this since no way $24$ can be placed in the very middle. At this time, I still had faith that the row-column analysis still works, of which I considered the $5$ by $4$ $\textit{consecutive paired sums}$ across the first, second, third, fourth up to the fifth row and also first to fifth columns of my first $45$ configuration as following:
\[
\begin{tabular}{|c c c c|}
\hline
27 & 30 & 27 & 30 \\
\hline
17 & 15 & 17 & 15 \\
\hline
27 & 30 & 27 & 30 \\
\hline
17 & 15 & 17 & 15 \\
\hline
27 & 30 & 27 & 30 \\
\hline
\end{tabular}
\ \ \
\begin{tabular}{||c| c| c| c| c||}
33 & 11 & 34 & 10 & 35 \\
34 & 10 & 35 & 9 & 36 \\
33 & 11 & 34 & 10 & 35 \\
34 & 10 & 35 & 9 & 36 \\
\end{tabular}
\]both of which do not have any nice pattern to base our $z \geq 45$ proof.
The idea which almost "prompted" me to the real idea was the standard "consider the highest numbers" idea -- which I considered the $16$ highest from $10$ to $25$ and ignoring altogether the lower ones, but since this is a problem about overall sums (of which a number as small as $1$ can play a huge role in determining the answer is $44$ or $45$) to my dismay, again this will not work.
Scavenging through the possibilities I had not considered yet, I was very sure that the placements of $\{11,12,\ldots 25\}$ must either occupy the $1^{st},3^{rd}$ and $5^{th}$ rows, or $1^{st},3^{rd}$ and $5^{th}$ columns. Experimenting a bit more yields some kind of these configurations:
\[
\begin{bmatrix}
25 & \textcolor{red}{13} & 17 & \textcolor{red}{16} & 22 \\
& & \textcolor{blue}{10} & & \\
20 & \textcolor{red}{12} & 21 & \textcolor{red}{11} & 19 \\
& & \textcolor{blue}{9} & & \\
23 & \textcolor{red}{15} & 18 & \textcolor{red}{14} & 24 \\
\end{bmatrix}
\begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array}
\begin{array}{cccc}
38 & 40 & 43 & 38 \\
32 & 43 & 42 & 30 \\
32 & 42 & 41 & 30 \\
38 & 42 & 41 & 38 \\
\end{array}
\]where the big numbers are specifically thrown out to the first and fifth rows with $21$ in the middle to balance things out; or the second option:
\[
\begin{bmatrix}
25 & \textcolor{red}{11} & 19 & \textcolor{red}{14} & 22 \\
& \textcolor{cyan}{\leq 3} & \textcolor{blue}{9} & \textcolor{cyan}{\leq 3} & \\
18 & \textcolor{red}{16} & 17 & \textcolor{red}{15} & 21 \\
& \textcolor{cyan}{\leq 2} & \textcolor{blue}{10} & \textcolor{cyan}{\leq 3} & \\
23 & \textcolor{red}{13} & 20 & \textcolor{red}{12} & 24 \\
\end{bmatrix}
\begin{array}{c} \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \\ \mid \end{array}
\begin{array}{cccc}
36 & 39 & 42 & 36 \\
34 & 42 & 41 & 36 \\
34 & 43 & 42 & 36 \\
36 & 43 & 42 & 36 \\
\end{array}
\]where there is a balance of big and small numbers in each of the first, third and fifth rows. Obviously, we can't complete the two tables, as in the first tablethere are some very small $32$s in the middle rows, though the second is very close indeed! (The second $45$ configuration was obtained using a blueprint of the second pattern, there I switched the locations of pairs of numbers $(23,13)$ and $(22,14)$ in the corners to make room for the number $4$ to be placed.)
For me, this is the dead giveaway that the answer is indeed $45 - $ the after completing $\textcolor{green}{\textbf{\text{three}}}$ configurations, and noticing that the big 9 $\{17,18\ldots,25\}$ is variably/arbitrarily located in the fixed $9$ squares, and the small 4 $\{1,2,3,4\}$ is variably/arbitrarily located in the fixed $4$ squares, no matter how wild the configuration is. This puts a special emphasis on the second, fourth rows and the second, fourth columns as the placement of middle numbers $\{5,6,\ldots,16\}$, as they are always placed there, together with the small 4 $\{1,2,3,4\}$.
In other words, those special rows/columns needed to be singled out, or somehow to be counted twice. Since I thought that the nine big squares are nice, I considered arbitrary $9$ squares passing through the $big - 9$ squares to match the positioning of the $fourth \ column$ and $fourth \ rows$, and there lies the solution.
silouan
03.07.2021 17:11
The problem proposed by Demetres Christofides (Cyprus) and me
lazizbek42
24.12.2021 23:05
Balkan mo shortlist.