Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 13 / 1 / Solution

For the unheaded existence request, use the probabilistic method. Choose every value $f(x,y)$ independently and uniformly from $\{-1,1\}$. For a rectangle with $x\ne x^{\prime }$ and $y\ne y^{\prime }$, its four entries are distinct, so independence and the zero mean of each sign give expectation zero for their product. If $x=x^{\prime }$ or $y=y^{\prime }$, the product is identically one. The number of ordered rectangles in this union of diagonal cases isTherefore the random sign rectangle fourth moment has expectationSome sign function has $Q(f)$ at most this expectation. Applying the bound in part (a) to that same function gives the simultaneous choicesBoth constants tend to zero whenever both dimensions tend to infinity, without any assumption on their relative rates of growth.