April 2020 – A Point of View.

A Matching Problem.

Here is an interesting graph theory problem (maybe a folklore, thou I haven’t met it) given at a Cambridge mathematical tripos. The problem is not as hard as compared to graph theory problems given at IMO level competitions, but I present it here as an example of reducing a problem that couldn’t be well visualized to another one that can be better encompassed and thereby the probability of producing a solution increases.
Two solutions are presented. Both use Hall’s marriage theorem and both exploit essentially the same idea. The first one is the way I managed it, the second one – more elegant but more formal – is from a paper, presented to me.

Problem. Let $G = (V=X \cup Y, E(G))$ be a simple, bipartite graph without isolated vertices, such that for every edge $x\,y;x\in X, y \in Y,\, \deg(x) \geq \deg(y).$ Show that there exists a matching from $X$ to $Y$ .

So, we have to find a function (matching) $f : X\to Y$ such that $\forall x\in X, x\,f(x)$ is an edge and $f$ is injection. A predictable idea is to use Hall’s marriage theorem.

Solution 1. To check Hall’s condition, we take $A\subset X$ and want to show $|N(A)|\geq |A|$ where $N(A)\subset Y$ is the set of all vertices in $Y$ that have a neighbour in $A$ . Consider the bipartite subgraph $G'=(A, N(A))$ induced by $A$ and $N(A)$ . Clearly it also satisfy the problem condition, since the degree in $G'$ of any $a\in A$ is the same as in $G$ and the degree in $G'$ of any $b\in N(A)$ is less or equal to its degree in $G$ (it may be less if $b$ is connected to some vertex in $X$ outside $A$ ). Enumerate vertices in $A$ as $a_1,a_2,\dots,a_n, n=|A|$ and those in $N(A)$ as $b_1,b_2,\dots,b_m, m=|N(A)|$ . Consider the incidence $n\times m$ matrix of $G'$ , $c=(c_{ij}),i\in [1..n],j\in[1..m]$ , where $c_{ij}=1$ iff $a_i\,b_j$ is an edge in $G'$ , otherwise $c_{ij}=0$ . The matrix $c$ has the following two properties.

There is at least one $1$ ‘s in every row and every column.
For any $c_{ij}=1$ , the number of $1$ ‘s in the $i$ -th row is greater or equal to the number of $1$ ‘s in the $j$ -th column.

Indeed (1) means $G'$ has no isolated vertices and (2) is just another expression of the given condition. So, it boils down to prove $m\geq n$ for any binary $n\times m$ matrix $(c_{ij})$ that satisfies the above two properties.
Of course, till now we have zero progress, but we reduced the problem to another one which is more “obvious” (at least to me).
Since we seek to prove $m\geq n$ we may look for expressing $n$ and $m$ in terms of the matrix entries. For this reason tag to each entry $c_{ij}=1$ two numbers $x_{ij}, y_{ij}$ where $x_{ij}$ is the reciprocal of the number of $1$ ‘s in the $i$ -th row and $y_{ij}$ is the reciprocal of the number of $1$ ‘s of the $j$ -th column. In case $c_{ij}=0$ we set $x_{ij}=y_{ij}=0$ .
Note that $x_{ij}\leq y_{ij},\forall i,j$ by the condition (2) and $\sum_{i, j}x_{ij}=n, \sum_{i, j}y_{ij}=m$ . The result follows. $\blacksquare$

Solution 2. Again, to check Hall’s condition, we take $A\subset X$ and want to show $|N(A)|\geq |A|$ where $N(A)\subset Y$ is the set of all vertices in $Y$ that have a neighbour in $A$ . We have

$\displaystyle |A| =\sum_{x\in A}\quad \sum_{y\in Y, xy\in E}\frac{1}{\deg(x)}=\sum_{x\in A} \quad\sum_{y\in N(A), xy\in E}\frac{1}{\deg(x)}\leq$

$\displaystyle \leq \sum_{x\in A}\quad \sum_{y\in N(A), xy\in E}\frac{1}{\deg(y)}= \sum_{y\in N(A)} \quad\sum_{x\in A, xy\in E}\frac{1}{\deg(y)}\leq$

