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,bA for which abS. Does there exist for all m3 an melement 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 Nn+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:
