19. $[\mathbf{1 2}]$ Find the least positive integer $N$ with the following property: If all lattice points in $[1,3] \times[1,7] \times$ $[1, N]$ are colored either black or white, then there exists a rectangular prism, whose faces are parallel to the $x y, x z$, and $y z$ planes, and whose eight vertices are all colored in the same color.
Answer: 127
First we claim that if the lattice points in $[1,3] \times[1,7]$ are colored either black or white, then there exists a rectangle whose faces are parallel to the $x$ and $y$ axes, whose vertices are all the same color (a.k.a. monochromatic). Indeed, in every row $y=i, 1 \leq i \leq 7$, there are two lattice points with the same color. Note there are 3 combinations of 2 columns to choose from (for the two similarly-colored lattice points to be in), and 2 colors to choose from. By the Pigeonhole Principle, in the $2 \cdot 3+1=7$ rows two rows must have a pair of similarly-colored lattice points in the same columns, i.e. there is a monochromatic rectangle.
This shows that in each cross section $z=i, 1 \leq i \leq N$ there is a monochromatic rectangle. Next, note there are $\binom{3}{2}\binom{7}{2}$ possibilities for this rectangle $\left(\binom{3}{2}\right.$ ways to choose the $2 x$-coordinates and $\binom{7}{2}$ ways to choose the $2 y$-coordinates), and 2 possible colors. Thus if $N=2\binom{3}{2}\binom{7}{2}+1=127$, then by the Pigeonhole Principle there are two values of $i$ such that the same-colored rectangle has the same $x$ and $y$ coordinates in the plane $z=i$, i.e. there is a monochromatic rectangular prism.
For $N=126$ the assertion is not true. In each cross section $z=i$, we can color so that there is exactly 1 monochromatic rectangle, and in the 126 cross sections, have all 126 possible monochromatic rectangles represented. To do this, in each cross section we color so that each row has exactly 2 lattice points of the same color, and such that 6 of the rows give all possible combinations of 2 points having the same color. This way, there will be exactly 1 monochromatic rectangle in each cross section; we can obviously vary it for the different cross sections.