**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 points)

**Deadline expired on 11 January 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.