 |
A B. 4698. feladat (2015. március) |
B. 4698. Mutassunk példát olyan \(\displaystyle H_1,H_2,\ldots\subset\mathbb{N}\) halmazokra, amelyekre a következő feltételek teljesülnek:
\(\displaystyle a)\) Tetszőleges \(\displaystyle n\) pozitív egészre \(\displaystyle |H_n|=n\).
\(\displaystyle b)\) Tetszőleges \(\displaystyle n\), \(\displaystyle k\) pozitív egészekre \(\displaystyle H_n \cap H_k = H_{(n,k)}\), ahol \(\displaystyle (n,k)\) az \(\displaystyle n\) és \(\displaystyle k\) legnagyobb közös osztóját jelöli.
(5 pont)
A beküldési határidő 2015. április 10-én LEJÁRT.
Megoldásvázlat. Definiáljuk az \(\displaystyle X_1,X_2,\ldots\) pozitív egészeket a következőképpen: legyen \(\displaystyle X_1=1\), továbbá, ha ha \(\displaystyle n\ge1\) prímtényezős felbontása \(\displaystyle n=p_1^{a_1}\cdots p_s^{a_s}\), akkor legyen \(\displaystyle X_n=p_1^{p_1^{a_1}-1}\cdots p_s^{p_s^{a_s}-1}\). Végül legyen \(\displaystyle H_n\) az \(\displaystyle X_n\) osztóinak halmaza.
Vegyük észre, hogy ha \(\displaystyle n\) prímtényezős felbontását kibővítjük néhány további prím nulladik hatványával, az nem változtatja meg a kapott \(\displaystyle X_n\) értéket.
Azt állítjuk, hogy
(1) minden \(\displaystyle n\)-re az \(\displaystyle X_n\)-nek pontosan \(\displaystyle n\) pozitív osztója van;
(2) bármely \(\displaystyle n,k\) pár esetén \(\displaystyle (X_n,X_k)=X_{n,k}\).
Az (1) triviális \(\displaystyle n=1\) esetén. Ha pedig \(\displaystyle n=p_1^{a_1}\cdots p_s^{a_s}\), akkor \(\displaystyle X_n=p_1^{p_1^{a_1}-1}\cdots p_s^{p_s^{a_k}-1}\) osztóinak száma éppen \(\displaystyle \big((p_1^{a_1}-1)+1\big)\cdots\big((p_s^{a_s}-1)+1\big)= p_1^{a_1}\cdots p_s^{a_s}=n\).
A (2) bizonyításához tegyük fel, hogy \(\displaystyle n=p_1^{a_1}\cdots p_s^{a_s}\) és \(\displaystyle n=p_1^{b_1}\cdots p_s^{b_s}\). (Azokat a prímeket, amik csak az egyik számban szerepelnek, a másik számnál is felsoroljuk \(\displaystyle 0\) kitevővel.)
Ekkor \(\displaystyle (n,k) = p_1^{\min(a_1,b_1)}\cdots p_s^{\min(a_s,b_s)}\) és
\(\displaystyle (X_n,X_k) = (p_1^{p_1^{a_1}-1}\cdots p_s^{p_s^{a_s}-1}, p_1^{p_1^{b_1}-1}\cdots p_s^{p_s^{b_s}-1}) = p_1^{\min(p_1^{a_1}-1,p_1^{b_1}-1)}\cdots p_s^{\min(p_s^{a_s}-1,p_s^{b_s}-1)} = p_1^{p_1^{\min(a_1,b_1)}-1}\cdots p_2^{p_2^{\min(a_2,b_2)}-1} = X_{(n,k)}. \)
Most ellenőrizzük, hogy a megkonstruált \(\displaystyle H_1,H_2,\ldots\) halmazokra valóban teljesül az a) és a b) tulajdonság.
Az (1) következménye, hogy \(\displaystyle |H_n|=n\).
Tetszőleges \(\displaystyle n,k\) párra a \(\displaystyle H_n\cap H_k\) halmaz az \(\displaystyle n\) és \(\displaystyle k\) közös osztóiból áll. Mivel a közös osztók éppen a legnagyobb közös osztó osztói, ez a halmaz pontosan \(\displaystyle H_{(n,k)}\).
Megjegyzés. A feladat kapcsolódik az A.492. feladat megoldásához.
Statisztika:
47 dolgozat érkezett. 5 pontot kapott: Baran Zsuzsanna, Bindics Boldizsár, Döbröntei Dávid Bence, Gáspár Attila, Glasznova Maja, Kerekes Anna, Kovács 246 Benedek, Lajkó Kálmán, Molnár-Sáska Zoltán, Nagy-György Pál, Porupsánszki István, Sal Kristóf, Schwarcz Tamás, Szebellédi Márton, Szécsényi Nándor, Tóth Viktor, Varga-Umbrich Eszter, Williams Kada, Zsakó Ágnes. 4 pontot kapott: Andó Angelika, Árvai Balázs, Csépai András, Imolay András, Katona Dániel, Keresztfalvi Bálint, Mócsy Miklós, Nagy Dávid Paszkál, Nagy Kartal, Wei Cong Wu, Záhorský Ákos. 3 pontot kapott: 4 versenyző. 2 pontot kapott: 6 versenyző. 1 pontot kapott: 2 versenyző. 0 pontot kapott: 3 versenyző. Nem versenyszerű: 2 dolgozat.
A KöMaL 2015. márciusi matematika feladatai