5
$\begingroup$

I get another training problem, for a Romanian 6th grader competition, for which I have no answer. Find the smallest $n \ge 1000$ such the sum $ 1+11+111+⋯+11⋯11 (n digits)$ it is divisible by 101. I am familiar with the sum, I know how to compute it, but I can see how I can reason about the divisibility by $101$.

I did a numeric analysis on it, and it looks that the solution is $n=1121$, while the first numbers for which the sum is divisible by 101 are $110,313, 403, 404, 514, 717, 807,808, 918$ . Also I did notice that $1111$ is divisible by $101$, and I also seen that the pattern $123456790$ keeps repeating on the sum.

$\endgroup$
0
$\begingroup$

If you consider the remainders upon dividing every term by $101$ we obtain the following sequence:

$$1 \equiv 1 \pmod {101}$$ $$11 \equiv 11 \pmod {101}$$ $$111 \equiv 10 \pmod {101}$$ $$1111 \equiv 0 \pmod {101}$$ $$11111 \equiv 1 \pmod {101}$$ $$ \cdots$$

It is not hard to conclude that the the remainders repeat each $4$ terms. Also note that any sum of $4$ consequtive terms will have remainder $1+11+10+0 = 22$ upon division by $101$. Thus:

$$\sum_{i=1}^{1000} a_n \equiv 22\cdot 250 \equiv 46 \pmod{101}$$

where $a_n = 11 \cdots 1 (n$ digits ). Now you want to solve the following equations:

$$46 + 22k_1 \equiv 100 \pmod{101}$$ $$46 + 22k_2 \equiv 89 \pmod {101}$$ $$46 + 22k_3 \equiv 0 \pmod {101}$$

The first one comes from adding $k_1$ blocks of $4$ terms and adding just one more afterwards to bring the remainder to $0$. The second one comes from ading $k_2$ blocks of $4$ terms and adding the next two afterwards. The last equation arises as one of the ways to reach remainder $0$ is to keep adding $k_3$ blocks of $4$ terms and the next three afterwards.

Let $k_1,k_2,k_3$ be the least nonegative solutions to the congruence relations. Then we have $n_1 = (250+k_1)\cdot 4 + 1$, $n_2 = (250+k_2)\cdot 4 + 2$, $n_3 = (250+k_3)\cdot 4 + 3$. The smallest integer out of $n_1,n_2,n_3$ is the wanted $n$.

$\endgroup$
1
$\begingroup$

Since $111100\ldots00$ is divisible by $101$, you can repeatedly remove the leading four $1$'s from $111\ldots 111$ until you get to one of $0,1,11,$ or $111$. And you can reduce $111$ still further to $10$. So you get the sum $$1+11+10+0+1+11+10+0+\ldots$$

mod $101$. Can you take it from there?

$\endgroup$
1
$\begingroup$

Firstly let's find $F(n) = 1+11+111+...+\frac{10^n-1}{9}$.

$F(n) = \sum_{i=1}^n\frac{10^i-1}{9} = \frac{1}{9}(\sum_{i=1}^{n}10^i-\sum_{i=1}^n1) = \frac{10}{9}\frac{10^n-1}{9}-\frac{n}{9}=\frac{10^{n+1}-9n-10}{81}$

$101 | F(n) \implies 101 | (10^{n+1}-9n-10)$ as gcd(101, 81) = 1

$10^{n+1} \equiv 9n+10 \mod{101}$

Notice

$10^{n+1} \equiv 10, -1, 91(-10), 1 \mod{101} \textrm{ when }n \equiv 0, 1, 2, 3 \mod{4}$ respectively.

Firstly, $9^{-1} \equiv 45\mod{101}$

Consider cases:

$n \equiv 0 \mod{4}, 9n+10\equiv10,n\equiv0 \mod{101} \implies n \equiv 0 \mod{404}$

$n \equiv 1 \mod{4}, 9n+10\equiv-1,9n\equiv-11,n \equiv(45)(-11)\equiv-495\equiv10\mod{101}\implies n\equiv313\mod{404}$

Similar for the other 2 cases, $n\equiv0, 110, 313, 403 \mod {404}$

$n = 0, 110, 313, 403, ..., 808, 918, 1121, ...$ so 1121 is the smallest integer >=1000.

$\endgroup$
1
$\begingroup$

Working $\pmod {101}$ we see that the remainders of the summands are periodic with cycle $\{1,11,10,0\}$.

We want the sum of the remainders to be a multiple of $101$.

Can we get $101$? Well $1+11+10=22$. To get to a multiple of $101$ we'll have to go through the cycle a number of times and then add $0$, $1$ or $12$. Thus we seek $k$ such that $$22k\equiv 0,-1,\, \text {or }\,-12 \pmod {101}$$

It's clear that the least solution for $0$ is $101$.

By brute force (though you could use the euclidean algorithm):

The least solution for $-1$ is $78$.

The least solution for $-12$ is $27$.

Starting with multiples $101$, we see that the first solution would be $1212$.

Now considering $78$, we note that $78\times 4 = 312$, $(78+101)\times 4=716$, $78+2\times 101=1120$. As $1120+1=1121<1212$, that's the lead contender for now.

We need to check that we don't get a smaller value if we start from $27$. But $27\times 4=108$, and adding $4\times 101=404$ to that repeatedly the first value $≥1000$ we come to is $1320$ so that's no good. (just to be careful, the prior value is $916$ and adding two to that does not get you to $1000$).

Thus we confirm your result, $1121$ is optimal.

