KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up


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.


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:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley