Browse · MathNet
PrintRioplatense Mathematical Olympiad
Argentina number theory
Problem
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 pesos, where 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?
a. Show that Beto can always complete his task.
b. Once Beto completes his task, he must pay Ana pesos, where 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 .
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 has at least 8 prime factors, which implies , and hence is greater or equal than .
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 .
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 has at least 8 prime factors, which implies , and hence is greater or equal than .
Final answer
Yes
Techniques
Prime numbersGreatest common divisors (gcd)Coloring schemes, extremal arguments