There is a $8*8$ board and the numbers $1,2,3,4,...,63,64$. In all the unit squares of the board, these numbers are places such that only $1$ numbers goes to only one unit square. Prove that there is atleast $4$ $2*2$ squares such that the sum of the numbers in $2*2$ is greater than $100$.
Problem
Source: Azerbaijan 2022 Junior National Olympiad
Tags: combinatorics, Junior, Azerbaijan, Bound
14.05.2022 14:07
This question was the most interesting one in the contest, I will show my full solution soon
14.05.2022 14:30
Suposse thet there is at most $3$ this means that there are $13$ squeares $2*2$ with some at most $99$ but $1+2+3+4+....+52=26*53>26*50=1300>1287=13*99$ contradiction
14.05.2022 14:31
P2nisic wrote: Suposse thet there is at most $3$ this means that there are $13$ squeares $2*2$ with some at most $99$ but $1+2+3+4+....+52=26*53>26*50=1300>1287=13*99$ contradiction nevermind, you are right, my bad, and my idea was similar too, the different thing from yours was I assumed there were no such 2x2 squares, and after bounding, I did bash the cases
14.05.2022 15:28
18.05.2022 15:29
Iora wrote: There is a $8*8$ board and the numbers $1,2,3,4,...,63,64$. In all the unit squares of the board, these numbers are places such that only $1$ numbers goes to only one unit square. Prove that there is atleast $4$ $2*2$ squares such that the sum of the numbers in $2*2$ is greater than $100$. Divide the board to 16 2*2 squares that are not intersecting.Call the sum of the numbers on the squares c1≤c2≤c3≤.....≤c15≤c16 by WLOG.Assume that c1≤c2≤....≤c13<100.Then c1+c2+...+c13<1300.But summing the minimal 52 numbers from 1 to 64 we get 26*53=1378>1300.So 100≤c13≤c14≤c15≤c16 And this was wanted in the question
06.06.2023 12:51
Wow we didn't need to overlap any 2x2 squares Divide the $8 \times 8$ square into 16 $2 \times 2$ squares. Suppose only 3 squares have sum more than 100. 13 squares thus, have sums of 100 or less. However, the lowest possible sum from 52 integers is $1+2+\dots+52=1378>13 \times 100$, thus at least 1 more square has a sum of more than 100 and at least 4 squares have a sum of more than 100
31.07.2023 17:28
This was not that hard. Just we have 16 non overlapping $2\times 2$ squares, we will present proof by contridiction, if only 3 squares have sum more than 100, then the lowest possible sum is $1+2+3...+52=1378$, which is greater than $13\cdot 100$, hence, proved.
31.07.2023 17:40
If not then the sum of the board is at most$$13\cdot 100+12\cdot 64<\frac{64\cdot 65}{2},$$a contradiction.
21.04.2024 10:52
Idk if this solution is true but I think it's correct. Let's claim that it's possible to make every 2x2 square has sum of numbers inside it less than or equal to 100. It's obvious that sum of every number on the board is $\frac{64 \cdot 65}{2} = 2080$. Let's look at this 8x8 board as a 4x4 board made of 2x2 squares. Maximum sum of a 2x2 square is 100. Hence, maximum sum of the board is $4 \cdot 4 \cdot 100 = 1600$. Which is not possible because the sum is supposes to be $2080$.
21.04.2024 12:23
Extend this question to $n \times n$ board.
02.11.2024 14:38
If there are $<4$ squares with sum greater than 100 then there are $13>$ squares with a sum with at most 99.So; $13\times 99+3\times (61+62+63+64)=2037<\frac{64\times 65}{2}$ this contradiction completes the proof