Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

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 January 11, 2016.


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

Problems in Mathematics of KöMaL, December 2015