Az A. 657. feladat (2015. december)

A. 657. Legyen \(\displaystyle \{x_n\}\) a van der Korput sorozat, azaz ha a pozitív egész \(\displaystyle n\) bináris alakja \(\displaystyle n=\sum_i a_i2^i\) \(\displaystyle \big(a_i\in\{0,1\}\big)\), akkor \(\displaystyle x_n=\sum_i a_i2^{-i-1}\). Legyen \(\displaystyle V\) a síkbeli \(\displaystyle (n,x_n)\) pontok halmaza, ahol \(\displaystyle n\) pozitív egész. Legyen \(\displaystyle G\) az a gráf, melynek csúcshalmaza \(\displaystyle V\), és amelyben két különböző csúcsot, \(\displaystyle p\)-t és \(\displaystyle q\)-t akkor és csak akkor kötjük össze éllel, ha van olyan - a koordinátatengelyekkel párhuzamos állású - \(\displaystyle R\) téglalap, melyre \(\displaystyle R\cap V=\{p,q\}\). Igazoljuk, hogy \(\displaystyle G\) kromatikus száma véges.

Schweitzer Miklós emlékverseny, 2015

(5 pont)

A beküldési határidő 2016. január 11-én LEJÁRT.

Megoldásvázlat. Megmutatjuk, hogy ha \(\displaystyle n,m\) különböző pozitív egészek, és \(\displaystyle n\equiv m\pmod7\), akkor az \(\displaystyle (n,x_n)\) és \(\displaystyle (m,x_m)\) pontok által meghatározott téglalap belsejében van legalább egy \(\displaystyle (k,x_k)\) pont. Ebből következik, hogy \(\displaystyle n\equiv m\pmod7\) esetén a \(\displaystyle (n,x_n)\) és \(\displaystyle (m,x_m)\) pontok nincsenek összekötve a gráfban, így azokat színezhetjük azonos színnel, így a gráf színezésére \(\displaystyle 7\) szín biztosan elég.

Tegyük tehát fel, hogy \(\displaystyle m<n\), és \(\displaystyle m\equiv n\pmod7\). Az \(\displaystyle m\) és \(\displaystyle n\) bináris alakja legyen \(\displaystyle m=\sum_i a_i2^i\), illetve \(\displaystyle n=\sum_i b_i2^i\). Legyen \(\displaystyle p\) és \(\displaystyle q\) a legkisebb, illetve a legnagyobb index, amelyre \(\displaystyle a_p\ne b_p\), illetve \(\displaystyle a_q\ne b_q\). A \(\displaystyle p\) és \(\displaystyle q\) definíciója miatt \(\displaystyle i<p\) és \(\displaystyle i>q\) esetén \(\displaystyle a_i=b_i\). Továbbá, ha \(\displaystyle p=q\) lenne, akkor \(\displaystyle n-m=2^p\) lenne, de ez ellentmondana annak, hogy \(\displaystyle n-m\) osztható \(\displaystyle 7\)-tel. Tehát biztosan \(\displaystyle p<q\). Ezen kívül, mivel \(\displaystyle m<n\), biztosan \(\displaystyle a_q=0\) és \(\displaystyle b_q=1\).

A keresett \(\displaystyle k\) számra két jelöltünk lesz:

    \(\displaystyle k_1 = \sum_{i<p} a_i 2^i + 2^p + 2^q + \sum_{i>q} a_i 2^i\), vagyis megtartjuk \(\displaystyle n\) és \(\displaystyle k\) közös első és utolsó jegyeit, a \(\displaystyle p\)-edik és \(\displaystyle q\)-adik jegyet \(\displaystyle 1\)-esre, a közöttük álló jegyeket \(\displaystyle 0\)-ra cseréljük;

    \(\displaystyle k_2 = \sum_{i<p} a_i 2^i + \sum_{p<i<q} 2^i + \sum_{i>q} a_i 2^i\), vagyis megtartjuk \(\displaystyle n\) és \(\displaystyle k\) közös első és utolsó jegyeit, a \(\displaystyle p\)-edik és \(\displaystyle q\)-adik jegyet \(\displaystyle 0\)-ra, a közöttük álló jegyeket \(\displaystyle 1\)-esre cseréljük.

