Problem 1391

We set $n = p \binom{p+1}{2}$. For each $j \in \{0, 1, \dots, n\}$, we consider the set $A_j^0 = \{(i, j, 0) \in A; 0 \le i \le p\}$. By the Pigeonhole Principle, we can guarantee that, for each $j$, there are two points of $A_j^0$ of the same color. There may be more than two, or it may happen for more than one color; it does not matter, among the $p+1$ we mark two that share a color. Taking into account that there are $p \binom{p+1}{2} + 1$ possible values of $j$, again by the Pigeonhole Principle, there will exist at least $r = \binom{p+1}{2} + 1$ of these $A_j^0$ (say $A_{j_1}^0, \dots, A_{j_r}^0$) in which the color repeated in all of them is the same (color $c$). Since the number of ways to choose the two positions (values of $i$) in each of these $A_{j_t}^0$, with $t = 1, \dots, r$, is $\binom{p+1}{2}$, using the Pigeonhole Principle once again, we can guarantee that there exist $A_{j_\alpha}$ and $A_{j_\beta}$, with $\alpha, \beta \in \{1, \dots, r\}$, in which color $c$ appears twice in each and in the same positions. That is, it is proved that in the plane $z = 0$, and with values of the coordinate $x \in \{0, 1, \dots, p\}$ and of the coordinate $y \in \{0, 1, \dots, n\}$, there exist four points
$$(i_1, j_\alpha, 0), (i_2, j_\alpha, 0) \in A_{j_\alpha} \quad (i_1, j_\beta, 0), (i_2, j_\beta, 0) \in A_{j_\beta}$$
which are vertices of a rectangle (always with Sides Parallel to the Grid Edges: SPGE) and all four of the same color.

The number, $m$, of ways to choose, in a grid of $(p+1) \times (n+1)$ points, four points that are vertices of an SPGE rectangle is the same as the number of ways to choose two values of the abscissa and two values of the ordinate, that is $m = \binom{p+1}{2} \binom{n+1}{2}$.

For each $k \in \{0, 1, \dots, p \times m\}$ we consider the grid $A^k = \{(i, j, k) \in A; 0 \le i \le p, 0 \le j \le n\}$. We have $pm + 1$ grids and in each of them there are four points that share a color and are vertices of an SPGE rectangle. By the Pigeonhole Principle, there are at least $p+1$ of these grids in which the four points of each one occupy the same positions with respect to their first two coordinates. Finally, again by the Pigeonhole Principle, there are (at least) two of these $p+1$ grids such that the common color of the four vertices of one is the same as the common color of the four vertices of the other. Thus we have eight points of $A$ that share a color and are vertices of a right parallelepiped.