Maths Olympiad Prep

Library / /465 of 520

Number theory Difficulty 7.0 National olympiad, round 2 Prove it

Lemma 2 For any given nNn \in \boldsymbol{N}, there exists a unique mapping fnf_{n} from N\boldsymbol{N} to itself, satisfying
fn(e)=n+;f_{n}(e)=n^{+} ;

and for any mNm \in \boldsymbol{N}, we have
fn(m+)=(fn(m))+.f_{n}\left(m^{+}\right)=\left(f_{n}(m)\right)^{+} .

Solution

First, we prove the uniqueness. If there exists another such mapping gng_{n}, then when m=em=e, by equation (3) we get gn(e)=fn(e)=n+g_{n}(e)=f_{n}(e)=n^{+}. Assuming for some mNm \in N, gn(m)=fn(m)g_{n}(m)=f_{n}(m), then by equation (4) we get
gn(m+)=(gn(m))+=(fn(m))+=fn(m+)g_{n}\left(m^{+}\right)=\left(g_{n}(m)\right)^{+}=\left(f_{n}(m)\right)^{+}=f_{n}\left(m^{+}\right)

Therefore, by Theorem 3 of §1 (the principle of mathematical induction), for all mNm \in N, we have gn(m)=fn(m)g_{n}(m)=f_{n}(m). This proves the uniqueness.

Next, we prove the existence. When n=en=e, we define the mapping from NN to itself as
fe(m)=m+,mNf_{e}(m)=m^{+}, \quad m \in \mathbf{N}

It satisfies the requirements. In fact, since fe(e)=e+f_{e}(e)=e^{+}, condition (3) is satisfied. For any mNm \in \boldsymbol{N}, by definition (5) we get
fe(m+)=(m+)+=(fe(m))+,f_{e}\left(m^{+}\right)=\left(m^{+}\right)^{+}=\left(f_{e}(m)\right)^{+},

which means condition (4) is satisfied. Assuming such a mapping fnf_{n} exists for nn, for n+n^{+} we define the mapping from N\boldsymbol{N} to itself as
fn+(m)=(fn(m))+,mNf_{n}^{+}(m)=\left(f_{n}(m)\right)^{+}, \quad m \in \mathbf{N}

From this and the fact that the mapping fnf_{n} satisfies conditions (3) and (4), we derive
fn+(e)=(fn(e))+=(n+)+fn+(m+)=(fn(m+))+=((fn(m))+)+=(fn+(m))+\begin{aligned} & f_{n^{+}}(e)=\left(f_{n}(e)\right)^{+}=\left(n^{+}\right)^{+} \\ f_{n^{+}}\left(m^{+}\right)= & \left(f_{n}\left(m^{+}\right)\right)^{+}=\left(\left(f_{n}(m)\right)^{+}\right)^{+}=\left(f_{n}^{+}(m)\right)^{+} \end{aligned}

This proves that the mapping fn+f_{n^{+}} satisfies conditions (3) and (4). Therefore, by the principle of mathematical induction (Theorem 3 of §1), for any nNn \in \boldsymbol{N}, there must exist a mapping fnf_{n} that satisfies conditions (3) and (4). 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.