Which Solution Would You Feature? 12/9/2012

This post originally appeared on the Brilliant blog on 12/9/2012.

Below, we present a problem from the 12/03/2012 Algebra and Number Theory set, along with three student submitted solutions (none of them have been edited). In the comments section, please vote for the correct solution that you think should be featured, and state your reason for choosing the particular solution. For example "Solution C. Because it made sense." Think also if the solutions are correct, wrong, or missing steps.

These solutions are presented as is, and have not been edited.

Note: I will not reveal who wrote which solution in this blog post. The chosen featured solution will (as always) be credited to the originator.

Problem: Consider $N=20132013 \ldots 2013$, where $N$ consists of the number $2013$ concatenated (repeated) $2013$ times. What is the remainder of $N$ when divided by $1001$?

Details: Concatenated: Combining $2$ strings of numbers into one, by placing the first string directly before the second. For example, the number $123$ concatenated 4 times would be $123123123123$.

Solution A

$201320132013 = 2013x(10**8+10**4+1) 2013 = 11 \mod 1001$ $10**4 = -10 mod 1001$ $201320132013 = 11*(-10X-10 + -10 +1) = 11*91 = 1001 = 0 mod 1001.$

Since $2013 = 0 mod 3$ (repeat 3 times) Hence $N = 0 mod 1001$.

Solution B

Notice that 1000≡−1(mod1001). So powers of 10 repeat as follows 1, 10, 100, −1, −10, −100, 1, ⋯ which has period 6 so this allows us to remove lcm(6, 4)=12 digits, or three concatenated terms from the modulus and replace it with 201320132013≡0(mod1001) As 2013 is divisible by 3, this means that all terms will be eliminated, giving 2013(2013 times)≡0(mod1001)

Solution C

For 2013 concatenated 3 times and divided by 1001, 201320132013/1001=2111913 Since 2013 is divisible by 3, 2013/3=671 N will be 201320132013 concatenated 671 times Thus N/1001=2111913 concatenated 671 times So there will be no remainder and the answer is 0.

Remarks from Calvin

This question is quite simple to explain, once you realize what is going on. However, all 3 solutions are confusing in their own way, and could be communicated better. As a result, few people seem to want to

All 3 solutions revolve around the idea that 201320132013 is a multiple of 1001. However, the explanation of their train of thought is lost, by not writing down what they are actually thinking.

For solution A, after establishing that 201320132013 is a multiple of 1001, the next line of 2013 = 0 mod 3 isn't clear, in part because there are so many 2013's around the place. It would have been much better to state that "Since $2013 = 3 \times 671$, hence $2013$ concatenated $2013$ times is $201320132013$ concatenated $671$ times, so $N$ is a multiple of 1001).

Solution B is too ambitious in combining ideas into a line (or too frugal with words). While I agree with each individual sentence fragment, it is difficult to see where he's heading, as he just throws all the ideas at you. The clearer way of stating his ideas is as follows: "Notice that $1000 = -1 \pmod{1001}$. Hence, taken modulo $1001$, the terms $10^n$ cycle as $1, 10, 100, -1, -10, -100, 1, \ldots$ with a period of $6$. We observe that $201320132013$ is a multiple of $1001$ (no substantiation given). Since $2013$ has length 4 and lcm(4,6)=12, it follows that $201320132013 \times 10^{12k} \equiv 201320132013 \equiv 0 \pmod{1001}$. As 2013 is divisible by 3, we can thus eliminate all of the digits bee removing strings of 12 at a time. Hence, 2013 concatenated 2013 times $\equiv 0 \pmod{1001}$.

Typos like that of Solution C can completely invalidate your proof. In the division, it should have been $201320132013/1001 = 201119013$. (If you consider the number of digits, it's clearly too short.) Also, we should have $N/1001 = 000201119013$ concatenated $671$ times. Both of these mistakes could have been avoided by actively checking that the number of digits makes sense. Frequent typos include mislabeling of points, interchanging of variables, wrong computations which carry, etc. While some of this can be fixed when I'm reading through the proof, numerous such errors can result in faulty logic, which would make the solution wrong. As a side note, proper punctuation will be helpful. The solution had no punctuation marks, though there were capitalized letters in logical places.

Overall, Solution C by Fang Ting provides the best explanation, once the typos are accounted for.