Track / Stage 6 / 183 of 400 #1183 of 2000

Problem 1183

National olympiad, first round

Number theory Difficulty 6.3 Prove it

Exercise 3. For any integer $n \in \mathbb{N}^{*}$ , we denote $v_{3}(n)$ as the 3-adic valuation of $n$ , which is the greatest integer $k$ such that $n$ is divisible by $3^{k}$ . We set $u_{1}=2$ and $u_{n}=4 v_{3}(n)+2-\frac{2}{u_{n-1}}$ for all $n \geqslant 2$ (provided that $u_{n-1}$ is defined and non-zero).

Show that, for any positive rational number $q$ , there exists a unique integer $n \geqslant 1$ such that $u_{n}=q$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

## Solution to Exercise 3

First, note that $u_{1}=2, u_{2}=1, u_{3}=3, u_{4}=\frac{3}{2}, u_{5}=\frac{2}{3}$ and $u_{6}=3$ . We prove by induction that, for all integers $n \geq 2$ , we have $00$ , we set $\left\|\frac{p}{q}\right\|=p+q$ . Then:

- $\left\|\varphi\left(\frac{p}{q}\right)\right\|=\left\|\frac{p}{q-p}\right\|=p<p+q=\left\|\frac{p}{q}\right\|$ if $0<p<q$ ;
- $\left\|\varphi\left(1+\frac{p}{q}\right)\right\|=\left\|2 \frac{p}{q-p}\right\| \leq 2 q<(p+q)+q=\left\|1+\frac{p}{q}\right\|$ if $0<p<q$ ;
- $\left\|\varphi\left(2+\frac{p}{q}\right)\right\|=\left\|\frac{p}{q}\right\|=p+q<(p+2 q)+q=\left\|2+\frac{p}{q}\right\|$ if $0<p$ and $0<q$ .

In all cases, if $x$ is a strictly positive rational number such that $x \notin\{1,2\}$ , we have $\|\varphi(x)\|<\|x\|$ . Now, for all strictly positive rational numbers $x$ and for all integers $n \geq 1$ :

- if $0<x<1$ , then $u_{n}=\varphi(x) \Leftrightarrow u_{3 n+2}=x$ ;
- if $1<x<2$ , then $u_{n}=\varphi(x) \Leftrightarrow u_{3 n+1}=x$ ;
- if $2<x$ , then $u_{n}=\varphi(x) \Leftrightarrow u_{3 n}=x$ .

An induction on $\|x\|$ immediately shows that, for all strictly positive rational numbers $x$ , there exists a unique integer $n \geq 1$ such that $u_{n}=x$ , which concludes the exercise.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.