Let \(n\) be a positive integer and consider an \(n\times n\) square grid. For \(1\le k\le n\), a python of length \(k\) is a snake that occupies \(k\) consecutive cells in a single row, and no other cells. Similarly, an anaconda of length \(k\) is a snake that occupies \(k\) consecutive cells in a single column, and no other cells. The grid contains at least one python or anaconda, and it satisfies the following properties: No cell is occupied by multiple snakes. If a cell in the grid is immediately to the left or immediately to the right of a python, then that cell must be occupied by an anaconda. If a cell in the grid is immediately to above or immediately below an anaconda, then that cell must be occupied by a python. Prove that the sum of the squares of the lengths of the snakes is at least \(n^2\). Proposed by Linus Tang
Problem
Source: ELMO Shortlist 2023 C4
Tags: Elmo, combinatorics, combinatorial geometry
30.06.2023 16:24
It sounds quite weird to calculate these squares, maybe we need to consider about pairs of cells. Anyway, can anyone pose a solution?
01.07.2023 17:03
02.07.2023 00:46
$k$ is not fixed.
10.11.2023 16:31
Here it is a possible approach. Maybe the implementation could be simplified somehow.
23.03.2024 16:28
BUMP for a nicer solution
22.06.2024 23:54
14.07.2024 11:58
I'm sorry, but I have diffuculty understanding any of the solution above. In Picture 1, I present a construction for $n=6$ where sum of the squares of the lengths is exactly $n^2$, and it is quite simple to generalize the construction to all even $n$. However, for Number1048576's solution, Number1048576 wrote: In any poisonous configuration the sum of the lengths of the hurt snakes touching each side is at least $2n$. If this is a key step in the proof process, I have no idea what to do next. For dgrozev's solution, if my understanding is correct, dgrozev wrote: We call a python bad if its both horizontal sides are propped by only one anaconda and no other snake or the frame of the big square touches them. The same goes for an anacoda. all the snakes in my construction are bad. So the following inequality (dgrozev says that it is for the second case "both $p$ and $a$ are bad") $$\Delta a\cdot\Delta p\leqslant \frac12 a^2+\frac12 p^2-S(p)\qquad (6)$$holds, but I don't think the next inequality $$\sum_{R\in\mathcal R}S(R)=\sum_{p,a}\Delta p\Delta a\leqslant\frac{1}{2}\sum_{a} \sum_{\Delta a\in a}\Delta a^2 + \frac{1}{2}\sum_{p} \sum_{\Delta p\in p}\Delta p^2- \sum_{p\text{ is bad}} S(p) -\sum_{a \text{ is bad}} S(a)$$holds. ($4\times6\not\leqslant2\left(\frac12\times2\times(2^2+3^2)\right)-4\times3$) Because $\sum_{p,a}\frac12 a^2+\frac12 p^2\leqslant\frac{1}{2}\sum_{a} \sum_{\Delta a\in a}\Delta a^2 + \frac{1}{2}\sum_{p} \sum_{\Delta p\in p}\Delta p^2$ isn't always correct. (However, I still believe that this method has great potential and can be moidified to a correct solution.) If my comprehension is wrong somewhere, please point it out, I would be grateful. (To make it worse, the .pdf file in the official website doesn't have a soltion for this problem. I don't know why.)
Attachments:

28.07.2024 06:32
Here's the badly LaTeX'd solution that I submitted to the longlist back in 2023.
Attachments:
Gridlocked_Snakes_Solution.pdf (224kb)