We used this as the first question in the CS interview at LMH in December 2019. The question below is from this post.

Question:

  1. Find the smallest natural number ending in \(6\), such that if the last \(6\) is removed and placed in the front, the new number is \(4\) times the original number.
  2. Can you give a procedure to find the smallest number ending in digit \(d\), where \(d\) is between \(1\) and \(9\), such that if the last digit, \(d\), is removed and placed in front, you get a number that is \(k\) times as large? Is this possible for every value of \(d\) and \(k\)?

Solution:

  1. The answer is 153846.

    Here's one way to arrive at it. We can start by doing long multiplication, where we multiply \(X\cdots X6\) by \(4\). We don't know how many digits there are or what they are, but we can at least multiply \(6\) by \(4\). We know that this yields the digit \(4\) and carry \(2\).

    \(X \cdots X^{(2)} 6\)
    \(\times 4\)
    \(Y \cdots Y 4 \)

    As we know that removing the trailing \(6\) and putting it at front yields a number \(4\) times as big, the above operation tells us that the digit just before the \(6\) must have been \(4\). This allows us to continue the long multiplication, \(4 \times 4 + 2\) is \(18 \) which yields the digit \(8\) and carry \(1\).

    \(X \cdots X^{(1)} 4^{(2)} 6\)
    \(\times 4\)
    \(Y \cdots 8 4 \)

    Continuing this way, and stopping as soon as we get the digit \(6\) and carry \(0\), we obtain,

    \(1^{(2)} 5^{(1)} 3^{(3)} 8^{(1)} 4^{(2)} 6\)
    \(\times 4\)
    \(6 1 5 3 8 4 \)

    We could of course continue and find other such numbers, but the question asked us to find the smallest such number, so we will stop here.

  2. First, we observe that if \(d \lt k \), then it is not possible, at least not if we don't allow the leading digit to be \(0\). This is because even if a number starts with \(1\), after multiplying it by \(k\), if the number of digits in the new number has not increased, the first digit in the new number is at least \(k\). We do know that the number of digits after multiplying by \(k\) remains unchanged as we are told that the new number is simply obtained by moving the \(d\) from the end to the beginning. So if \(d \lt k\) this is not possible. We shall now show that whenever \(d \geq k\), we can always find a solution.

    We will follow the same strategy as we used in the special case above. Let us consider what happens when we have to multiply some digit \(d_1\) by \(k\); let us also assume that we may already have a carry \(c_1\) (from the previous multiplication). We get the number \(d_1 k + c_1 \). If \(d_1 k + c_1 \geq 10\), we need to break this into a digit \(d_2\) and a carry \(c_2\). Let us make a few observations.

    1. \(d_1 k + c_1 \lt 10k \) provided \(c_1 \lt k\). This follows as \(d_1\) is a digit between \(0, \ldots, 9\), so \(d_1 k \leq 9k \), and also we have that \( c_1 \lt k\).
    2. Hence, we can write \( d_1 k + c_1 = 10 \cdot c_2 + d_2 \), where \(d_2\) is a digit between \(0, \ldots, 9\), and we also have that \(c_2 \lt k\). (If \(c_2 \geq k\), then \(10 \cdot c_2 + d_2 \geq 10k\), but as \(10 \cdot c_2 + d_2 = d_1 k + c_1\), and \(d_1 k + c_1 \lt 10k\), that can't happen.)
    3. The most critical observation (which I didn't expect any candidate to make) is that under the condition that \(d_1, d_2\) are digits between \(0, \ldots, 9\) and that \(c_1 \lt k\) and \(c_2 \lt k\), this process is entirely reversible. That starting with \((d_2, c_2)\) where \(c_2 \lt k\), there is a unique pair \((d_1, c_1)\) with \(c_1 \lt k\) satisfying \( d_1 k + c_1 = 10 c_2 + d_2 \). In fact, \(d_1\) is the quotiend when \(10 c_2 + d_2 \) is divided by \(k\) and \(c_1\) is the remainder.

    Now let us repeat the algorithm that we had from the previous part. We start with the digit \(d\) and multiplier \(k\). We begin with \((d_0 = d, c_0 = 0)\) and perform long multiplication. Starting with \((d_i, c_i)\) we get a \((d_{i+1}, c_{i+1})\) as indicated by Observation (b) above. Since each \(d_i\) takes values in \(0, \ldots, 9\) and each \(c_i\) takes values in \(0, \ldots, k-1\), there are at most \(10k\) such pairs. Thus, the sequence has to eventually repeat. By the reversibility from Observation (c), we know that the first repetition must yield \((d, 0)\), so we have obtained the smallest number we were looking for.

Remark: While this was certainly not expected during interviews, we can quickly check that provided \(d \geq k \), the reversibility ensures that in order to get to \((d_0 = d, c_0 = 0 )\), we must have started from \(d_{-1} = q, c_{-1} = r)\), where \( 10 \cdot 0 + d = q \cdot k + r \). The fact that \(d \geq k\) ensures that \(q \geq 1\), so the leading digit of the number we are looking for is at least \(1\).

This also gives us a way of writing the number from left to right, rather than right to left. Let's see how this works out with the specific example above with \(d = 6 \) and \(k = 4\), the first digit must be given by looking for \(q, r\) satisfying \(10 \cdot 0 + 6 = 4 q + r\), so we get that the first digit must be \(1 \) and the corresponding carry is \(2\). Then, we are looking for \(q, r\) that satisfy, \(2 \cdot 10 + 1 = 4 q + r \), we get the next digit must be \(5 \) and carry is \(1\); then looking for \(1 \cdot 10 + 5 = 4 q + r\), gives digit \(3\) and carry \(3\), looking for \(3 \cdot 10 + 3 = 4q + r\) gives digit \(8\) and carry \(1\), looking for \(1 \cdot 10 + 8 = 4 q + r\) gives digit \(4 \) and carry \(2\), and finally looking for \( 2 \cdot 10 + 4 = 4 q + r \) gives digit \(6 \) and carry \(0\), when we can stop. The number is \(153846\).

Discussion

As can be seen from the solution to the second part of the question, getting the correct answer was quite involved and led to lots of interesting discussions in the interview. This kind of interaction between tutor and student is an integral part of tutorials at Oxford, and this is why we design interview questions that can lead to such discussions, to see how you would perform in tutorials.

The main purpose of this question was to get candidates to think algorithmically and then reason mathematically about the algorithmic approach. As can be seen in the solution above, there are certain aspects of the argument that are quite subtle and we were not expecting candidates to present such a detailed argument, certainly not without help from the interviewers. What we were hoping is that candidates would see that they can at least start doing long multiplication and that that reveals the digits of the number one by one starting from the right. We were also hoping that, perhaps with a bit of help in some cases, candidates would see that given a digit and carry, the next digit and carry is uniquely defined, and since the number of digit-carry pairs can be at most \(100\), at some point of time the process must repeat. Stopping at the first repetition gives the desired smallest number, though as you can see the argument of correctness is a bit subtle.

What was more interesting is that some candidates started approaching the problem purely mathematically. Let's see this approach for the specific example first. Let \(l\) be the number of digits in the target number. We can write the unknown number as \( 10 x + 6 \), as we know that the last digit is \(6\). Then we have the following equality:

\[ 4 (10 x + 6 ) = 6 \cdot 10^l + x. \]

This is a single equation in two unknowns \(x, l\), both of which have to be positive integers. We do also have the additional information that we are looking for the smallest possible \(l\) that satisfies the equation for some \(x \), since we are looking for the smallest such number. We can rearrange the above equation to get

\begin{align*} 4 (10 x + 6 ) &= 6 \cdot 10^l + x \\ 39 x + 24 &= 6 \cdot 10^l \\ 13 x + 8 &= 2 \cdot 10^l \\ 13 x &= 2 (10^l - 4). \end{align*}

At this point, we may try to find the smallest value of \(l\) that satisfies the above equation. In order to satisfy the equation we need that \(13 | 10^l - 4\), or alternatively, we want \( 10^l \equiv 4~(\mathrm{mod}~13)\). You could check the following relatively easily, especially if you've seen some modular arithmetic.

\begin{align*} &10^1 \equiv 10 ~(\mathrm{mod}~13) &10^2 \equiv 9 ~(\mathrm{mod}~13) \\ &10^3 \equiv 12 ~(\mathrm{mod}~13) &10^4 \equiv 3 ~(\mathrm{mod}~13) \\ &10^5 \equiv 4 ~(\mathrm{mod}~13) &10^6 \equiv 1 ~(\mathrm{mod}~13) \end{align*}

This gives us \(l = 5\) as a solution, as \(10^5 - 4\) is divisible by 13. We can then solve for \(x\) as:

\begin{align*} 13 x &= 2 (10^5 - 4) \\ x &= 2 \cdot 99996 / 13 \\ x &= 2 \cdot 7692 = 15384. \end{align*}

This gives us the solution \(153846\) as desired. This was a solution that I didn't have in mind when we started interviewing, so it was interesting to see some of these solutions in interviews! One could try this approach in general, but here's an observation: we had \( 10^6 \equiv 1 ~(\mathrm{mod}~13)\), so if we hadn't found a solution with \(l = 1, 2, 3, 4, 5, 6\), we would not have found a solution at all, as \(l = 6 + i\) would behave exactly the same as \(l = i\). The general problem gives rise to the following equation:

\begin{align} k \cdot (10x + d) &= 10^l d + x, \end{align}

and so,

\begin{align} (10k - 1) x &= d (10^l - k). \end{align}

Now we know that the algorithmic solution implies that this equation should always have a solution for \(x, l\), whenever \(d \geq k\), but can one argue this from this equation alone? I haven't quite figured out how do to that, so if anyone has an argument that can directly show that this equation always has a solution, I'd be very keen to receive it by email or in comments below.