Nice problem. Call a lattice point set $S$ semi-convex if when $P, Q \in S$ and $\overline{PQ}$ is parallel to an axis, then all lattice points on $\overline{PQ}$ belong to $S$. The main idea of the solution is to repeatedly project onto lines and planes; this theme will recur throughout the solution. Lemma (2D variant). Let $S$ be a semi-convex subset of $\{1, \dots, n\}^2$ of size $2n - 1 + k$. Then there are at least $k$ unit squares in $S$. Proof. The idea is to project onto the $x$-axis. Suppose $S$ has $a_i$ points on line $y = i$; then they must be contiguous due to semi-convexity, forming a segment of length $\ge a_i - 1$. (This is valid for $a_i = 0$ as well.) Then all $n$ lines $y = i$, in total, form \[\ge (a_1 - 1) + \dots + (a_n - 1) = (2n - 1 + k) - n = n - 1 + k\]unit horizontal segments. Now, project them onto the $x$-axis. If some unit segment on $y = 0$ receives $b_r$ segments, then these $b_r$ segments originally formed $\ge b_r - 1$ unit squares by semi-convexity. Since there are $n - 1$ possible images for unit segments, there were at least \[(b_1 - 1) + \dots + (b_{n - 1} - 1) \ge (n - 1 + k) - (n - 1) = k\]unit squares. $\square$ The idea for the 3D problem is to project these unit squares onto planes, in a manner similar to the above. Let $S$ be a semi-convex subset of $\{1, \dots, n\}^3$ of size $3n^2 - 3n + 1 + k$. Split $S$ into $S_1, \dots, S_n$ of size $a_1, \dots, a_n$ by intersecting $S$ with $z = 1, \dots, z = n$. Then each $S_i$ determines $\ge a_i - (2n - 1)$ unit squares, so there are \begin{align*} \ge (a_1 - (2n - 1)) + \dots + (a_n - (2n - 1)) & = (3n^2 - 3n + 1 + k) - (2n^2 - n)\\ & = n^2 - 2n + 1 + k \end{align*}unit squares. Now, project them onto the $xy$-plane. By a similar argument to above, if some unit square on $z = 0$ receives $b_{r, s}$ unit squares, then these $b_{r, s}$ unit squares originally formed $\ge b_{r, s} - 1$ unit cubes. Since there are $(n - 1)^2$ possible images for unit squares, there were at least \[\sum_{(n - 1)^2 \; \text{terms}} (b_{r, s} - 1) \ge (n^2 - 2n + 1 + k) - (n - 1)^2 = k\]unit cubes. $\square$ Comments. This problem has many equality cases. There are many equality cases for $k = 0$ alone, and one can show that there exist equality cases for every $k \in [0, (n - 1)^3]$.This means that any inequalities used must be much closer to equalities than inequalities. It is natural to try the 2D problem first, both to gain intuition and because examples are easier to draw. A simple family of $2n - 1$-size semi-convex sets with zero unit squares is given by up-right paths from $(1, 1)$ to $(n, n)$. The common feature of these paths is that projecting the unit segments to the $x$-axis leaves the entirety of $[(1, 0), (n, 0)]$ singly covered. This can help motivate the projections approach to solve the 2D problem. Once the 2D problem is solved, the 3D problem falls similarly: the only caveat is that we need to actually use the 2D problem, because we need unit squares for projecting.

İs there any handout/book that İ can learn this topic (Because İ even dont understand the statement of problem)

CantonMathGuy wrote: Nice problem. Then each $S_i$ determines $\ge a_i - (2n - 1)$ unit squares Can you explain this please?

Here's a solution I found, which is a bit different from @CantonMathGuy's solution. I'll prove the following generalization: Generalization (m-dimensional variant) Let $m,n$ and $k$ be positive integers and let $$T = \{ (x,y_1,y_2,\ldots,y_{m-1}) \in \mathbb{N}^{m} \mid 1 \leqslant x,y,z \leqslant n \}$$be the length $n$ lattice $m$-dimensional cube. Suppose that $n^m-(n-1)^m+k$ points of $T$ are colored red such that if $P$ and $Q$ are red points and $PQ$ is parallel to one of the coordinate axes, then the whole line segment $PQ$ consists of only red points. Then, there exists at least $k$ unit $m$-dimensional cubes, all of whose vertices are colored red. Solution. We proceed by induction. The base case $m=1$ is trivial. For the inductive step, assume the statement holds for $t\geqslant 1$ dimensions. We'll show it holds for $t+1$ dimensions too. Let $S$ be the set of red points in $T$, and suppose that $|S|=n^{t+1}-(n-1)^{t+1}+k$. For each possible value of $\mathbf{y}=(y_1,y_2,\ldots,y_t)\in\{1,2,\ldots,n\}^t$, let $f(\mathbf{y})$ denote the number of points in $S$ of the form $(x,\mathbf{y})$. (sorry for abuse of notation ) Furthermore, for each $i=1,2,\ldots,n-1$, let $S_i$ denote the set of $\mathbf{y}$ such that both $(i,\mathbf{y})$ and $(i+1,\mathbf{y})$ are in $S$. It's easy to see that each $\mathbf{y}$ contributes exactly $\max\{0,f(\mathbf{y})-1\}$ to the sum $\sum_{i=1}^{n-1} |S_i|$, therefore $$\sum_{i=1}^{n-1} |S_i| = \sum_{\mathbf{y}} \max\{0,f(\mathbf{y})-1\} \geqslant \sum_{\mathbf{y}} (f(\mathbf{y}) - 1) = |S|-n^t$$ Now observe that by the inductive assumption, if $|S_i|= n^t-(n-1)^t+k_i$ then we have at least $\max\{0,k_i\}$ unit $t$-dimensional cubes in $S_i$. Moreover, if $U$ is such a cube then $U' =(i,U)\cup (i+1,U)$ is a unit $(t+1)$-dimensional cube. It's clear that all these $t+1$-dimensional cubes formed are distinct, hence the number of unit $(t+1)$-dimensional cubes is at least $$\sum_{i=1}^{n-1} \max\{0,|S_i|-n^t+(n-1)^t\} \geqslant \left(\sum_{i=1}^{n-1} |S_i|\right) - (n-1)\big(n^t-(n-1)^t\big)$$$$\geqslant \Big(|S| - n^t\Big) -(n-1)\big(n^t-(n-1)^t)=|S|-n^{t+1}+(n-1)^{t+1} = k$$which concludes our proof. $\blacksquare$

