Number theoryDifficulty 6.8National OlympiadProve itItaly
Problem:
A positive integer n is called doubly reversible of type ℓ if there exist two consecutive bases b and b+1 such that n is represented by palindromic numbers of ℓ digits both in base b and in base b+1. For example, 104 is doubly reversible of type 3 because 10410=4045=2526.
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 xx in some base b and as yy in base b+1. By definition of the representation of a number in a base, we must have x⋅b1+x⋅b0=y⋅(b+1)1+y⋅(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 xyx in base b and as uvu in base b+1. As above, this leads us to the equality x⋅b2+y⋅b+x⋅b0=u⋅(b+1)2+v⋅(b+1)+u⋅(b+1)0 which we rewrite as x⋅b2+y⋅b+x⋅b0=u⋅b2+(2u+v)⋅b+(2u+v)⋅b0. Thinking now about the uniqueness of the representation in base b, we observe that if there were no carries in the computation of 2u+v in base b, that is, if 2u+v<b held, then the digits of our number in base b would be both x,y,x and u,2u+v,2u+v, but this would force x=u=2u+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 2u+v is greater than b but less than 2b. Actually, for a reason we will see in a moment, it is convenient to focus on the case in which 2u+v≤2b−2. Indeed, in that case it is easy to determine exactly the carries and rewrite u⋅b2+(2u+v)⋅b+(2u+v)⋅b0 in the form (u+1)⋅b2+(2u+v+1−b)⋅b+(2u+v−b)⋅b0 where 2u+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 b2. The condition 2u+v≤2b−2 guarantees that 2u+v+1−b≤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,2u+v+1−b,2u+v−b. Imposing the equality of these digits we obtain the system ⎩⎨⎧x=u+1y=2u+v+1−bx=2u+v−b 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=2u+v−b⇒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 343b=2(b−1)2b+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: 343b=3b2+4b+32(b−1)2b+1=2(b+1)2+(b−1)(b+1)+2=2(b2+2b+1)+b2−1+2=2b2+4b+2+b2−1+2=3b2+4b+3 We have thus constructed infinitely many doubly reversible numbers of type 3: they are all those that, in any base b≥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.