Maths Olympiad Prep

Track / Stage 6 / 68 of 400 #1068 of 1964

Problem 1068

National Olympiad, first round
Number theory Difficulty 6.0 Prove it

(30th Russian Mathematical Olympiad) Can a positive integer be written at each integer point in the plane so that three integer points are collinear if and only if the 3 positive integers written on them have a common divisor greater than 1?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

It cannot be done. Assume it can be done. Now consider an integer point AA, assume it is labeled with a positive integer aa. Let aa have nn distinct prime factors.

Take another integer point A1A_{1} in the plane. Clearly, there are other integer points B1B_{1} on the line AA1A A_{1}, for example, B1B_{1} can be taken as the symmetric point of AA with respect to A1A_{1}.

Since the 3 numbers written on A,A1,B1A, A_{1}, B_{1} have a common divisor greater than 1, they can all be divided by some prime p1p_{1}. In particular, p1ap_{1} \mid a.
Take another integer point A2A_{2} in the plane, such that A2A_{2} is not on the line AA1A A_{1}.
There are other integer points B2B_{2} on the line AA2A A_{2}, the 3 numbers written on A,A2,B2A, A_{2}, B_{2} can all be divided by some prime p2p_{2}. In particular, p2ap_{2} \mid a.
Since A,A1,A2A, A_{1}, A_{2} are not collinear, p1p2p_{1} \neq p_{2}. Continue this process to construct lines AA3,AA4,,AAn+1A A_{3}, A A_{4}, \cdots, A A_{n+1}, each time obtaining a new prime that can divide aa, resulting in a total of n+1n+1 distinct primes, all of which can divide aa. This contradicts the assumption that aa has only nn distinct prime factors.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.