A marble is placed on each $33$ unit square of a $10*10$ chessboard. After that, the number of marbles in the same row or column with that square is written on each of the remaining empty unit squares. What is the maximum sum of the numbers written on the board?
Problem
Source: Turkey JBMO TST 2023 Day 2 P2
Tags: Chessboard, combinatorics
30.04.2023 19:58
Answer is 438 i will ad solution later
01.05.2023 00:15
We will prove that the answer to the problem is $438$. Let $x_i$ and $y_i$ be the number of marbles in the $i-$ row and column of the board, respectively. Note that $\displaystyle \sum_{i=1}^{10} x_i=\sum_{i=1}^{10} y_i=10$. The total sum of the numbers written on the board is $A=\sum_{i=1}^{10} (x_i(10-x_i)+y_i(10-y_i))$. We have the following key Claim: Claim: $\sum_{i=1}^{10} x_i^2 \geq 111$ and $\sum_{i=1}^{10} y_i^2 \geq 111$. Proof: We will only prove the first inequality. By Cauchy Schwarz, $\displaystyle \sum_{i=1}^{10} x_i^2 \geq \dfrac{(\sum_{i=1}^{10} x_i)^2}{10}=108.5,$ and so the sum is $\geq 109$. By $\pmod 2$ reasons, it is odd. Hence, we only need to dispose of the case it is equal to $109$. Assume that it is. Then, again by Cauchy Schwarz, $9(109-x_{10}^2)=9(x_1^2+\ldots+x_9^2) \geq (x_1+\ldots+x_9)^2=(33-x_{10})^2,$ and so we easily infer that $x_{10} \in [3,\dfrac{18}{5}]$, that is $x_10=3$. Similarly $x_i=3$ for all $i$, which is an obvious contradiction $\blacksquare$ Now, to the problem, from our Claim we have that $\displaystyle A=660-\sum_{i=1}^{10} x_i^2-\sum_{i=1}^{10} y_i^2 \leq 660-111-111=438,$ hence we have established the upper bound. Now, for the construction, denote a marble with $\times$ and an empty square with $-$. Fill in the board as follows: $\begin{bmatrix} \times & - & - & - & - & - & - & - & \times & \times \\ \times & \times & - & - & - & - & - & - & \times & - \\ \times & \times & \times & - & - & - & - & - & - & - \\ - & \times & \times & \times & - & - & - & \times & - & - \\ - & - & \times & \times & \times & - & - & - & - & - \\ - & - & - & \times & \times & \times & - & - & - & - \\ - & - & - & - & \times & \times & \times & - & - & - \\ - & - & - & - & - & \times & \times & \times & - & \times \\ - & - & - & - & - & - & \times & \times & \times & \times \\ - & - & - & - & - & - & - & \times & \times & \times \\ \end{bmatrix}$ It is easy to verify that in this case, $A=438$, and so we are done.
01.05.2023 00:17
imo i feel like this was harder than amo p6
17.04.2024 15:32
Answer: $438$. Example: $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline X&X&X&&&&&& \\\hline X&X&X&&&&&& \\\hline X&X&X&&&&&& \\\hline &&&X&X&X&&&\\\hline &&&X&X&X&&&\\\hline &&&X&X&X&&&\\\hline &&&&&&X&X&X&X \\\hline &&&&&&X&X&X&X\\\hline &&&&&&X&X&X&X \\\hline &&&&&&X&X&X& \\\hline \end{array} $$Proof: Construct the bipartite graph where $R_1,...,R_{10}$ are the rows and $C_1,C_2,...,C_{10}$ are the columns. There are $33$ edges thus $\sum{deg R_i}+\sum{deg C_i}=66$ Let $S$ be the sum of the numbers on the table. Every edge, whose vertices are $A$ and $B$, increases the sum $deg A(10-deg A)+deg B(10-deg B)$. \[S=\sum{degR_i(10-deg R_i)+deg C_i(10-deg C_i)}=10(\sum{deg R_i+deg C_i})-(\sum{deg R_i^2+deg C_i^2})\]\[=660-(\sum{deg R_i^2+deg C_i^2})\]Let $f=\sum{deg R_i^2}$ Claim: $f_{min}=(a_1,a_2,...,a_{10})$ has no $2$ elements whose difference is bigger than $1$. Proof: Assume that there are $2$ elements $a,a+k$. \[(a+1)^2+(a+k-1)^2=a^2+2+k^2+2k(a-1)<a^2+(a+k+1)^2\]This contradicts with our $f_{min}$ assumption since $f_{min}=f(a_1,...,a_i,...,a_j,...,a_{10})<f(a_1,...,a_i+1,...,a_j-1,...,a_{10})$ where $a_i<a_j$. Claim: $f_{min}\geq 111$. Proof: Assume that $f_{min}\leq 110$. Let elements of $f_{min}$ be $x$ times $k$ and $10-x$ times $k+1$. We have $10+10k-x=xk+(10-x)(k+1)=33\iff 10k-x=23\implies k\geq 3$. $xk^2+(10-x)(k+1)^2\leq 110$ \[110\geq xk^2+(10-x)(k^2+2k+1)=10(k+1)^2-2xk-x\]\[110\geq 10k^2+(20-2x)k+(10-x)=10k^2+(10-x)(2k+1)\geq 10k^2\implies 3\geq k\]Hence $k=3$ and $x=7$ which gives a contradiction. So \[S=660-\sum{deg R_i^2}-\sum{deg C_i^2}\leq 660-2f_{min}\leq 660-222=438\]As desired.$\blacksquare$