Az A. 494. feladat (2009. december)

A. 494. Legyenek p₁,...,p_k prímszámok, és legyen S az egész számok azon részhalmaza, melynek elemei nem oszthatók p₁,...,p_k-tól különböző prímszámmal. Az egészek egy véges A részhalmaza esetén jelöljük $\mathcal{G}(A)$ -val azt a gráfot, melynek csúcsai az A elemei, élei pedig azon a,b $\in$ A párok, melyekre a-b $\in$ S. Létezik-e minden m $\ge$ 3-ra egészeknek olyan m elemű A részhalmaza, melyre

(a) $\mathcal{G}(A)$ teljes?

(b) $\mathcal{G}(A)$ összefüggő, de minden csúcsának a fokszáma legfeljebb 2?

Schweitzer Miklós Matematikai Emlékverseny (2009)

(5 pont)

A beküldési határidő 2010. január 11-én LEJÁRT.

Megoldás. (a) A válasz: nem.

Legyen q a legkisebb olyan prím, ami nem szerepel p₁,...,p_k között. Ha |A|>q, akkor a skatulya-elv miatt A elemei között van kettő, aminek a különsége osztható q-val. Tehát m>q esetén $\mathcal{G}(A)$ nem lehet teljes.

(b) A válasz: igen.

Legyen $a_n=\sum_{i=1}^n (p_1p_2\cdots p_k)^i$ (n=1,2,...). A definíció szerint a_n+1-a_n=(p₁p₂^...p_k)ⁿ⁺¹ $\in$ S.

Megmutatjuk hogy N $\ge$ n+1 esetén $a_N-a_n\not\in S$ . A definícióból

$a_N-a_n = (p_1p_2\cdots p_k)^{n+1} + (p_1p_2\cdots p_k)^{n+2} + \ldots + (p_1p_2\cdots p_k)^N.$

Az összes tag osztható p_iⁿ⁺²-gyel, kivéve az elsőt. A teljes összeg tehát nem osztható p_iⁿ⁺²-vel. Az legnagyobb S-beli szám, ami osztója (a_N-a_n)-nek, az (p₁p₂^...p_k)ⁿ⁺¹, ami kisebb, mint a_N-a_n.

Az $A=\{a_1,a_2,\ldots,a_m\}$ halmaz esetén tehát a $\mathcal{G}(A)$ gráf egy m csúcsú út.

Statisztika:

11 dolgozat érkezett.

5 pontot kapott: Backhausz Tibor, Bodor Bertalan, Éles András, Frankl Nóra, Mester Márton, Nagy 235 János, Nagy 648 Donát, Somogyi Ákos, Weisz Ágoston.

2 pontot kapott: 1 versenyző.

0 pontot kapott: 1 versenyző.

A KöMaL 2009. decemberi matematika feladatai

11 dolgozat érkezett.
5 pontot kapott:	Backhausz Tibor, Bodor Bertalan, Éles András, Frankl Nóra, Mester Márton, Nagy 235 János, Nagy 648 Donát, Somogyi Ákos, Weisz Ágoston.
2 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

Már regisztráltál?
Új vendég vagy?