$\displaystyle \leq \sum_{y\in N(A)}\quad \sum_{x\in X, xy\in E}\frac{1}{\deg(y)}=N(A).$

Miklos Schweitzer, 2019, problem 8.

Miklos Schweitzer, 2019, problem 8. Let $f: \mathbb{R} \to \mathbb{R}$ be a measurable function such that $f(x+t) - f(x)$ is locally integrable for every $t$ as a function of $x$ . Prove that $f$ is locally integrable.

Solution. Let $D\subset \mathbb{R}$ be a closed interval with $m(D)\leq 1/2$ (hereafter $m(\cdot)$ is the Lebesgue measure). We’ll prove $\int_D |f(x)|\,dx<\infty$ . Seeking a contradiction, assume it is false. Let $D_+:=\{x\in D : f(x)\ge 0\}; D_-:=\{x\in D : f(x)< 0\}$ . Then, either $\int_{D_+} f(x)\,dx=+\infty$ or $\int_{D_-} f(x)\,dx=-\infty$ . WLOG, suppose $\int_{D_+} f(x)\,dx=+\infty$ .
The idea is to find a subset $S\subset D_+$ and an offset $t_0$ such that $\int_S (f(x+t_0)-f(x))\,dx=-\infty$ . It would contradict the given hypothesis. The set $S$ will be constructed as a disjoint union of measurable sets $\Delta_i':=\Delta_i\cap D_+ , i=1,2,\dots$ where $\Delta_i$ are small intervals and

