Maths Olympiad Prep

Track / Stage 6 / 56 of 400 #1056 of 1964

Problem 1056

National Olympiad, first round
Number theory Difficulty 6.0 Prove it

Can 15⋅3115 \cdot 31 divide the set of integers into 3 subsets such that for any integer nn, nn, n−50n-50, and n+1987n+1987 belong to 3 different subsets?
(50th Moscow Mathematical Olympiad, 1987)

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

[Solution] We prove that it is impossible to divide the set of integers into 3 subsets such that n,n−50,n+1987n, n-50, n+1987 belong to 3 different subsets, where nn is any integer.

If a 3-tuple of 3 numbers each comes from 3 different subsets, then we call this 3-tuple "representative."

Assume there exists a partition that meets the requirements of the problem, then for any integer nn, the following 3-tuples are "representative":
(n−50,n,n+1987),(n−100,n−50,n+1937)(n+1937,n+1987,n+2⋅1987). \begin{array}{l} (n-50, \quad n, \quad n+1987), \\ (n-100, \quad n-50, \quad n+1937) \\ (n+1937, \quad n+1987, \quad n+2 \cdot 1987) . \end{array}

We use the notation i∼ji \sim j to indicate that the integer ii and the integer jj belong to the same subset, and the notation i∝ji \propto j to indicate that the integer ii and the integer jj do not belong to the same subset.
From (2) we know
n+1937∝n−50,  n+1937 \propto n-50 \text {, }

From (3) we know
n+1937∝n+1987 n+1937 \propto n+1987

From (1) we know
n∝n−50,n∝n+1987. \begin{array}{r} n \propto n-50, \\ n \propto n+1987 . \end{array}

Thus, it can only be that
n∼n+1937.  n \sim n+1937 \text {. }

From (2), by replacing n+1937n+1937 with nn, we get another "representative" 3-tuple
(n−100,n−50,n).  (n-100, n-50, n) \text {. }

We can also get (by replacing nn with n−50n-50)
(n−150,n−100,n−50).  (n-150, \quad n-100, \quad n-50) \text {. }

which is also a "representative" tuple.
Thus, from (5) and (6) we know
n∝n−50,n∝n−100,  n \propto n-50, \quad n \propto n-100 \text {, }

Thus, it can only be that
n∼n−150.  n \sim n-150 \text {. }

From (4) and (7) we get
0∼1937∼2⋅1937∼⋯∼50⋅1937=646⋅150−50∼645⋅150−50∼⋯∼−50. \begin{array}{c} 0 \sim 1937 \sim 2 \cdot 1937 \sim \cdots \sim 50 \cdot 1937 \\ =646 \cdot 150-50 \sim 645 \cdot 150-50 \sim \cdots \sim-50 . \end{array}

Thus 0∼−500 \sim-50, i.e., when n=0n=0, nn and n−50n-50 belong to the same subset, leading to a contradiction. Therefore, there cannot be a partition that meets the requirements of the problem.

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