$\endgroup$
  • $\begingroup$ "...and then add $0,1,$ or $12$." $\endgroup$ – TonyK Feb 22 at 9:52
  • $\begingroup$ @Tonyk True...not sure why I neglected that. Will edit. $\endgroup$ – lulu Feb 22 at 9:53
  • $\begingroup$ @TonyK edited. $\quad $ $\endgroup$ – lulu Feb 22 at 9:56
0
$\begingroup$

Denote $1_n$ by the number with $n$ digits, each one equal to $1$. E.g. $1_3 = 111$.

Start with looking at the remainders when $1_n$ is divided by $101$. Note that $1_n = 10 \times 1_{n-1} + 1$, and $1_1 = 1$. Therefore, inductively we get that the sequence $1_n \mod 101$(for $n \geq 1$) looks like $$1,11,10,0,1,11,10,0,...$$

Now, let us denote $b_m = \sum_{n=1}^m 1_n$. We are interested in $b_m \mod 101$. For this, we break $m = 4k,4k+1,4k+2,4k+3$.

For $m = 4k$, clearly $b_m \pmod{101} = 22k$. For $m = 4k+1$ it is $22k+1$, for $m = 4k+2$ it is $22k+12$, for $m = 4k+3$ it is $22k + 22$.

Therefore, we need to solve these equations : $$ 22k \equiv 0 \pmod{101} \\ 22k+1 \equiv 0 \pmod{101} \\ 22k+12 \equiv 0 \pmod{101} \\ 22(k+1) \equiv 0 \pmod{101} $$

Each of these can be solved, since $22$ and $23$ are invertible mod $101$. The first and fourth equations have obvious solutions. I list the corresponding solutions below. $$ k \equiv 0 \mod 101 k \equiv 78 \mod 101 k \equiv 27 \mod 101 k \equiv -1 \mod 101 $$

Thus, the corresponding solutions to $b_m = 0$ are(for each $l \geq 0$) : $$ 4(101l) = 404l \\ 4(101l+78) + 1 = 404l + 313 \\ 4(101l+27) +2 = 404l+110 \\ 4(101l-1) + 3 = 404l-1 $$

Now, we combine all this into any solution being of the form $404l + d$ where $l \geq 0$ and $d \in \{0,(-1=) 403,110,313\}$.

Finally, it is easy to see that $404 \times 2 + 313 = 1121$ is the smallest solution having four digits.


I feel the need to add this, but I think it will be nice to see.

Let us replace $101$ by an integer $N$ which is coprime to $2$ and $5$. Use the pigeonhole argument, to show that $N$ is divisible by $1_m$ for some $1 \leq m \leq n+1$. (Hint : consider the remainders when $1_m$ is divided by $n$).

Pick the smallest $M$ such that $N$ divides $1_M$. Then, we can now look at the sequence of numbers $b_m = \sum_{i=1}^m 1_n$, and ask : does there exist a number $F$ such that $b_F$ is a multiple of $N$?

Indeed, there is! To see this, note that $1_M$ is a multiple of $N$. Suppose that $b_M$ leaves a remainder $r$ mod $N$.

We claim the following inductive formula holds: $$ b_{kM} = b_M\left(\frac{10^{kM}-1}{10^M - 1}\right) + \sum_{i=1}^{k-1} 1_{iM} $$

This can be verified easily. Next, taking remainders modulo $N$ above, note that $1_{iM}$ is a multiple of $n$ since $1_M$ is a multiple of $n$. So, we just get : $$ b_{kM} \equiv r\times \left(\frac{10^{kM-1}}{10^M-1}\right) \pmod{N} $$

Observe that $\frac{10^{kM} - 1}{10^M-1} = \frac{1_{kM}}{1_M} = c_k$ .Note that this is an integer.

Claim : there exists $1 \leq K \leq N+1$ such that $N$ divides $c_K$.

For this, use pigeonhole on the remainders of $c_K$ mod $N$. Note that two of $c_1,...,c_{N+1}$ have the same remainder mod $N$, say $c_{s} > c_{t}$. Then, $N | c_s - c_t = 10^{t}(c_{s-t})$ (you can check this). But $N$ is coprime to $10^r$, hence $N | c_{s-t}$. Take $K = s-t$.

Therefore, $b_{KM} \equiv rc_K \equiv 0 \mod N$.

Now, we can find infinitely many $F$ such that $b_F$ is a multiple of $N$, by taking $b_{2F},b_{3F}$ and so on.

IN the example of $101$, you can check that $M = 4$ and $K = 101$ worked.

$\endgroup$
  • $\begingroup$ "Romanian sixth grader competition" : I would expect this to be, in the least, crazy stuff at sixth class level. $\endgroup$ – астон вілла олоф мэллбэрг Feb 22 at 9:53
  • $\begingroup$ Your $23k$ should be $22k+22$, I think. (This is not the same as $23k$!) $\endgroup$ – TonyK Feb 22 at 9:54
  • $\begingroup$ Thank you for the point out. $\endgroup$ – астон вілла олоф мэллбэрг Feb 22 at 9:55
  • $\begingroup$ You are right guys, people who make the subjects must be crazy.. $\endgroup$ – motoras Feb 22 at 10:02
  • $\begingroup$ I am adding something to my answer : I'd like to do more than just answer it, if you don't mind. $\endgroup$ – астон вілла олоф мэллбэрг Feb 22 at 10:03
-1
$\begingroup$

Hint: In order to understand the sum, we should understand the terms that go into it. What is the $n$-digit number $11\cdots 11$ mod $101$? How many terms does it take for that sequence to repeat? Your observation that $1111\equiv 0\mod 101$ will be helpful here.

$\endgroup$

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.