Which parellelepied covers all the coloured lattice points?
Source: Czech-Polish-Slovak 2001 Q6
April 30, 2013
analytic geometrycombinatorics unsolvedcombinatorics
Problem Statement
Points with integer coordinates in cartesian space are called lattice points. We color lattice points blue and other lattice points red in such a way that no two blue-red segments have a common interior point (a segment is blue-red if its two endpoints are colored blue and red). Consider the smallest rectangular parallelepiped that covers all the colored points.
(a) Prove that this rectangular parallelepiped covers at least lattice points.
(b) Give an example of a coloring for which the considered rectangular paralellepiped covers at most lattice points.