Apologies if I am violating any regulations, but I posted a solution in Greek here.

Demetres wrote: Apologies if I am violating any regulations, but I posted a solution in Greek here. I think in your solution, we can only guarantee the smaller rectangle's difference is $\frac{x+3}{4}$ , not $x+\frac{3}{4}$ .

liekkas wrote: Demetres wrote: Apologies if I am violating any regulations, but I posted a solution in Greek here. I think in your solution, we can only guarantee the smaller rectangle's difference is $\frac{x+3}{4}$ , not $x+\frac{3}{4}$ . You are absolutely right. I believe I have a different approach but I will need to think about it. By the way this is related to geometric discrepancy. It is know that if we have an $N \times N$ square with $N^2$ points inside, then there is always a rectangle with difference at least $C\log{N}$ for some consant $C$. See for example this book here and in particular Section 6.2.

In fact it's a K.Roth's result (Roth, K. F. "On Irregularities of Distribution." Mathematika 1, 73-79, 1954) applied for the $2$-dimensional case. The problem statement is equivalent to the following claim. Suppose we have a set $S$ of $N$ points in the unit square $Q$. For any point $x\in Q$ let $R_x$ be the rectangle which left-bottom corner is $(0,0)$ and its top-right point is $x$. Denote $$D(S,R_x):= |S\cap R_x|-N\cdot \text{ area }(R_x).$$It's called the discrepancy of set $S$ in the rectangle $R_x$ and measures how uniform $S$ is distributed. Let $D(S,Q)$ be the maximal discrepancy $|D(S,R_x)|$ when $x$ runs through $Q$. The Roth's result says: $$D(S,Q)\geq c\cdot (\log_2 N)^{1/2}.$$In the $d$-dimensional case, $d\geq 2$, the constant $1/2$ is replaced by $(d-1)/2$. One can see a short nice proof of it here (http://home.wlu.edu/~baczkowskid/talks/discrepancy.pdf), I suppose it's the Roth's proof. In fact the proof goes for the $L^2$ discrepancy, as the method uses it substantially. In our situation, by dilating the $n\times n, (n=10^{2019})$ square into the unit square, we get to the above situation with $N=n^2$. Unfortunately, we cannot see the official solution, at least for now being. As far as I know, the materials of St. Petersburg contest are not officially published.

dgrozev wrote: I suppose it's the Roth's proof. In fact the proof goes for the $L^2$ discrepancy, as the method uses it substantially. The book suggested by Demetres actually has the same pictorial illustrations as those provided in the powerpoint in post #7

Maybe, but that book costs money, whereas that presentation costs nothing, but has a full proof. Yes, it's the Roth's proof, see here: http://www.math.tifr.res.in/~publ/ln/tifr56.pdf

dgrozev wrote: Unfortunately, we cannot see the official solution, at least for now being. As far as I know, the materials of St. Petersburg contest are not officially published. I think they don't post the solutions in the official site , only the problems( which are posted there: http://www.pdmi.ras.ru/~olymp/current/problems.html )

$\textbf {Theorem (Schmidt’s lower bound for corners)}$. For any $n$-point set $P \subset [0,1]^2$ there is an axis-parallel rectangle $R$ with discrepancy $|D(P,R)| \ge c \log n$, for a suitable constant $c>0$.