To each point of $\mathbb{Z}^3$ we assign one of $p$ colors. Prove that there exists a rectangular parallelepiped with all its vertices in $\mathbb{Z}^3$ and of the same color.
Problem
Source: Spain Mathematical Olympiad 2020 P3
Tags: combinatorics, lattice, Spain
14.07.2020 20:18
Sumgato wrote: To each point of $\mathbb{Z}^3$ we assign one of $p$ colors. Prove that there exists a rectangular parallelepiped with all its vertices in $\mathbb{Z}^3$ and of the same color. Is it full statement of problem? If not, post full problem please.
14.07.2020 20:43
Brian_math wrote: Is it full statement of problem? If not, post full problem please. Why would you think it is not the full statement? It seems like a perfectly reasonable problem to me...
21.07.2020 11:30
Claim 1: Every 2d rectangle of dimensions $(p+1)\;\times\; p{p+1\choose 2}+1$ contains a chromatic subrectangle. Proof: PHP ensures that every column has a chromatic pair, also by PHP we have the same pair(row-wise) in at least $p+1$ columns, as we have $p$ colours we have at leats two chromatic pairs in the same rows and different columns and they form a chromatic rectangle. Claim 2: Every rectangular parallelepiped of dimensions $(p+1)\; \times\; p{p+1\choose 2}+1 \; \times\; p{p+1\choose 2} {p{p+1\choose 2}+1 \choose 2}+1$ contains a chromatic rectangular parallelepiped. Proof: By the claim 1 we have a chromatic rectangle in every $xy$-plane, by PHP we have the same quartet($xy$-plane-wise) in at least $(p+1)$ $xy$-planes, as we have $p$ colours we have at leats two chromatic quartets in different $xy$-planes and they form a chromatic rectangular parallelepiped.