$\displaystyle \int_{\Delta_i'} (f(x+t)-f(x))\,dx<-1\quad (1)$

We first choose $\Delta_i$ in appropriate way such that $(1)$ is true for any translation $t\in T$ except a small set of $t$ ‘s for which $(1)$ fails ( $T$ is appropriate set of translations). We take care the sum of those “exceptions” is not too much, hence there exists $t_0\in T$ for which $(1)$ holds for any $\Delta_i,i=1,2,\dots.$ The details follow.

Lemma. Let $f$ be a a non negative function with support on an interval $\Delta$ with $\int_{\Delta} f(x)\,dx= M>0$ . Let $A$ is a measurable subset of $I:=[0,1]$ with $m(A)\ge 1-\delta$ . Then

$\displaystyle \int_I \chi_A(x)f(x-t)\,dx \ge M/2 \quad (2)$

holds for all $t$ satisfying $(\Delta+t)\cap I\neq \emptyset$ except a set with measure less than $2(|\Delta|+\delta)$ .

Proof. Denote $T:=\{ t\in \mathbb{R}: (\Delta+t)\cap I\neq \emptyset\}$ . Then $|T|=1+|\Delta|$ . Assume $(2)$ does not hold on a subset of $T$ with measure $\varepsilon$ . We have

$\displaystyle \int_I\left( \int_T \chi_A (x)f(x-t)\,dt\right)\,dx =\int_I M\chi_A(x)\,dx>M(1-\delta)$

On the other hand the same integral on the RHS of the above inequality can be calculated as

$\displaystyle \int_T\left(\int_I\chi_A(x)f(x-t)\,dx\right)\,dt<\varepsilon M/2+(1+|\Delta|-\varepsilon)M$

It yields

$M(1-\delta)<\varepsilon M/2+(1+|\Delta|-\varepsilon)M$

It implies $\varepsilon <2(|\Delta|+\delta)$ . $\blacksquare$

Fix some $\delta>0$ . We can find $N>0$ such that

$m\left(A:=\{x\in I=[0,1]: f(x)\le N\}\right)>1-\delta\quad (3)$ .

Since $\displaystyle \int_{D_+}f(x)\,dx=+\infty$ , we can find as small interval $\Delta\subset D$ as we want with

$\displaystyle \int_{\Delta'} f(x)\,dx>2(N+1)$ , where $\Delta'=\Delta\cap D_+\quad (4)$ .

Let $T:=\{t\in\mathbb{R}: (\Delta+t)\cap I\neq \emptyset\}$ . Applying Lemma for $M=2(N+1)$ it follows

$\displaystyle \int_{\{x:x-t\in \Delta'\}} \chi_A(x)f(x-t)\,dx >N+1$

holds for all $t\in T$ except a set $E$ with $m(E)<2(|\Delta|+\delta)$ . Thus, for any $t\in T\setminus E$ we have

$\displaystyle \int_{\{x\in A:x-t\in \Delta'\}} f(x-t)-f(x)\,dx>N+1-N=1\quad (5)$

Denote $T':=\{t\in \mathbb{R}: D+t\subset I=[0,1]\}$ . Note that $T'\subset T$ and $m(T')\geq 1/2$ since $m(D)\le 1/2$ .
Now, let $\delta_i>0, i=1,2,\dots.$ Proceeding through $(3),(4),(5)$ we choose corresponding $\Delta_i$ (as small as we want) and obtain the set of exceptions $E_i$ outside of which $(5)$ holds and

$\displaystyle m(E_i)<2(\delta_i+|\Delta_i|)$

It can be reckoned $\Delta_i,i\in \mathbb{N}$ are mutually disjoint (it can be arranged that way). We choose $\delta_i, \Delta_i, i=1,2,\dots$ such that $\displaystyle \sum_{i=1}^{\infty}2(\delta_i+|\Delta_i|)<1/2$ . It follows there exists $t_0\in T'$ for which

$\displaystyle \int_{\{x\in A_i:x-t_0\in \Delta_i'\}} f(x-t_0)-f(x)\,dx>1\,,\,\forall i\in\mathbb{N}$

where $A_i\subset I$ are corresponding sets satisfying $(3)$ and $\Delta_i'=D_+\cap \Delta_i$ . Denote $\Delta_i'':= \{u\in \Delta_i' : u+t_0\in A_i\}$ . Then

$\displaystyle \int_{\Delta_i''} f(u+t_0)-f(u)\,du<-1$

Since $\Delta_i''$ are disjoint, we obtain

$\displaystyle \int_{S} f(u+t_0)-f(u)\,du=-\infty$

where $S:=\bigcup_{i=1}^{\infty}\Delta_i''.$ It means $f(x+t_0)-f(x)$ is not locally integrable, contradiction.

А Weaker Jensen’s Inequality, an Olympiad Approach.

Sometimes, we feel applying the Jensen’s inequality would yield a result, but unfortunately the function is not convex/concave on the given domain. Is it a reason to give up? This post illustrates how we can “approximate” the given function with another “better” one, which is convex/concave, and still obtain a Jensen’s type estimate, thou a weaker one. I will give two applications of the method – USAMO 2017, problem 6 and CGMO 2007, p3.

Suppose, we have a function $f(x), x\in [a,b]$ and want to estimate, say to find a lower bound for $\alpha_1f(x_1)+\alpha_2f(x_2)+\dots+\alpha_nf(x_n)$ where $x_i\in [a,b], \sum_{i=1}^n\alpha_i=1.$ Unfortunately, $f$ is not convex to apply Jensen’s inequality. But we can apply the following trick. Construct a function $g(x)$ which is convex in $[a,b]$ and $g(x)\leq f(x), \forall x\in[a,b]$ and then write

$\displaystyle \sum_{i=1}^n \alpha_if(x_i)\geq \sum_{i=1}^n \alpha_ig(x_i)\geq g\left(\sum_{i=1}^n \alpha_ix_i\right)\quad (1)$

Usually, we choose $g$ be a linear function because the second inequality in $(1)$ becomes an equality. The closer the function $g$ is to $f$ , the sharper estimate the inequality $(1)$ yields, thus $g$ should touch $f$ at as many points, as possible in the given interval, so it cannot be moved up anymore, see figure 1 .

In the applications that follow, we have to find the minimum value of $\sum_{i=1}^n \alpha_if(x_i)$ , where $f$ is a given “bad” function, $a\le x_i\le b$ and $\sum_{i=1}^n\alpha_i=1$ , but $\alpha_i$ may depend on $x_i, i=1,\dots,n$ . Choosing appropriate linear function $g(x)$ and applying $(1)$ , we get a lower bound which is $g\left(\sum_{i=1}^n \alpha_ix_i\right)$ . Since $g$ is linear, it boils down to find the minimum or maximum (depending on the sign of the slope of $g$ ) value of $\sum_{i=1}^n \alpha_ix_i$ , which is a much easier task. Assume, for those values of $x_i$ , the first inequality in $(1)$ is actually an equality. It happens when $x_i,i=1,\dots,n$ are exactly the points where $g$ touches $f$ . In that case we hit the jackpot, because those values of $x_i$ are exactly the values where $\sum_{i=1}^n \alpha_if(x_i)$ attains its minimum under the given conditions. Let us consider two Olympiad problems allowing the described approach.

CGMO 2007, Problem 3

Let $n\geq 3$ be an integer, and $x_1, x_2, \cdots, x_n$ be non-negative real numbers with $x_1 + x_2 + \cdots + x_n = 2$ . Determine the minimum value of

$\displaystyle A(x_1,x_2,\dots,x_n)=\frac{x_1}{x_2^2 + 1}+ \frac{x_2}{x^2_3 + 1}+ \cdots + \frac{x_n}{x^2_1 + 1}$

Solution. let us denote $\displaystyle f(x)=\frac{1}{x^2+1}$ and $\alpha_i=x_i/2,i=1,2,\dots,n$ . Then $\sum_{i=1}^n \alpha_i=1, 0\le x_i\le 2$ and we have to find the minimum value of

$A=\displaystyle 2\sum_{i=1}^n \alpha_if(x_{i+1})$

where $x_{n+1}=x_1$ . Let $\displaystyle g(x):=1-\frac{x}{2}$ , see figure 2.

Thus, $g$ is a linear function, $f(x)\geq g(x), \forall x\in[0,2]$ and it can be easily checked $g$ touches $f$ at the points $x=0,x=1$ . Using $(1)$ we get

$\displaystyle \sum_{i=1}^n \alpha_if(x_{i+1}) \ge \sum_{i=1}^n \alpha_ig(x_{i+1})=g\left(\sum_{i=1}^n \alpha_ix_{i+1} \right)$

Since $g$ is decreasing, $\displaystyle g\left(\sum_{i=1}^n \alpha_ix_{i+1} \right)\ge g\left(\max \sum_{i=1}^n \alpha_ix_{i+1}\right)$ . But

$\displaystyle \sum_{i=1}^n \alpha_ix_{i+1}=\frac{1}{2}\sum_{i=1}^n x_ix_{i+1}\leq \frac{1}{2}\frac{(x_1+x_2+\dots+x_n)^2}{4}=\frac{1}{2}$

The equality is attained when all $x_i$ are zeroes except $x_k=x_{k+1}=1$ for some $k$ . Hence, it yields

$\displaystyle \sum_{i=1}^n \alpha_if(x_{i+1}) \ge g(1/2)=\frac{3}{4}\quad (2)$

Note that for $x_k=x_{k+1}=1$ , and all others $x_i$ – zero, the inequality (2) actually is equality, since $f(0)=g(0),f(1)=g(1)$ . Thus, $3/4$ is indeed the minimum value of the LHS of $(2)$ . Finally, the minimum value of $A=2 (\text{ the LHS of (2) })$ is $3/2$ . $\blacksquare$

USAMO 2017, problem 6

Find the minimum possible value of

$\displaystyle A=\frac{x_1}{x_2^3+4}+\frac{x_2}{x_3^3+4}+\frac{x_3}{x_4^3+4}+\frac{x_4}{x_1^3+4}$

given that $x_1, x_2, x_3, x_4$ are non-negative real numbers such that $x_1+x_2+x_3+x_4=4$ .

Solution. Let $\displaystyle f(x)=\frac{1}{x^3+4},0\le x\le 4$ and $\alpha_i:=x_i/4,i=1,2,3,4$ , so $\sum \alpha_i=1$ . We have to find the minimum value of

$\displaystyle A=4\sum_{i=1}^4\alpha_i f(x_{i+1})\,;\, (x_5=x_1)$

Let us consider the linear function $g(x)$ the passes through the point $A(0,f(0))$ and is tangent to $f(x)$ , see figure 3.

One may calculate $\displaystyle g(x)=\frac{1}{4}-\frac{x}{12}$ , it touches $f$ at the point $B(2,1/12)$ and also passes through $(0,3)$ . Thus, we have

$\displaystyle \sum_{i=1}^4\alpha_i f(x_{i+1})\ge \sum_{i=1}^4\alpha_i g(x_{i+1})=g\left(\sum_{i=1}^4 \alpha_ix_{i+1}\right)\quad (3)$

The RHS of $(3)$ attains its minimum when $\sum_{i=1}^4 \alpha_i x_{i+1}$ attains its maximum, since $g$ is decreasing.

$\displaystyle \sum_{i=1}^4\alpha_i x_{i+1}=\frac{1}{4}\sum_{i=1}^4 x_ix_{i+1}\le \frac{1}{4}\frac{(x_1+\dots+x_4)^2}{4}=1\quad (4)$

Thus, we have

$\displaystyle \sum_{i=1}^4\alpha_i f(x_{i+1})\ge g(1)=\frac{1}{6}\quad (5)$

The equality in $(4)$ is attained when $x_k=x_{k+1}=2$ for some $k\in[1..4]$ and the two others $x_i$ ‘s are zeroes. But exactly in this case, we also have equality in $(3)$ , since $f(0)=g(0)$ and $f(2)=g(2)$ . It means $1/6$ is indeed the minimum value of the LHS of $(5)$ . Finally, the minimum value of $A$ is $2/3$ . $\blacksquare$

References.
[1] CGMO 2007, problem 3
[2] USAMO 2017, problem 6

Set of points with mutual integer distances.

It’s known a set with infinitely many points in the plane, with all mutual distances integers, can exist only if all points lie on a straight line (Erdos – Anning theorem). It’s also known, there exists a finite set with arbitrary many points with the same property, not lying on the same line.
Here we consider some additional properties, such finite set of points has, illustrated with three similar problems of math competitions. One – given at Putnam 1993, the other – at a Bulgarian competition, and the third one – at Miklos Schweitzer 2018. We start with the Putnam problem, since that idea is used in the other two problems.

Putnam 1993, Problem B5. [1] Show there do not exist four points in the Euclidean plane such that the pairwise distances between the points are all odd integers.

Solution. We use a formula for the volume of a tetrahedron knowing the lengths of its edges:

$\displaystyle V=\frac{1}{12}\sqrt{\sum_1 a^2b^2c^2 - \sum_2 a^2b^2c^2 - \sum_3 a^4b^2 }$

Here $a,b,c$ denote the lengths of some combinations of edges, $\displaystyle \sum_1$ is taken over the $12$ cases where $a, b, c$ form an open path of length $3$ . $\displaystyle \sum_2$ is taken over the $4$ cases where $a, b, c$ form the sides of a face. $\displaystyle \sum_3$ is taken over the $6$ cases where $a, b$ are opposite sides (without a vertex in common).

In our case the volume of the tetrahedron is $0$ , since it lies in a plane. Hence

$\displaystyle \sum_1 a^2b^2c^2 - \sum_2 a^2b^2c^2 - \sum_3 a^4b^2 =0\quad (1)$

It remains some simple calculations $\mod 4$ . If all edges of a planar tetrahedron are odd integers, then the LHS of $(1)$ equals $2\, \mod 4$ , which is impossible. $\blacksquare$

Miklos Schweitzer 2018, Problem 4. [2] Let $P$ be a finite set of points in the plane. Assume that the distance between any two points is an integer. Prove that $P$ can be colored by three colors such that the distance between any two points of the same color is an even number.

Solution. Consider a graph $G$ with vertices $V\equiv P$ . Two vertices $p_1,p_2$ are connected if and only if the distance between them is odd. We wish to show the vertices could be colored by three colors. First, to see $G$ does not contain $K_4$ (a complete graph on $4$ vertices. Indeed, it’s exactly the previous Putnam problem, which says no four points on a plane can have all mutual distances being odd integers.

Suppose now, there is a triangle in $G$ , say all distances between $P_1,P_2,P_3\in P$ are odd. We color them by colors $1,2,3$ respectively. Consider any other point $Q\in P$ and let see the possible parities of $QP_1, QP_2, QP_3$ . We’ve established they are not all odd. It’s also impossible all three of them to be even. Indeed, assuming that, we obtain that the LHS of $(1)$ is odd, which is impossible.
It’s also impossible two of those distances to be even and the remaining one – odd. Indeed, in that case again from $(1)$ we get the LHS is odd, a contradiction.
The only possibility is two of those distances to be odd and the remaining one, say $QP_i, i\in \{1,2,3\}$ – even. Then, we color $Q$ by the color $i$ .
In that way, we color all points in $P$ . It’s easy to prove the coloring is appropriate, since otherwise we get $4$ points, all connected.

Let us consider now the case there is no triangle in $G$ . In this case we claim there is no odd cycle in $G$ . For the sake of contradiction, let there is one $P_1,P_2,\dots, P_{2n+1}$ . Then, $P_1$ have to be connected with $P_4$ . Indeed, otherwise by $(1)$ , the LHS would be odd, impossible. Hence, $P_1P_4$ is an edge. Analogously, $P_1P_6, P_1P_8,\dots,P_1P_{2n}$ are also edges and finally we get a triangle $P_1P_{2n}P_{2n+1}$ , but we’ve assume there is no triangle in $G$ , a contradiction.
So, in this case the graph $G$ is a bipartite graph and can be colored by $2$ colors. $\blacksquare$

Bulgarian Spring Math Competition,2000, P 10.3. [3] $n\geq 4$ points lie in a plane. The distance between any two of them is integer. Prove at least $1/6$ of the distances between the points are multiple of $3$ .

Solution. Take some $4$ points. We prove there is a distance among them multiple of $3$ . Assume on the contrary all 6 distances are not multiple of $3$ . We use again $(1)$ . Since $a^2\equiv 1\pmod 3$ for any edge of the corresponding tetrahedron, we get $\sum_1$ and $\sum_3$ are multiple of 3 (number of terms in $\sum_1$ is 12 and in $\sum_3$ – 6). We also obtain $\sum_2\equiv 1\pmod 3$ which contradicts to $(1)$ .

Thus, for any 4 points, there is a distance among them multiple of 3. In all possible combinations $\binom{n}{4}$ any edge can be counted at most $\binom{n-2}{2}$ times. It means the number of distances multiple of 3 is at least

$\displaystyle \frac{\binom{n}{4}}{\binom{n-2}{2}}=\frac{n(n-1)}{12}$

Since all possible distances are $\frac{n(n-1)}{2}$ , the result follows. $\blacksquare$

Some comments on the presented problems. The official solutions of the last one uses cosine formula to prove there is a distance multiple of 3 among any 4 points, say $A,B,C,D$ . We apply cosine formula for the triangles $\triangle ABC, \triangle ACD, \triangle ABD$ , then use $\angle BAD=\angle BAC+\angle DAC$ and play with it to get a contradiction. Another approach is presented in [3], see post #5. I like it, one does not need to know some fancy formulas. It can be also applied on the other two problems. The Miklos Schweitzer’s one is the hardest presented problem, since those mod 2 arguments are applied many times.

References.
[1] Putnam 1993, Problem B5.
[2] Miklos Schweitzer 2018, Problem 4.
[3] Bulgarian Spring Math Competition, 2000, Problem 10.3/11.3.

3-tuples and an Inequality. A China TST problem.

I have recently seen in AoPS [1] a problem from a China TST, which was still partly unsolved, or at least not in a satisfactory enough way. I tried it, but also am not satisfied with the solution following. The problem asks for the minimal $n$ for which a certain property holds. That property involves an inequality, but the interesting part is it can be interpreted in a pure combinatorial way which leads to a curious problem.
Suppose two sets $S,T$ of 3D lattice points are given inside the lattice $[1..n]^3$ . It is known the projections of $S$ and $T$ on each of the planes $Oxy, Oxz, Oyz$ do not intersect. What condition $|S|$ and $|T|$ should satisfy?
I don’t know. In the 2D case it easily follows $\sqrt{S}+\sqrt{T}\leq n$ which is sharp. So, any ideas would be appreciated.

Problem (2018 China TST 4, Problem 6). Suppose $a_i, b_i, c_i, i=1,2,\cdots ,n$ , are $3n$ real numbers in the interval $\left [ 0,1 \right ]$ . Define

$S=\left \{ \left ( i,j,k \right ) |\, a_i+b_j+c_k<1 \right \}, \, T=\left \{ \left ( i,j,k \right ) |\, a_i+b_j+c_k>2 \right \}$

It is known that $\left | S \right |\ge 2018,\, \left | T \right |\ge 2018.$ Find the minimal possible value of $n$ .

Solution. Interpret $S$ and $T$ as sets of 3D lattice points inside a cube $[1..n]^3$ . The only fact that matters in the lower bound estimate for $n$ is the following property of the sets $S,T$ .

Property 1. There do not exist $P\in S, Q\in T$ that lie on the same line parallel to one of the axes $Ox, Oy$ or $Oz$ . In other words, it means the projections of $S$ and $T$ on each of the planes $Oxy, Oxz,Oyz$ do not intersect.

Proof. Assume WLOG $P,Q$ lie on a line parallel to $Oz$ . It means $P=(i,j,k_1), Q=(i,j,k_2)$ or $a_i+a_j+a_{k_1}<1$ and $a_i+a_j+a_{k_2}>2$ . But this is impossible since $|a_{k_1}-a_{k_2}|\leq 1.$ $\square$

The plan is first to find a lower bound of $n$ using only the property 1. The approach below is not elegant, so any comment or other ideas are welcomed.

Let us first consider the two dimensional analogous problem. It is an easier one and I’ll explain why. Let $S,T$ be sets of lattice points in a $n\times n$ lattice and $S_x,S_y, T_x,T_y$ be the sets of their projections on the axes $Ox,Oy$ correspondingly. Clearly, we have $S_x\cap T_x=\emptyset\,, S_y\cap T_y=\emptyset$ . This is the main difference between two and three dimensional cases (for example $(1,2,3)$ and $(1,3,4)$ in 3D have the same first coordinate but their projections on $Oxy,Oxz,Oyz$ are distinct). Back to 2D, it gives us $|S_x|+|T_x|\le n, |S_y|+|T_y|\leq n$ which implies

$\sqrt{|S|}+\sqrt{|T|}\leq n\,\,\,\,\,\,\,\,\,\, (1)$

Let’s now handle the 3D case. We project $S$ and $T$ on $Oxy$ and $S_0,T_0$ be their projections. Since they do not intersect, $|S_0|+|T_0|\leq n^2.$ We denote by $S_i,T_i$ the intersections of the planes $z=i, i=1,2,\dots,n$ with $S$ and $T$ respectively. Thus, using $(1)$ , we get the conditions

$\displaystyle \sqrt{|S_i|}+\sqrt{|T_i|}\leq n\,;\, |S_i|\leq |S_0|, |T_i|\leq |T_0|$

$\displaystyle \sum_{i=1}^n |S_i|\geq 2018\,;\,\sum_{i=1}^n |T_i|\geq 2018$

Denoting $s_i:=\sqrt{|S_i|},t_i:=\sqrt{|T_i|}, i=0,1,\dots,n$ it yields

$\displaystyle s_i+t_i\leq n\,;\, s_i\leq s_0, t_i\leq t_0\,,\,i=1,2,\dots,n \,\,\,\,\,\,\,\,\,\,(2)$

$\displaystyle \sum_{i=1}^n s_i^2\geq 2018\,;\,\sum_{i=1}^n t_i^2\geq 2018\,\,\,\,\,\,\,\,\,\,(3)$

Now, we’ll prove for $n=19$ there is no way $(2)$ and $(3)$ to hold for any $s_0,t_0$ with $s_0^2+t_0^2=19^2$ . Take some $s_i,s_j,t_i,t_j$ . If any of those numbers is not on the edge of its values as required in $(2)$ , we can transform them into $(s_i+\Delta, s_j-\Delta, t_i-\Delta, t_j+\Delta)$ for any small $\Delta$ . The new values also satisfy $(2),(3)$ . It means for all pairs $(s_i,t_j)$ except at most one, either $s_i=s_0, t_i=19-s_0$ or $t_j=t_0, s_j=19-t_0.$ A clumsy calculation with these values shows it’s impossible $(2),(3)$ to hold simultaneously for $n\leq 19$ , thus $n\geq 20$ .