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