7
$\begingroup$

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


What I have tried:

First, I 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 $a=b$, and $b < 5$, so $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$

I see 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$.

I'm stuck here and how should I continue?

Help is appreciated!

Thanks!

Max0815

$\endgroup$
1
$\begingroup$

Let $I_5$ be the last two digits of $N$ in base 5 but treating it as a base 10 integer.

Let $I_6$ be the last two digits of $N$ in base 6 but treating it as a base 10 integer.

The largest number $I_5$ can be is 44. The largest number $I_6$ can be is 55. So this means that the sum of the two can be no bigger than 99. This implies that there is no overflow problem into the third digit when adding the two numbers. In fact no digit pair will ever carry into the next digit.The reason for this is the digit range of the base 5 number is 0-4 and the digit range of the base 6 number is 0-5. The sum of which is 0-9.

$I_5$ cycles every 25 numbers. $I_6$ cycles every 36 numbers. The last two digits of $N$ cycles every 100 numbers. The lcm of 25,36,and 100 is 900. This means that the numbers that will produce equality for the two right most digits of $2N$ and $S$ will be in a cycle of 900. The op has already shown that the numbers must be of the form $30x+y$ where $x,y\in\Bbb{N}\space|\space 0\le y\le 4$. Since digit matchings are independent. If a $30x$ number matches the tens digit for $2N$ and $S$ then all numbers $30x+y$ numbers (for the same $x$) will match both digits. Putting all of this together; only the tens digit of multiples of 30 of $N$ less than 900 have to be examined. The equation that we want to solve is this: $$I_5+I_6=2N\pmod{100}$$ $$equivalently$$ $$I_5+I_6=60x\pmod{100}$$ If we focus on the tens digit we can change the problem to this: $$x\pmod{5}+(6-x)\pmod{6}\equiv6x\pmod{10}\quad\quad\quad(1)$$ Then move the left most term to the right side: $$(6-x)\pmod{6}\equiv6x\pmod{10}-x\pmod{5}\quad\quad\quad(2)$$ What is good about equation (2) is that the result of the right side has the following 5 number sequence $\{0,5,0,5,0\}$. The left side of equation (2) is 0 when $x \pmod{6}\equiv0$. The right side of equation (2) is 5 when $x \pmod{6}\equiv1$. So now all we have to do is solve 5 Chinese remainder theorem problems $$\begin{matrix} 6a & 5b\\ 6a & 5b+2\\ 6a & 5b+4\\ 6a+1 & 5b+1\\ 6a+1 & 5b+3\\ \end{matrix}$$

The result is $x=30p+q$ where $q\in\{0,1,12,13,24\}$. In order to get the values for $N$, x has multiplied by 30 then added to y. So $$N=900p+30q+y$$ or the last two digits of $2N$ and $S$ are the same iff $$N\pmod{900}\equiv0,1,2,3,4,30,31,32,33,34,360,361,362,363,364,390,391,392,393,394,720,721,722,723,724$$

Edit: when I first saw this problem I misinterpreted it and thought that there were two $S$'s one for N and one for $2N$ and the goal was to get the last two digits of the $S$'s the same. I managed to solve that problem as well. The solution to that problem is below in case anyone is interested.

Let $F_5$ be the last two digits of $2N$ in base 5 but treating it as a base 10 integer.

Let $F_6$ be the last two digits of $2N$ in base 6 but treating it as a base 10 integer.

Our goal then is to find when $$I_5+I_6=F_5+F_6\quad (3)$$

With some simple algebra (3) can be rewritten as $$F_5-I_5=I_6-F_6 (4)$$

The chart directly below shows all possible values of $F_5$ and $I_5$ and the difference between them. (In order of $I_5$ values)

$$ \begin{array}{c|r|r} F_5 & I_5 & F_5-I_5\\ \hline 00 & 00 & 0\\ 02 & 01 & 1\\ 04 & 02 & 2\\ 11 & 03 & 8\\ 13 & 04 & 9\\ 20 & 10 & 10\\ 22 & 11 & 11\\ 24 & 12 & 12\\ 31 & 13 & 18\\ 33 & 14 & 19\\ 40 & 20 & 20\\ 42 & 21 & 21\\ 44 & 22 & 22\\ 01 & 23 & -22\\ 03 & 24 & -21\\ 10 & 30 & -20\\ 12 & 31 & -19\\ 14 & 32 & -18\\ 21 & 33 & -12\\ 23 & 34 & -11\\ 30 & 40 & -10\\ 32 & 41 & -9\\ 34 & 42 & -8\\ 41 & 43 & -2\\ 43 & 44 & -1\\ \end{array} $$

The chart directly below shows all possible values of $I_6$ and $F_6$ and the difference between them. (In order of $I_6$ values)

$$ \begin{array}{c|r|r} I_6 & F_6 & I_6-F_6\\ \hline 00 & 00 & 0\\ 01 & 02 & -1\\ 02 & 04 & -2\\ 03 & 10 & -7\\ 04 & 12 & -8\\ 05 & 14 & -9\\ 10 & 20 & -10\\ 11 & 22 & -11\\ 12 & 24 & -12\\ 13 & 30 & -17\\ 14 & 32 & -18\\ 15 & 34 & -19\\ 20 & 40 & -20\\ 21 & 42 & -21\\ 22 & 44 & -22\\ 23 & 50 & -27\\ 24 & 52 & -28\\ 25 & 54 & -29\\ 30 & 00 & 30\\ 31 & 02 & 29\\ 32 & 04 & 28\\ 33 & 10 & 23\\ 34 & 12 & 22\\ 35 & 14 & 21\\ 40 & 20 & 20\\ 41 & 22 & 19\\ 42 & 24 & 18\\ 43 & 30 & 13\\ 44 & 32 & 12\\ 45 & 34 & 11\\ 50 & 40 & 10\\ 51 & 42 & 9\\ 52 & 44 & 8\\ 53 & 50 & 3\\ 54 & 52 & 2\\ 55 & 54 & 1\\ \end{array} $$

Now we just have to match the difference values of the two charts using modular arithmetic. In the first chart the values cycle every 25 numbers so the rows of the first chart corresponds with $N\pmod{25}$. In the second chart the values cycle every 36 numbers so the rows of the second chart corresponds with $N\pmod{36}$.

If the following rules are applied in order they can be used to determine if the last two digits of $S$ obtained from $2N$ will match the last two digits of $S$ obtained from $N$.

Rule 1: If $N \equiv 3\pmod{6}$ then the digits will not match

Rule 2: If $N\pmod{25}+N\pmod{36}=0$ then the digits will match

Rule 3: If $$1\le N\pmod{36}\le 14$$ and $$N\pmod{25}+N\pmod{36}-\left\lfloor\frac{N\pmod{36}+3}{6}\right\rfloor=25$$ the digits will match

Rule 4: If $$22\le N\pmod{36}$$ and $$N\pmod{25}+N\pmod{36}-\left\lfloor\frac{N\pmod{36}+3}{6}\right\rfloor=30$$ the digits will match

Rule 5: in any other case the digits will not match

$\endgroup$
  • $\begingroup$ Thank you very much! Your help is appreciated! $\endgroup$ – Max0815 Mar 25 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.