Each field of the table $(mn + 1) \times (mn + 1)$ contains a real number from the interval $[0, 1]$. The sum the numbers in each square section of the table with dimensions $n x n$ is equal to $n$. Determine how big it can be sum of all numbers in the table.
Problem
Source: Czech-Polish-Slovak Junior Match 2017, individual p5 CPSJ
Tags: combinatorics
24.08.2020 22:01
Bump!!!!!!!!!!
06.03.2022 04:14
Nice problem! Any solution?
06.03.2022 16:29
Answer. $\boxed{(mn+1)(m+1)}$. For the construction, simply fill every $kn+1$-th row with $1$'s, where $0\leq k\leq m$. To show maximality, let us look at all squares on the first row and column, we want to maximize the sum in this group. Now let us consider sets of squares \begin{align*} A_{j,k}&= \{(jn,nk-(n-1)),\ldots,(jn,nk-1),(jn,nk)\} & \text{for }0<k\leq m, 0\leq j\leq m,\\ B_{k,j}&= \{(nk-(n-1),jn),\ldots,(nk-1,jn),(nk,jn)\}& \text{for }0<k\leq m, 0\leq j\leq m. \end{align*}Let $x$ be the number in $(0,0)$. Let $\sigma(X)$ denote the sum of squares in set $X$. Enough for defining things, simply observe that $\sigma(A_{j,k})+\sigma(B_{k,j})\leq n+1$ for every $0<k\leq m, 0\leq j\leq m$. Thus, $$x+\sum_{1}^{m}\sigma(A_{0,k})+\sum_{1}^{m}\sigma(B_{k,0})\leq 1+m(n+1)=(mn+1)(m+1)-m^2n,$$as desired.
06.03.2022 16:34
Ok, It was for juniors after all. The answer is $(m+1)(mn+1)$ and can be attained putting $1$'s in the rows $1,n+1,2n+1,\dots, mn+1$ and $0$'s elsewhere. It remains to prove that it's impossible to get greater sum. The picture for the case $m=2,n=2$ is below. The sum of numbers on each of the colored regions cannot exceed $n=2$. Even if we put $1$'s on the cells not covered (which number is $m+1=3$), the entire sum will be at most $m(m+1)\cdot n+m+1=15$.
06.03.2022 16:44
dgrozev wrote: Ok, It was for juniors after all. The answer is $(m+1)(mn+1)$ and can be attained putting $1$'s in the rows $1,n+1,2n+1,\dots, mn+1$ and $0$'s elsewhere. It remains to prove that it's impossible to get greater sum. The picture for the case $m=2,n=2$ is below. The sum of numbers on each of the colored regions cannot exceed $n=2$. Even if we put $1$'s on the cells not covered (which number is $m+1=3$), the entire sum will be at most $m(m+1)\cdot n+m+1=15$. Sry, I do not understand your solution, wanna elaborate since you claim this was juniors after all ?
08.03.2022 17:03
@above: I didn't want to insult anyone claiming it's for juniors. It was just a junior competition - see the source! My argument is simple. Partition the $(mn+1)\times (mn+1)$ table into $m(m+1)$ regions, each one a subset of some $n\times n$ square, and $m+1$ additional unit squares. We are done if it's possible. To make a partitioning like that, we can be guided by a candidate configuration for attained maximum (as in the figure). The number of $1$'s in every region should be exactly $n$. There should remain $m+1$ uncovered unit squares in which is written $1$. This is just a guidance, that makes it easier for us. A note on your solution. It's fine, but an argument like that can be carried out only in case the sum of the numbers in each $n\times n$ table is exactly $n$. You cannot implement the same argument if that sum is at most $n$. While the idea of partitioning the board could be implement in either case.