Let $M_n(\mathbb{R})$ denote the vector space of matrices of size $n$ with real coefficients.
If $M$ is a matrix, let $s(M)$ denote the sum of its elements.
We define the "cut norm" of a matrix $A$ in $M_n(\mathbb{R})$ as
$||A||^*=\frac{1}{n^2}\max_{\text{submatrices M of A}} |s(M)| $
It's trivial to verify that this is a norm.
Also recall that a submatrix $M$ of $A$ is a matrix obtained by deleting some set of columns and some set of rows from $A$.
The goal is to show that there is a sequence of matrices $\{A_n\}_{n \in \mathbb{N}}$ such that $A_n$ is matrix in $M_n(\mathbb{R})$ with its coefficients in the set $\{-1,+1\}$, and such that $\lim_{n \to \infty}||A_n||^*=0$. (i.e there exist large matrices whose cut norm is arbitrarily small).
Edit: To avoid this question being closed, let me say that I already have solved this problem using
probabilistic methods
In general, I only post problems on MSE for which I already know a solution, so that others can provide different solutions.
