Maths Olympiad Prep

Library / /9 of 10

Number theory Difficulty 6.8 National Olympiad Prove it Italy

Problem:

A positive integer nn is called doubly reversible of type \ell if there exist two consecutive bases bb and b+1b+1 such that nn is represented by palindromic numbers of \ell digits both in base bb and in base b+1b+1. For example, 104 is doubly reversible of type 3 because 10410=4045=2526104_{10}=404_{5}=252_{6}.

a. Prove that there are no doubly reversible numbers of type 2.

b. Prove that there exist infinitely many doubly reversible numbers of type 3.

Solution

Solution:

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

b. We look for a doubly reversible number of type 3 by writing it as xyxx y x in base bb and as uvuu v u in base b+1b+1. As above, this leads us to the equality
xb2+yb+xb0=u(b+1)2+v(b+1)+u(b+1)0 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
xb2+yb+xb0=ub2+(2u+v)b+(2u+v)b0. 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 bb, we observe that if there were no carries in the computation of 2u+v2 u+v in base bb, that is, if 2u+v<b2 u+v<b held, then the digits of our number in base bb would be both x,y,xx, y, x and u,2u+v,2u+vu, 2 u+v, 2 u+v, but this would force x=u=2u+vx=u=2 u+v, hence u=v=0u=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 2u+v2 u+v is greater than bb but less than 2b2 b. Actually, for a reason we will see in a moment, it is convenient to focus on the case in which 2u+v2b22 u+v \leq 2 b-2. Indeed, in that case it is easy to determine exactly the carries and rewrite ub2+(2u+v)b+(2u+v)b0u \cdot b^{2}+(2 u+v) \cdot b+(2 u+v) \cdot b^{0} in the form
(u+1)b2+(2u+v+1b)b+(2u+vb)b0 (u+1) \cdot b^{2}+(2 u+v+1-b) \cdot b+(2 u+v-b) \cdot b^{0}
where 2u+v+1b2 u+v+1-b comes from having added the carry of 1 from the units digit and then subtracted the quantity bb, which is carried over to the digit corresponding to b2b^{2}. The condition 2u+v2b22 u+v \leq 2 b-2 guarantees that 2u+v+1bb12 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 bb is written both with the digits x,y,xx, y, x, and with the digits u+1,2u+v+1b,2u+vbu+1,2 u+v+1-b, 2 u+v-b. Imposing the equality of these digits we obtain the system
{x=u+1y=2u+v+1bx=2u+vb \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 yx=1y-x=1, that is, y=x+1y=x+1. The comparison between the first and third equations instead gives u+1=2u+vbb=u+v1u+1=2 u+v-b \Rightarrow b=u+v-1. We can then choose (somewhat arbitrarily) u=2,v=b1,x=u+1=3,y=x+1=4u=2, v=b-1, x=u+1=3, y=x+1=4, which leads us to consider the number 343b=2(b1)2b+1343_{b}=2(b-1) 2_{b+1} (where the notation to the right of the equal sign denotes the number that, in base b+1b+1, is written with the digits 2,b1,22, 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:
343b=3b2+4b+32(b1)2b+1=2(b+1)2+(b1)(b+1)+2=2(b2+2b+1)+b21+2=2b2+4b+2+b21+2=3b2+4b+3 \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 b2b \geq 2, are written as 343.

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: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty) added by this project.