Library / /23 of 91

, 2013

Algebra Difficulty 5.4 AIME, harder Prove it India

Let $h \ge 3$ be an integer and $X$ the set of all positive integers that are greater than or equal to $2h$ . Let $S$ be a nonempty subset of $X$ such that the following two conditions hold:
* if $a + b \in S$ with $a \ge h, b \ge h$ , then $ab \in S$ ;
* if $ab \in S$ with $a \ge h, b \ge h$ , then $a+b \in S$ .

Prove that $S = X$ .

Solution

Let $f: X \to \{0, 1\}$ be such that $f(x) = 1$ if and only if $x \in S$ . Then $f(a+b) = f(ab)$ whenever $a \ge h, b \ge h$ . If $a \ge h+2$ then
$f(2a - 1) = f(a^2 - a) = f(a^3 - 2a^2) = f(a^2 + a - 2) = f(2a + 1).$
Given $n \ge 2h$ , it is easy to see that there exists an $a \ge h+2$ such that $f(n) = f(2a-1)$ . This proves that $f$ is constant and hence $S = X$ . $\square$

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 reproduced verbatim; metadata (topic, difficulty) added by this project.