This question is from an old Russian contest:
The unit square $ABCD$ is divided into $10^{12}$ smaller squares (not necessarily equal). Prove that the sum of the perimeters of all the smaller squares intersecting the main diagonal $AC$ is not greater than 1500.
It is possible to divide $ABCD$ in a way such that all squares intersect the main diagonal in at least one point. To do this divide $ABCD$ into four equal smaller squares. A 'diagonal' square is one whose main diagonal belongs to $AC$.
Then divide each of the two diagonal squares into four smaller equal squares. The other two squares that are not 'diagonal' are let unchanged. Repeat this subdivision of diagonal squares into four smaller squares until we have $10^{12}$ squares.
I think that the process above maximize the sum of the perimeters asked, however I don't know how to prove this.
Does anyone know how to proceed?
As I'm re-reading this it's a bit graceless, but here goes:
I think that we have to use your "diagonal" squares exclusively can be taken as given--it's all but obvious that cutting any off-diagonal squares is strictly dominated by cutting an on-diagonal square, because doing so a) adds nothing to the relevant perimeter and b) moves us closer to the constraint on total squares.
This question, then, is about choosing among all partitions of diagonal squares and showing that no arrangement of $10^{12}$ squares can exceed the stated total perimeter.
Let's start from this:
Suppose we're at a given partition of the square into sub-squares $S_1,\ldots,S_k$, which have sides $s_1,\ldots,s_k$, respectively. Then the total perimeter at this stage is $4\sum_j s_j$.
Proceeding, we can only crack one of the $k$ squares, say $l$, into 4 sub-squares, each of which will have side $\frac{s_l}{2}$. Thus the perimeter after this will become $4\sum_j s_j+4s_l$.
Thus the total perimeter's increase each time we add 3 squares is bounded by how large we can make $s_l$. (also, as a sanity check, note that since we start with 1 square and add 3 each time, we must have $10^{12} \equiv 1 \mod 3$, which is true).
How large the maximal $s_l$ can be is decreasing logarithmically. To see this, let's start from the beginning and change notation slightly; now we'll use $S^n_i$ to denote the $i$th square of side length $2^{-n}$ in our partition. So our initial square is $S^0_1$ and it can only be split at the second step into $S^1_1,S^1_2,S^1_3,S^1_4$.
Here, it is obvious that the maximal $s_l$ is $\frac{1}{2}$ because all squares are the same, but it's key to notice that in the next step, we'll have a choice between $s=\frac{1}{2}$ and $s=\frac{1}{4}$; $s=\frac{1}{2}$ will be again be maximal, but as subdividing any more side-$\frac{1}{2}$ squares would create off-diagonal squares, the next $s_l$ must be $\frac{1}{4}$.
Now we've got $S^1_{1:2}$ and $S^2_{1:8}$. Using similar logic, we can see that only half of these can be broken into on-diagonal squares, so that we'll have $s_l=\frac{1}{4}$ four times. Continuing, we'll have $s_l=\frac{1}{8}$ eight times, and so on.
Thus, the total perimeter after $M$ optimal breaks is: $4 + 4\sum_{m=1}^M s_l^m$, where ${s_l^m}={\frac{1}{2},\frac{1}{2},\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{8},\frac{1}{8},\frac{1}{8},\ldots}$
There are $10^{12}$ squares after $\frac{10^{12}-1}{3}$ breaks. So the maximal total perimeter is:
$4+4(\frac{1}{2}+\frac{1}{2})+4(\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4})+4(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8})+\cdots$
$=4+4+4+4+\cdots$
Since $\log_2((10^{12}-1)/3+1)+1\approx 43$, the perimeter is less than 4*43=172.