Maths Olympiad Prep

Library / /194 of 520

Number theory Difficulty 5.9 AIME, harder Prove it

Theorem 1 For any nNn \in \boldsymbol{N}, we have nn+n \neq n^{+}.

Solution

Let the subset of elements nn in N\boldsymbol{N} for which nn+n \neq n^{+} holds be denoted as SS. By axiom (ii), we know ee+e \neq e^{+}, so eSe \in S, and SS is non-empty. If nSn \in S, i.e., nn+n \neq n^{+}, we will prove that it must be the case that n+Sn^{+} \in S. If not, then we would have n+=(n+)+n^{+}=\left(n^{+}\right)^{+}. From this and axiom (iii), it follows that n=n+n=n^{+}, which is a contradiction. Therefore, by the induction axiom (iv), we conclude S=NS=N. Proof completed.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.