The number $1$ is written on the blackboard. At any point, Kornny may pick two (not necessary distinct) of the numbers $a$ and $b$ written on the board and write either $ab$ or $\frac{1}{a}+\frac{1}{b}+\frac{1}{ab}$ on the board as well. Determine all possible numbers that Kornny can write on the board in finitely many steps.
Problem
Source: 2022 Thailand Online MO P9
Tags: number theory
04.04.2022 13:30
Obviously, all number on the board must be positive rational number. Claim 1: All number that cannot be expressed as $\frac{p}{q}$ with odd positive integers $p,q$ cannnot be on the board. Proof. If Korny choose $\frac{p}{q}$ and $\frac{r}{s}$ with odd positive integers $p,q,r,s$ then he can write $\frac{pr}{qs}$ or $\frac{qr+ps+qs}{pr}$ which are both $\frac{\text{odd}}{\text{odd}}$. Since we start off with $\frac{1}{1}$ which is $\frac{\text{odd}}{\text{odd}}$, every number on the board must be $\frac{\text{odd}}{\text{odd}}$. $\blacksquare$ Claim 2: Every odd positive integers can be on the board. Proof. Define functions $f,g:\mathbb{Q}^{+}\to\mathbb{Q}^{+}$ so that $$f(p,q)=pq\quad\text{ and }\quad g(p,q)=\frac{1}{p}+\frac{1}{q}+\frac{1}{pq}$$for every positive rational numbers $p,q$ that can be on the board. Obviously, if both $p$ and $q$ can be on the board then $f(p,q)$ and $g(p,q)$ can be on the board. Let $m$ be a number that can be on the board. We have $$g(m,1)=\frac{m+2}{m}\quad,\quad f(m,\frac{m+2}{m})=m+2 \ .$$If $m$ can be on the board then $m+2$ can be on the board. By induction, all odd postive integers can be on the board. $\blacksquare$ Claim 3: $\frac{1}{4k+3}$ can be on the board for every $k\geq 0$. Proof. Since all odd positive integers can be on the board, we have $$g(12k+9, 6k+5)=\frac{1}{4k+3} \ . \ \blacksquare$$ Claim 4: $\frac{1}{4k+1}$ can be on the board for every $k\geq 0$. Since every odd positive integers and $\frac{1}{4k+3}$ can be on the board, we have $$g(1, 4k+1)=\frac{4k+3}{4k+1}\quad ,\quad f(\frac{4k+3}{4k+1}, \frac{1}{4k+3})=\frac{1}{4k+1} \ . \ \blacksquare$$ Claim 5: All number that can be expressed as $\frac{p}{q}$ with odd positive integers $p,q$ can be on the board. Proof. By our claim 3 and claim 4, $\frac{1}{\text{odd}}$ can be on the board. For every $c,d\geq 0$, we have $$f(2c+1, \frac{1}{2d+1})=\frac{2c+1}{2d+1} \ . \ \blacksquare$$