tenplusten wrote: İs there any handout/book that İ can learn this topic (Because İ even dont understand the statement of problem) I think this is of similar flavor? https://artofproblemsolving.com/community/c6h1480696p8639265

Nice problem We will prove the $1D$ and $2D$ analogy first. CLAIM 1. In a $n\times 1$ grid (which is just a number line), if $1+k$ points are colored so that every point between two colored points are colored, then there are at least $k$ colored unit segments. Proof. Obvious. $\blacksquare$ CLAIM 2. In a $n\times n$ grid $G$, if $n^2-(n-1)^2+k=2n-1+k$ points are colored so that every point between two color poitns are colored, then there are at least $k$ colored unit square. Proof. WLOG assume that there are colored unit squares in every row and column(otherwise we can just add them without changing the number of colored unit squares.) Let $(i,j)$ denote the cell in the $i^{th}$ row and the $j^{th}$ column. We color another $n\times (n-1)$ grid $G'$ as follows: $$\text{If both } (i,j) \text{ and } (i,j+1)\text{ are selected in } G\text{ then } (i,j)\text{ is selected in } G'$$Now it is easy to see that in $G'$, every point between two colored points are colored. Meanwhile, every colored unit square in $G$ corresponds to a vertical segment in $G'$. Now there are at least $$2n-1+k-n=n-1+k$$colored points in $G'$. Suppose there are $c_1,c_2,...,c_{n-1}$ colored points in each of the columns of $G'$. By CLAIM 1, there are at least $$c_1+c_2+...+c_{n-1}-(n-1)\geq k$$colored vertical segments, this proves CLAIM 2. $\blacksquare$ Now we return to the original problem. CLAIM 3. In a $n\times n\times n$ cube $C'$, if $n^3-(n-1)^3+k=3n^2-3n+1+k$ points are colored so that every point between two color poitns are colored, then there are at least $k$ colored unit square. Proof. This is very similar to CLAIM 2, again we can assume that there are colored unit suqares in every line parallel to one of the coordinate axes. Color the $n\times n\times (n-1)$ cube $C'$ so that a point in $C'$ is colored if and only if the corresponding unit square in $C$ is colored. Now, unit cubes in $C$ corresponds to vertical segments in $C'$. From CLAIM 2 we can see that there are at least $$3n^2-3n+1-n(2n-1)+k=(n-1)^2+k$$points in $C'$. Now by CLAIM 1 there are at least $$(n-1)^2+k-(n-1)^2$$vertical segments in $C'$ so we are done.

Solved with goodbear. Consider the following binary matrices: Let \(A\) be the \(n\times n\times n\) matrix with \(A_{ijk}=1\) iff \((i,j,k)\) is red. Let \(B\) be the \(n\times n\times(n-1)\) matrix with \(B_{ijk}=1\) iff \(A_{ijk}=A_{i,j,k+1}=1\). Let \(C\) be the \(n\times(n-1)\times(n-1)\) matrix with \(C_{ijk}=1\) iff \(B_{ijk}=B_{i,j+1,k}=1\). Let \(D\) be the \((n-1)\times(n-1)\times(n-1)\) matrix with \(D_{ijk}=1\) iff \(C_{ijk}=C_{i+1,j,k}=1\). Hence each 1 in \(D\) corresponds with a unit cube colored red. For binary matrices \(S\), let \(\sum S\) denote the number of 1's in \(S\) (i.e.\ the sum of the elements). It can be easily verified that \(\sum B\ge\sum A-n^2\), since for each of the \(n\times n\) beams with fixed \(z\)-coordinate, if the beam contains \(r\ge1\) red cells, then it contains \(r-1\) pairs of adjacent red cells; \(\sum C\ge\sum B-n(n-1)\) analogously; and \(\sum D\ge\sum C-(n-1)^2\) analogously. The number of unit cubes is \begin{align*} \sum D&\ge\sum A-\left[n^2+n(n-1)+(n-1)^2\right]\\ &=\left(3n^2-3n+1+k\right)-\left(3n^2-3n+1\right)=k. \end{align*}

Very Nice, reminds of IMO 20/6. Claim 1: If in an $n \cdot n$ grid we color $2n-1+k$ red points, such that if $\overline{PQ}$ is parallel to one of coordinate axes then the whole segment $\overline{PQ}$ is colored red then atleast $k$ red unit squares are formed.

Now in similar fashion, we split into planes and project onto x-y plane; Let $x_k$ denote the number of points on k-th plane; then we have atleast $n^2-2n+1+k$ unit squares by Claim 1, so we have atleast $k$ unit cubes.