KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

A. 494. Let p1,...,pk be prime numbers, and let S be the set of those integers whose all prime divisors are among p1,...,pk. For a finite subset A of the integers let us denote by \mathcal{G}(A) the graph whose vertices are the elements of A, and the edges are those pairs a,b\inA for which a-b\inS. Does there exist for all m\ge3 an m-element subset A of the integers such that (a\mathcal{G}(A) is complete? (b\mathcal{G}(A) is connected, but all vertices have degree at most 2?

Miklós Schweitzer Memorial Competition, 2009

(5 points)

Deadline expired on 11 January 2010.


Solution. (a) NO.

Let q be the least prime which is not listed among p1,...,pk.

If |A|>q then A has two element which are congruent modulo q. Their difference is divisible q, so these elements are not connected.

Therefore, \mathcal{G}(A) cannot be complete if |A|>q.

(b) YES.

Let a_n=\sum_{i=1}^n (p_1p_2\cdots p_k)^i (n=1,2,...). By the definition, an+1-an=(p1p2...pk)n+1\inS.

We show that a_N-a_n\not\in S for any N\gen+1. By the definition.


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.

For each i, all terms are divisible by pin+2, except the first one. Hence, the complete sum is not divisible by pin+2-vel; the greates element of S, which divides aN-an is (p1p2...pk)n+1, less than aN-an.

Therefore, for the choice A=\{a_1,a_2,\ldots,a_m\}, the graph \mathcal{G}(A) is a simple path.


Statistics on problem A. 494.
11 students sent a solution.
5 points: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 points:1 student.
0 point:1 student.


  • Problems in Mathematics of KöMaL, December 2009

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley