A B. 4334. feladat (2011. február)

B. 4334. Adott egy egyenes és rajta egy pont. Nevezzük Z-nek az egyenes azon pontjainak halmazát, amelyeknek ettől a ponttól vett távolsága egész. Mutassuk meg, hogy Z-nek bármely H háromelemű részhalmaza esetén Z felbontható H-val egybevágó részhalmazokra.

Javasolta: Bodor Bertalan és Éles András (Budapest)

(5 pont)

A beküldési határidő 2011. március 10-én LEJÁRT.

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.

Statisztika:

3 dolgozat érkezett.
5 pontot kapott:	Viharos Andor.
4 pontot kapott:	Gyarmati Máté.
2 pontot kapott:	1 versenyző.

A KöMaL 2011. februári matematika feladatai