Maths Olympiad Prep

Library / /34 of 57

Algebra Difficulty 6.9 National olympiad Prove it Russia

We say that a non-empty set AA consisting of positive integers is complete if for any positive integers aa and bb such that a+bAa+b \in A, the number abab also lies in AA (the numbers aa and bb are not required to be distinct or to belong to AA). Find all complete sets.

Назовём непустое (конечное или бесконечное) множество AA, состоящее из натуральных чисел, полным, если для любых натуральных aa и bb (не обязательно различных и не обязательно лежащих в AA) таких, что a+ba+b лежит в AA, число abab также лежит в AA. Найдите все полные множества натуральных чисел.

Solutions — 2

Solution 1

The set of all positive integers, along with {1}\{1\}, {1,2}\{1, 2\}, {1,2,3}\{1, 2, 3\}, and {1,2,3,4}\{1, 2, 3, 4\}.

First, we check that the sets {1}\{1\}, {1,2}\{1, 2\}, {1,2,3}\{1, 2, 3\}, {1,2,3,4}\{1, 2, 3, 4\}, and the set of all positive integers are complete. For the last set, this is obvious; for the first four, note that if positive integers aa and bb are such that a+b4a+b \le 4, then either both are 22, or one of them is 11; in any of these cases, we have aba+bab \le a+b. Thus, if a+bAa+b \in A, then abAab \in A.

Now let AA be an arbitrary complete set. If AA contains some number k2k \ge 2, then by the condition it also contains the number 1(k1)=k11 \cdot (k-1) = k-1. Continuing this process, we obtain that all positive integers not exceeding kk lie in AA. In particular, if AA does not contain numbers greater than 44, then the set AA is already listed in the answer.

Now suppose AA contains a number 5\ell \ge 5. Define a sequence 1,2,\ell_1, \ell_2, \dots by 1=\ell_1 = \ell, n+1=2(n2)\ell_{n+1} = 2(\ell_n - 2). All these numbers lie in AA. Indeed, 1\ell_1 lies in AA by our assumption, and if n=2+(n2)A\ell_n = 2 + (\ell_n - 2) \in A, then n+1=2(n2)A\ell_{n+1} = 2(\ell_n - 2) \in A. Moreover, n+1=n+(n4)\ell_{n+1} = \ell_n + (\ell_n - 4); by induction, we now get that n+1>n5\ell_{n+1} > \ell_n \ge 5. Thus, for any positive integer nn we have n>n\ell_n > n; from the reasoning of the previous paragraph, we now see that nAn \in A. Therefore, all positive integers lie in AA.

Solution 2

Множество всех натуральных чисел, а также множества {1},{1,2},{1,2,3}\{1\}, \{1,2\}, \{1,2,3\} и {1,2,3,4}\{1,2,3,4\}.

Для начала проверим, что множества {1},{1,2},{1,2,3},{1,2,3,4}\{1\}, \{1,2\}, \{1,2,3\}, \{1,2,3,4\}, а также множество всех натуральных чисел — полные. Для последнего множества это очевидно; для первых четырёх заметим, что если натуральные числа aa и bb таковы, что a+b4a+b \le 4, то либо они оба равны 22, либо одно из них равно 11; в любом из этих случаев имеем aba+bab \le a+b. Значит, если a+bAa+b \in A, то и abAab \in A.

Пусть теперь AA — произвольное полное множество. Если AA содержит некоторое число k2k \ge 2, то по условию оно также содержит число 1(k1)=k11 \cdot (k-1) = k-1. Продолжая этот процесс, получаем, что все натуральные числа, не превосходящие kk, лежат в AA. В частности, если AA не содержит чисел, больших 44, то множество AA уже перечислено в ответе.

Пусть теперь в AA есть число 5\ell \ge 5. Зададим последовательность 1,2,\ell_1, \ell_2, \dots соотношениями 1=,n+1=2(n2)\ell_1 = \ell, \ell_{n+1} = 2(\ell_n - 2). Все эти числа лежат в AA. Действительно, 1\ell_1 лежит в AA по нашему предположению, а если n=2+(n2)A\ell_n = 2+(\ell_n-2) \in A, то и n+1=2(n2)A\ell_{n+1} = 2(\ell_n-2) \in A. Кроме того, n+1=n+(n4)\ell_{n+1} = \ell_n + (\ell_n - 4); по индукции теперь получаем, что n+1>n5\ell_{n+1} > \ell_n \ge 5. Значит, для любого натурального nn имеем n>n\ell_n > n; из рассуждений предыдущего абзаца понимаем теперь, что и nAn \in A. Итак, все натуральные числа лежат в AA.

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.