0
$\begingroup$

Here are two problems, each one is an olympiad combinatorics problem with coloring the plane and space.

A) The plane is colored with four colors. Prove that it is possible to choose three different points with different colors, such that they are collinear, i.e. there is a line containing three different colored points!

B) The space is colored with five colors. Prove that it is possible to choose fourdifferent points with different colors, such that they are on the same plane, i.e. there is a plane containing four different colored points!

Can you generalize for $n$th dimension? Please help!

$\endgroup$
0
$\begingroup$

Lemma. For $t\in \Bbb R$ let $v(t)=(1,t,\ldots, t^{n-1})^T\in\Bbb R^n$. Then if $t_1<t_2<\ldots< t_n$, the vectors $v(t_i)$, $1\le i\le n$ form a basis of $\Bbb R^n$.

Proof. Linear dependency would mean that the matrix $$\begin{pmatrix}1&t_1&t_1^2&\ldots& t_1^{n-1}\\ 1&t_2&t_2^2&\ldots& t_2^{n-1}\\ \vdots &\vdots&\vdots&\ddots&\vdots\\ 1&t_n&t_n^2&\ldots& t_n^{n-1}\\\end{pmatrix} $$ is singular, hence has a non-zero $(c_0,\ldots, c_{n-1})^T$ in its kernel. Then the $t_i$ are $n$ distinct roots of the polynomial $c_0+c_1 X+\ldots c_{n-1}X^{n-1}$, contradiction. $\square$

Theorem. Let $n\ge 2$. Let $\gamma\colon \Bbb R^n\to\{1,\ldots, n+2\}$ be onto. Then there exists a $1$-codimensional affine subspace $H$ such that $|\gamma(H)|\ge n+1$.

Proof. Assume the claim is false. Pick $a$ with $\gamma(a)=n+2$. For $t\in \Bbb R$, let $H(t)$ be the hyperplane through $a$ and perpendicular to $v(t)$, where $v(t)$ is defined as in the lemma. Each $H(t)$ avoids two (or more) colours. By the pigeon-hole principle, there are infinitely many among these hyperplanes that avoid the same pair $\{u,v\}$ of colours, in particular we find real numbers $t_1<\ldots <t_n$ with $\gamma(H(t_i))\cap\{u,v\}=\emptyset$ for $1\le i\le n$.

Pick points $b,c$ with $\gamma(b)=u$, $\gamma(c)=v$. As $v(t_1),\ldots, v(t_n)$ form a basis, $b-c$ cannot be perpendicular to all $v(t_i)$. It follows that the line $bc$ intersects one of the $H(t_i)$ in a point $d$ with a colour $\gamma(d)\notin \{u,v\}$. Pick $n-2$ points $x_1,\ldots, x_{n-2}$ such that the $n+1$ points $b,c,d,x_1,\ldots, x_{n-2}$ have pairwise distinct colours (this is the step where we use that $n\ge 2$). As $b,c,d$ are collinear, the points $b,c,d,x_1,\ldots, x_{n-2}$ are in a common hyperplane $H$ with the desired property. $\square$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.