Competition problem — Number theory

Library / /4 of 18

Number theory Difficulty 6.3 National olympiad Prove it Argentina

The vertices of a regular hexagon are marked on a blackboard. Ana draws some segments that are either sides or diagonals of the hexagon, in any way she wants to (she can even decide not to draw any segment at all, or to draw the 15 possible segments).
Afterwards, Beto writes a positive integer on each vertex, in such a way that the following condition is satisfied: if two vertices are connected by a segment drawn by Ana, then the corresponding numbers must have a common divisor greater than 1; otherwise, if they are not connected by a segment, the numbers must not have any common divisor greater than 1.

a. Show that Beto can always complete his task.

b. Once Beto completes his task, he must pay Ana $M$ pesos, where $M$ is the greatest of the 6 numbers that Beto wrote. Beto wants to pay as least as possible and Ana wants to get paid the greatest possible amount of pesos. Can Ana draw the segments in such a way that she is guaranteed to receive more than 2023 pesos?

Solution

a. Beto can proceed as follows. First he picks a unique prime number for each segment drawn by Ana, and he assigns that prime number to both endpoints of this segment. Then, the number he writes on each vertex is the product of all prime numbers assigned to that vertex (if there are none, we consider the product to be 1). This implies that the numbers on vertices joined by a segment will both be divisible by the prime number corresponding to that segment, while numbers on vertices which are not joined by a segment will not have any common prime divisor, since the prime numbers corresponding to the segments are all different.

b. Suppose Ana draws the segments shown in the figure. The number on vertex A must share a prime factor with each of the other 5 numbers, and these prime factors must be different, because there are no segments between the other 5 vertices, which means that the corresponding numbers are pairwise relatively prime. So A must have at least 5 prime factors, which implies $A \ge 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 = 2310 > 2023$ .

Comment: The lower bound can be improved if Ana draws these segments instead.

In this situation, both A and B must have at least 4 prime factors, and they can't share any of those prime factors.

Therefore, their product $A \cdot B$ has at least 8 prime factors, which implies $A \cdot B \ge 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 23 = 11741730$ , and hence $\max\{A, B\}$ is greater or equal than $\sqrt{11741730} \approx 3426.62$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.