Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az A. 494. feladat (2009. december)

A. 494. Legyenek p1,...,pk prímszámok, és legyen S az egész számok azon részhalmaza, melynek elemei nem oszthatók p1,...,pk-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\inA párok, melyekre a-b\inS. Létezik-e minden m\ge3-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 p1,...,pk 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 an+1-an=(p1p2...pk)n+1\inS.

Megmutatjuk hogy N\gen+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ó pin+2-gyel, kivéve az elsőt. A teljes összeg tehát nem osztható pin+2-vel. Az legnagyobb S-beli szám, ami osztója (aN-an)-nek, az (p1p2...pk)n+1, ami kisebb, mint aN-an.

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