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 the graph whose vertices are the elements of A, and the edges are those pairs a,bA for which a-bS. Does there exist for all m3 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
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, cannot be complete if |A|>q.
Let (n=1,2,...). By the definition, an+1-an=(p1p2...pk)n+1S.
We show that for any Nn+1. By the definition.
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 , the graph is a simple path.