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^{i1}\). 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:
