Maths Olympiad Prep

Track / Stage 6 / 38 of 400 #1038 of 1964

Problem 1038

National olympiad, first round
Number theory Difficulty 6.0 Prove it

Can 153115 \cdot 31 divide the set of integers into 3 subsets such that for any integer nn, nn, n50n-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.

Official solution

[Solution] We prove that it is impossible to divide the set of integers into 3 subsets such that n,n50,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":
(n50,n,n+1987),(n100,n50,n+1937)(n+1937,n+1987,n+21987). \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 iji \sim j to indicate that the integer ii and the integer jj belong to the same subset, and the notation iji \propto j to indicate that the integer ii and the integer jj do not belong to the same subset.
From (2) we know
n+1937n50 n+1937 \propto n-50 \text {, }

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

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

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

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

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

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

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

From (4) and (7) we get
0193721937501937=646150506451505050. \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 0500 \sim-50, i.e., when n=0n=0, nn and n50n-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 and solution reproduced as published; topic, difficulty and ordering added by this site.