 |
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