Problem B. 4334. (February 2011)

B. 4334. Given a line and a point on it, let Z denote the set of those points of the line that are at integer distances from the given point. Prove that if H is any three-element subset of Z, then it is possible to partition Z into subsets congruent to H.

(Suggested by B. Bodor and A. Éles, Budapest)

(5 pont)

Deadline expired on March 10, 2011.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Képzeljük az egyenest vízszintesnek, és vegyünk fel rajta egy \(\displaystyle P'\) pontot, amely az adott \(\displaystyle P\) ponttól 1/2 távolságra esik. \(\displaystyle Z\)-nek \(\displaystyle P'\)-től jobbra eső pontjait \(\displaystyle P'\)-re tükrözve \(\displaystyle Z\)-nek \(\displaystyle P'\)-től balra eső pontjait kapjuk, ezért elegendő azt megmutatni, hogy \(\displaystyle Z\)-nek bármely \(\displaystyle H\) háromelemű részhalmaza esetén \(\displaystyle Z\) \(\displaystyle P'\)-től jobbra eső pontjainak halmaza felbontható \(\displaystyle H\)-val egybevágó részhalmazokra. Ezt a feladatot az egész számok nyelvén a következőképpen fogalmazhatjuk át: bizonyítandó, hogy tetszőleges \(\displaystyle a\le b\) pozitív egészek esetén léteznek olyan \(\displaystyle s_1<s_2<\ldots\) természetes számok és \(\displaystyle S_i\in \left\{ \{s_i, s_i+a, s_i+a+b\},\ \{s_i, s_i+b, s_i+a+b\}\right\}\) halmazok, hogy minden természetes szám az \(\displaystyle S_i\) halmazok közül pontosan egybe esik bele.

Ilyen sorozatokat konstruálhatunk a következő eljárással. Tegyük fel, hogy valamely \(\displaystyle n>0\) egész számra \(\displaystyle i<n\) esetén az \(\displaystyle s_i\) természetes számokat és a megfelelő \(\displaystyle S_i\) halmazokat már megadtuk. Legyen \(\displaystyle N\) a legkisebb természetes szám, amelyet az \(\displaystyle S_i\) halmazok (\(\displaystyle i<n\)) egyike sem tartalmaz. Legyen \(\displaystyle s_n=N\). Ha az \(\displaystyle \{N, N+a, N+a+b\}\) halmaz diszjunkt az eddig megadottaktól, akkor legyen \(\displaystyle S_n=\{N, N+a, N+a+b\}\), ellenkező esetben pedig legyen \(\displaystyle S_n=\{N, N+b, N+a+b\}\). Kezdetben egyetlen \(\displaystyle s_i\) számunk és \(\displaystyle S_i\) halmazunk sincs megadva, így első lépésben az eljárási szabály az \(\displaystyle s_1=0\), \(\displaystyle S_1=\{0,a,a+b\}\) választásra vezet.

Elegendő lesz azt megmutatni, hogy minden \(\displaystyle n\) pozitív egészre teljesül a következő három állítás:

(i) \(\displaystyle s_1<s_2<\ldots<s_n\);

(ii) az \(\displaystyle S_1,S_2,\ldots, S_n\) halmazok uniója tartalmazza az első \(\displaystyle s_n+1\) természetes számot;

(iii) az \(\displaystyle S_1,S_2,\ldots, S_n\) halmazok páronként diszjunktak.

Ezt \(\displaystyle n\) szerinti teljes indukcióval látjuk be; \(\displaystyle n=1\) esetén az állítás nyilvánvaló.

Az indukciós lépéshez tegyük fel, hogy \(\displaystyle n>1\), és \(\displaystyle (n-1)\)-re már mind a három állítás igazolást nyert. Legyen tehát \(\displaystyle N\) a legkisebb természetes szám, amelyet az \(\displaystyle S_i\) halmazok (\(\displaystyle i<n\)) egyike sem tartalmaz. A második állításból következik, hogy \(\displaystyle N>s_{n-1}\), ami az \(\displaystyle s_n=N\) választás miatt azt jelenti, hogy az első állítás igaz lesz \(\displaystyle n\)-re is. Mivel \(\displaystyle S_n\) választása garantálja, hogy \(\displaystyle N\in S_n\), a második állítás is érvényes lesz \(\displaystyle n\)-re. Mivel \(\displaystyle S_1,\ldots,S_{n-1}\) páronként diszjunktak, a harmadik állítás is nyilván teljesül \(\displaystyle n\)-re abban az esetben, ha az \(\displaystyle \{N, N+a, N+a+b\}\) halmaz diszjunkt az eddig megadottaktól, vagyis az \(\displaystyle n\)-edik lépésben az \(\displaystyle S_n=\{N, N+a, N+a+b\}\) választást alkalmazzuk.

Ha az \(\displaystyle \{N, N+a, N+a+b\}\) halmaz nem diszjunkt az eddig megadottaktól, akkor először gondoljuk meg, hogy minden eddig megkonstruált halmaz legkisebb eleme kisebb, mint \(\displaystyle s_n=N\), tehát minden eddig megkonstruált halmaz legnagyobb eleme kisebb, mint \(\displaystyle N+a+b\), ami azt jelenti, hogy csakis \(\displaystyle N+a\) lehet az a szám, amely beleesik valamelyik már megkonstruált halmazba. Megmutatjuk, hogy ekkor \(\displaystyle N+b\) nem eshet bele egyikbe sem, ami azt jelenti, hogy \(\displaystyle S_n=\{N, N+b, N+a+b\}\) valóban diszjunkt az egymástól páronként diszjunkt \(\displaystyle S_1,\ldots,S_{n-1}\) halmazok mindegyikétől.

Ezen észrevétel igazolásához tegyük fel, hogy \(\displaystyle N+b\) beleesik valamelyik \(\displaystyle S_i\) (\(\displaystyle i<n\)) halmazba. Az \(\displaystyle s_i<N\) és \(\displaystyle a\le b\) feltételek miatt ez csak úgy lehet, ha \(\displaystyle N+b\) ennek az \(\displaystyle S_i\) halmaznak a legnagyobb eleme; ekkor az \(\displaystyle S_i\) halmaz legkisebb eleme \(\displaystyle N-a\). Mivel \(\displaystyle N\not \in S_i\), ez csak úgy lehet, ha \(\displaystyle S_i=\{N-a, (N-a)+b, N+b\}\), azonban ez esetben az eljárás értelmében az \(\displaystyle S_i=\{N-a,N,N+b\}\) választást kellett volna alkalmaznunk. Ez az ellentmondás igazolja észrevételünket, és egyben azt is, hogy a harmadik állítás is érvényes lesz \(\displaystyle n\)-re.

Statistics:

3 students sent a solution.
5 points:	Viharos Andor.
4 points:	Gyarmati Máté.
2 points:	1 student.

Problems in Mathematics of KöMaL, February 2011