Problem 2. Determine the smallest natural number $n$ such that, no matter which $n$ vertices of a cube we color red, there exists a vertex of the cube that has all three adjacent vertices red.
Solution. We will show that the sought number is 5.

Let $A B C D A^{\prime} B^{\prime} C^{\prime} D^{\prime}$ be a cube. By coloring the 4 vertices of one face of the cube in red, for example $A, B, C, D$, there is no vertex that has all three adjacent vertices red, so $n \geq 5$.

Now, for $n=5$, no matter how we color $n$ vertices in red, one of the planes $(A B C D)$ and $\left(A^{\prime} B^{\prime} C^{\prime} D^{\prime}\right)$ will have at least three red vertices. We can assume that $A, B, C$ are red. If $D$ is also red, then there is only one red vertex in the plane $\left(A^{\prime} B^{\prime} C^{\prime} D^{\prime}\right)$. If $X^{\prime}$ is the red vertex, with $X \in\{A, B, C, D\}$, then vertex $X$ has all its neighbors red.

If $D$ is not red, then in the plane $\left(A^{\prime} B^{\prime} C^{\prime} D^{\prime}\right)$ there are two red vertices. If $B^{\prime}$ or $D^{\prime}$ is red, then $B$, respectively $D$, has all its neighbors red. In the contrary case, $A^{\prime}$ and $C^{\prime}$ are red and then $B^{\prime}$ has all its neighbors red.

In conclusion, no matter how we color 5 of the vertices in red, there will be at least one vertex that has all its neighbors red, so the minimum sought is $n=5$.