Magyar Information Contest Journal Articles

# Problem A. 657. (December 2015)

A. 657. Let $\displaystyle \{x_n\}$ be the van der Korput sequence, that is, if the binary representation of the positive integer $\displaystyle n$ is $\displaystyle n = \sum_i a_i2^i$ ($\displaystyle a_i\in\{0,1\}$), then $\displaystyle x_n = \sum_i a_i2^{-i-1}$. Let $\displaystyle V$ be the set of points $\displaystyle (n,x_n)$ in the plane where $\displaystyle n$ runs over the positive integers. Let $\displaystyle G$ be the graph with vertex set $\displaystyle V$ that is connecting any two distinct points $\displaystyle p$ and $\displaystyle q$ if and only if there is a rectangle $\displaystyle R$ which lies in a parallel position to the axes and $\displaystyle R\cap V = \{p,q\}$. Prove that the chromatic number of $\displaystyle G$ is finite.

Miklós Schweitzer competition, 2015

(5 pont)

Deadline expired on 11 January 2016.

### Statistics:

 4 students sent a solution. 5 points: Szabó 789 Barnabás, Williams Kada. 1 point: 1 student. 0 point: 1 student.

 Our web pages are supported by: Morgan Stanley