Olimpiadi di Matematica - Febbraio

Solution:

a. Suppose for contradiction that there exists a positive integer that is doubly reversible of type 2. It is written as $x x$ in some base $b$ and as $y y$ in base $b+1$. By definition of the representation of a number in a base, we must have
$$x \cdot b^{1}+x \cdot b^{0}=y \cdot(b+1)^{1}+y \cdot(b+1)^{0},$$
where $0<x<b$ and $0<y<b+1$. Rewriting, we have
$$x(b+1)=y(b+2),$$
from which we see that $b+2$ divides $x(b+1)$. Since $b+2$ and $b+1$, being consecutive integers, have no common prime factors, $b+2$ must also divide $x$, but this contradicts the inequality $0<x<b$.

b. We look for a doubly reversible number of type 3 by writing it as $x y x$ in base $b$ and as $u v u$ in base $b+1$. As above, this leads us to the equality
$$x \cdot b^{2}+y \cdot b+x \cdot b^{0}=u \cdot(b+1)^{2}+v \cdot(b+1)+u \cdot(b+1)^{0}$$
which we rewrite as
$$x \cdot b^{2}+y \cdot b+x \cdot b^{0}=u \cdot b^{2}+(2 u+v) \cdot b+(2 u+v) \cdot b^{0} .$$
Thinking now about the uniqueness of the representation in base $b$, we observe that if there were no carries in the computation of $2 u+v$ in base $b$, that is, if $2 u+v<b$ held, then the digits of our number in base $b$ would be both $x, y, x$ and $u, 2 u+v, 2 u+v$, but this would force $x=u=2 u+v$, hence $u=v=0$, which does not correspond to a positive integer. We conclude therefore that there must be a carry in order for the equality above to be possible, and we thus try asking ourselves what happens if this carry is the smallest possible, that is, if $2 u+v$ is greater than $b$ but less than $2 b$. Actually, for a reason we will see in a moment, it is convenient to focus on the case in which $2 u+v \leq 2 b-2$. Indeed, in that case it is easy to determine exactly the carries and rewrite $u \cdot b^{2}+(2 u+v) \cdot b+(2 u+v) \cdot b^{0}$ in the form
$$(u+1) \cdot b^{2}+(2 u+v+1-b) \cdot b+(2 u+v-b) \cdot b^{0}$$
where $2 u+v+1-b$ comes from having added the carry of 1 from the units digit and then subtracted the quantity $b$, which is carried over to the digit corresponding to $b^{2}$. The condition $2 u+v \leq 2 b-2$ guarantees that $2 u+v+1-b \leq b-1$, that is, that there are no further carries. We are then looking for a number that in base $b$ is written both with the digits $x, y, x$, and with the digits $u+1,2 u+v+1-b, 2 u+v-b$. Imposing the equality of these digits we obtain the system
$$\left\{\begin{array}{l} x=u+1 \\ y=2 u+v+1-b \\ x=2 u+v-b \end{array}\right.$$
The difference of the second and third equations gives $y-x=1$, that is, $y=x+1$. The comparison between the first and third equations instead gives $u+1=2 u+v-b \Rightarrow b=u+v-1$. We can then choose (somewhat arbitrarily) $u=2, v=b-1, x=u+1=3, y=x+1=4$, which leads us to consider the number $343_{b}=2(b-1) 2_{b+1}$ (where the notation to the right of the equal sign denotes the number that, in base $b+1$, is written with the digits $2, b-1,2$). That this equality is satisfied follows from the considerations that led us to write it, but it is also easy to verify it directly:
$$\begin{gathered} 343_{b}=3 b^{2}+4 b+3 \\ 2(b-1) 2_{b+1}=2(b+1)^{2}+(b-1)(b+1)+2=2\left(b^{2}+2 b+1\right)+b^{2}-1+2 \\ =2 b^{2}+4 b+2+b^{2}-1+2=3 b^{2}+4 b+3 \end{gathered}$$
We have thus constructed infinitely many doubly reversible numbers of type 3: they are all those that, in any base $b \geq 2$, are written as 343.