1
$\begingroup$

Could someone give me hints in how to solve the following (rather interesting) problem?

Prove that there exists an integer consisting of an alternance of $1$s and $2$s with as many $1$s as $2$s (as in $12$, $1212$, $1212121212$, etc.), and which is divisible by $2013$.

Source: Problem 4 in this document.

I just had to ask it before 2013 ends :)

$\endgroup$
5
$\begingroup$

Among the first 2014 numbers of this kind, two must have the same remainder mod $2013$.

$\endgroup$
  • $\begingroup$ Just brilliant. Many thanks :) $\endgroup$ – Prism Dec 31 '13 at 9:15
  • 1
    $\begingroup$ This is formally known as en.wikipedia.org/wiki/Pigeonhole_principle $\endgroup$ – lab bhattacharjee Dec 31 '13 at 9:18
  • 2
    $\begingroup$ Actual solution can be obtained by Fermat's theorem. It is 12 repeated 660 times. I had to answer before 2013 ended :-) $\endgroup$ – user44197 Dec 31 '13 at 9:36
1
$\begingroup$

Hint:

Consider the numbers: the sequence of integers $12,1212,121212,12121212,.......$

Two of them must be equal modulo $2013$.Hence, the difference of these two must be divisible by $2013$. Now use this difference to obtain the desired number (note that $2,5\not|2013$)

$\endgroup$
  • $\begingroup$ Thanks for more detailed explanation :D $\endgroup$ – Prism Dec 31 '13 at 9:18
1
$\begingroup$

note $3$ has to divide the number. So what can you say about the sum of the digits?

$11 has to divide the number. So what can you say about the sum of digits in the odd location and even location.

Once you have fixed these two, you want $61$ divide the number.

I am glad that 2013 is not a prime number :)


In response to the comment by OP:

Suppose the number starts as $12$. It is not clear if the length has to be even, but I will assume that. Then every time you add another $12$ you are muliplying by 100 and adding 12. So $$ P_{n+1} = 100 P_n + 12 $$ Solving we have $$ P_n = 4 \times \frac{100^n-1}{33} $$ Since $61$ divides $P_n$, by Fermat's theorem $$ n = 60 k $$ Number is clearly divisible by 3. Working modulo $11$ we have $$ P_{n+1} = P_n + 1 $$ So $$ P_1 = 1\\ P_2 = 2 \\ P_3 = 3 \\ P_4 = 4 $$ Hence $n$ has to be a multiple of 11.

The smallest $n$ is 660.

So the number is $12$ repeated 660 times.

$\endgroup$
  • $\begingroup$ How do you make $61$ divide the number? I don't immediately see it. At least for divisibility by $3$ and $11$, we have the the known criterions… Never heard of one for 61. :) $\endgroup$ – Prism Dec 31 '13 at 9:19
  • $\begingroup$ Trial and error. But is better than trying out 2014 numbers, the largest having 4028 digits! $\endgroup$ – user44197 Dec 31 '13 at 9:20
  • $\begingroup$ Haha well, I multiplied $61$ by $10k+2$ for $k=0, 1, 2, 3, 4, … 15$, but I haven't gotten single number of the form $121212…12$ $\endgroup$ – Prism Dec 31 '13 at 9:27
  • $\begingroup$ It is 12 repeated 660 times. See my update $\endgroup$ – user44197 Dec 31 '13 at 9:35
  • $\begingroup$ Finding a formula for $P_n$ is an interesting idea. Thanks for taking your time for updating the answer (+1). This is a very concrete approach to the problem! $\endgroup$ – Prism Dec 31 '13 at 9:40

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.