Problem:
Bernardo chooses a three-digit positive integer N and writes both its base- 5 and base-6 representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-10 integers, he adds them to obtain an integer S. For example, if N=749, Bernardo writes the numbers 10,444 and 3,245, and LeRoy obtains the sum S=13,689. For how many choices of N are the two rightmost digits of S, in order, the same as those of 2N ?
Answer Choices:
A. 5
B. 10
C. 15
D. 20
E. 25
Solution:
Expand the set of three-digit positive integers to include integers N,0≤N≤99, with leading zeros appended. Because lcm(52,62,102)=900, such an integer N meets the required condition if and only if N+900 does. Therefore N can be considered to be chosen from the set of integers between 000 and 899, inclusive. Suppose that the last two digits in order of the base- 5 representation of N are a1 and a0. Similarly, suppose that the last two digits of the base- 6 representation of N are b1 and b0. By assumption, 2N≡a0+b0 (mod10), but N≡a0(mod5) and so
a0+b0≡2N≡2a0(mod10)
Thus a0≡b0(mod10) and because 0≤a0≤4 and 0≤b0≤5, it follows that a0=b0. Because N≡a0(mod5), it follows that there is an integer N1 such that N=5N1+a0. Also, N≡a0(mod6) implies that 5N1+a0≡a0 (mod6) and so N1≡0(mod6). It follows that N1=6N2 for some integer N2 and so N=30N2+a0. Similarly, N≡5a1+a0(mod25) implies that 30N2+a0≡5a1+a0(mod25) and then N2≡6N2≡a1(mod5). It follows that N2=5N3+a1 for some integer N3 and so N=150N3+30a1+a0. Once more, N≡6b1+a0(mod36) implies that 6N3−6a1+a0≡150N3+30a1+a0≡6b1+a0 (mod36) and then N3≡a1+b1(mod6). It follows that N3=6N4+a1+b1 for some integer N4 and so N=900N4+180a1+150b1+a0. Finally, 2N≡ 10(a1+b1)+2a0(mod100) implies that
60a1+2a0≡360a1+300b1+2a0≡10a1+10b1+2a0(mod100)
Therefore 5a1≡b1(mod10), equivalently, b1≡0(mod5) and a1≡b1(mod2). Conversely, if N=900N4+180a1+150b1+a0,a0=b0, and 5a1≡b1(mod10),
then 2N≡60a1+2a0=10(a1+5a1)+a0+b0≡10(a1+b1)+(a0+b0) (mod100). Because 0≤a1≤4 and 0≤b1≤5, it follows that there are exactly 5 different pairs (a1,b1), namely (0,0),(2,0),(4,0),(1,5), and (3,5). Each of these can be combined with 5 different values of a0(0≤a0≤4), to determine exactly 25 different numbers N with the required property.
The problems on this page are the property of the MAA's American Mathematics Competitions