Megmutatjuk, hogy a \(\displaystyle (k_1,x_{k_1})\), \(\displaystyle (k_2,x_{k_2})\), pontok közül legalább az egyik az \(\displaystyle (n,x_n)\) és \(\displaystyle (m,x_m)\) pontok által meghatározott téglalap belsejében van.

1. eset: \(\displaystyle x_m<x_n\). Ez azt jelenti, hogy \(\displaystyle a_p=0\) és \(\displaystyle b_p=1\).

Világos, hogy \(\displaystyle k_1>m\) és \(\displaystyle x_{k_1}>x_m\). Ha a \(\displaystyle b_{p+1},\ldots,b_{q-1}\) jegyek között valamelyik \(\displaystyle 1\)-es, akkor \(\displaystyle k_1<n\) és \(\displaystyle x_{k_1}<x_n\), vagyis a \(\displaystyle k_1\) megfelelő.

Hasonlóan, \(\displaystyle k_2<n\) és \(\displaystyle x_{k_2}<x_n\) triviális, és ha az \(\displaystyle a_{p+1},\ldots,a_{q-1}\) jegyek között szerepel a \(\displaystyle 0\), akkor \(\displaystyle k_2>m\) és \(\displaystyle x_{k_2}>x_m\), vagyis \(\displaystyle k_2\) megfelelő.

Már csak az az eset maradt meg, ha \(\displaystyle a_{p+1}=\ldots=a_{q-1}=1\) és \(\displaystyle b_{p+1}=\ldots=b_{q-1}=0\), ebben az esetben viszont \(\displaystyle n-m=3\cdot2^p\), ez pedig ellentmond annak, hogy \(\displaystyle n-m\) osztható \(\displaystyle 7\)-tel.

2. eset: \(\displaystyle x_m<x_n\). Ekkor tehát, hogy \(\displaystyle a_p=1\) és \(\displaystyle b_p=0\).

Ha az \(\displaystyle a_{p+1},\ldots,a_{q-1}\) jegyek között szerepel a \(\displaystyle 1\), és a \(\displaystyle b_{p+1},\ldots,b_{q-1}\) jegyek között is szerepel a \(\displaystyle 1\), akkor \(\displaystyle k_1\) megfelelő, mert \(\displaystyle m<k_1<n\) és \(\displaystyle x_m>x_{k_1}>x_n\).

Hasonlóan, ha az \(\displaystyle a_{p+1},\ldots,a_{q-1}\) jegyek között szerepel a \(\displaystyle 0\), és a \(\displaystyle b_{p+1},\ldots,b_{q-1}\) jegyek között is szerepel a \(\displaystyle 0\), akkor \(\displaystyle k_2\) megfelelő, mert \(\displaystyle m<k_2<n\) és \(\displaystyle x_m>x_{k_2}>x_n\).

Ha sem \(\displaystyle k_1\), sem \(\displaystyle k_2\) nem megfelelő, az csak úgy lehet, hogy az \(\displaystyle a_{p+1},\ldots,a_{q-1}\) és \(\displaystyle b_{p+1},\ldots,b_{q-1}\) jegysorozatok közül az egyik csupa \(\displaystyle 0\)-ból, a másik csupa \(\displaystyle 1\)-esből áll. Ha \(\displaystyle a_{p+1}=\ldots=a_{q-1}=1\) és \(\displaystyle b_{p+1}=\ldots=b_{q-1}=0\), akkor \(\displaystyle n-m=2^p\) nem osztható \(\displaystyle 7\)-tel, ellentmondás. Ha pedig \(\displaystyle a_{p+1}=\ldots=a_{q-1}=0\) és \(\displaystyle b_{p+1}=\ldots=b_{q-1}=1\), akkor \(\displaystyle n-m=2^{q+1}-3\cdot2^p=2^p\cdot(2^{q-p+1}-3)\), ami szintén nem lehet osztható \(\displaystyle 7\)-tel, szintén ellentmondás. (A \(\displaystyle 2^{q-p+1}\) csak \(\displaystyle 1,2\) vagy \(\displaystyle 4\) maradékot adhat \(\displaystyle 7\)-tel osztva.)

Ezzel bebizonyítottuk, hogy a gráf kromatikus száma legfeljebb \(\displaystyle 7\).

Statisztika:

4 dolgozat érkezett.
5 pontot kapott:	Szabó 789 Barnabás, Williams Kada.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2015. decemberi matematika feladatai