AMC10 2013 10B, Problem 25

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$?

Solution: First, we can examine the units digits of the number base 5 and base 6 and eliminate some possibilities. Say that $N \equiv a \pmod{6}$ also that $N \equiv b \pmod{5}$ Substituting these equations into the question and setting the units digits of $2N$ and $S$ equal to each other, it can be seen that $b < 5$ (because otherwise $a$ and $b$ will have different parities), and thus $a=b$. $N \equiv a \pmod{6}$, $N \equiv  a \pmod{5}$, $\implies N=a \pmod{30}$, $0 \le a \le 4$ Therefore, $N$ can be written as  $30x+y$ and $2N$ can be written as $60x+2y$ Just keep in mind that $y$ can be one of five choices: $0, 1, 2, 3,$ or $4$, ; Also, we have already found which digits of $y$ will add up into the units digits of $2N$. Now, examine the tens digit, $x$ by using $\mod{25}$ and $\mod{36}$ to find the tens digit (units digits can be disregarded because $y=0,1,2,3,4$ will always work) Then we take $N=30x+y$ $\mod{25}$ and $\mod{36}$ to find the last two digits in the base $5$ and $6$ representation. \[N \equiv 30x \pmod{36}\] \[N \equiv 30x \equiv 5x \pmod{25}\] Both of those must add up to \[2N\equiv60x \pmod{100}\] ($33 \ge x \ge 4$) Now, since $y=0,1,2,3,4$ will always work if $x$ works, then we can treat $x$ as a units digit instead of a tens digit in the respective bases and decrease the mods so that $x$ is now the units digit. \[N \equiv 5x \pmod{6}\] \[N \equiv 6x \equiv x \pmod{5}\] \[2N\equiv 6x \pmod{10}\] Say that $x=5m+n$ (m is between 0-6, n is 0-4 because of constraints on x) Then \[N \equiv 5m+n \pmod{5}\] \[N \equiv 25m+5n \pmod{6}\] \[2N\equiv30m + 6n \pmod{10}\] and this simplifies to \[N \equiv n \pmod{5}\] \[N \equiv m+5n \pmod{6}\] \[2N\equiv 6n \pmod{10}\] From careful inspection, this is true when $n=0, m=6$ $n=1, m=6$ $n=2, m=2$ $n=3, m=2$ $n=4, m=4$ This gives you $5$ choices for $x$, and $5$ choices for $y$, so the answer is $5* 5 = \fbox{25}$

Answer: 25