# Problem A. 494. (December 2009)

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

*Miklós Schweitzer Memorial Competition,* 2009

(5 pont)

**Deadline expired on January 11, 2010.**

**Solution.** (a) NO.

Let *q* be the least prime which is not listed among *p*_{1},...,*p*_{k}.

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, cannot be complete if |*A*|>*q*.

(b) YES.

Let (*n*=1,2,...). By the definition, *a*_{n+1}-*a*_{n}=(*p*_{1}*p*_{2}^{...}*p*_{k})^{n+1}*S*.

We show that for any *N**n*+1. By the definition.

For each *i*, all terms are divisible by *p*_{i}^{n+2}, except the first one. Hence, the complete sum is not divisible by *p*_{i}^{n+2}-vel; the greates element of *S*, which divides *a*_{N}-*a*_{n} is (*p*_{1}*p*_{2}^{...}*p*_{k})^{n+1}, less than *a*_{N}-*a*_{n}.

Therefore, for the choice , the graph is a simple path.

### Statistics:

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