Problem

Source: ELMO Shortlist 2023 C4

Tags: Elmo, combinatorics, combinatorial geometry



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