For a rational number $r$, its *period* is the length of the smallest repeating block in its decimal expansion. for example, the number $r=0.123123123...$ has period $3$. If $S$ denotes the set of all rational numbers of the form $r=\overline{abcdefgh}$ having period $8$, find the sum of all elements in $S$.
Problem
Source: RMO 2018 P3
Tags: algebra, combinatorics
07.10.2018 15:04
My answer was 50000045...Why do I have a feeling it's wrong?
07.10.2018 15:05
I was getting a non integral answer lol
07.10.2018 15:05
Not irrational tho
07.10.2018 15:26
The answer will be integral and large because... $$r=\frac{\overline{a_1a_2a_3a_4...a_8}}{10^{8}-1}$$where \(a_8\) is positive and the rest are non-negative (and obviously all are less than equal to 9). Now if we add all possible numerators of r, then we'll have an integer multiple of \(10^{8}-1\). It is of order 8 because the no. of numerators having \(a_1=9\) is itself \(9\times10^7\).
07.10.2018 15:33
I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$
07.10.2018 15:39
NikoIsLife wrote: I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$ You missed the case when no. Is like 0.12121212.....
07.10.2018 15:39
You have to subtract that from it
07.10.2018 15:40
Smita wrote: You missed the case when no. Is like 0.12121212..... DynamoBlaze wrote: smallest repeating block
07.10.2018 15:45
Smita wrote: NikoIsLife wrote: I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$ You missed the case when no. Is like 0.12121212..... I already counted for this in $\sum_{i=0}^{9999}\frac i{9999}$.
07.10.2018 15:46
TheDarkPrince wrote: Suppose $r = \frac{p}{q}$ and $\gcd(p,q) = 1$. We have that $\left(10^{n} - 1\right)r$ is integer or $q\mid p(10^n-1)$ but $\gcd(p,q)=1$ so $q\mid 10^n-1$ where $n$ is the period. Here $n$ is $8$, thus $q\mid 10^8-1$ but $q\nmid 10^4 -1$ thus $q\mid 10^4 + 1 = 10001 = 73\cdot 137$ and $q\neq 1$. Thus $q = 73$ or $137$ or $10001$. If $q = 73$, then $p = 1,2,\dots ,72$. Thus sum of $r$ is $36$. If $q = 137$, then $p = 1,2,\dots ,136$. Thus sum of $r$ is $68$. If $q=10001$, then $p\neq 73,137$ and $p=1,2,\dots ,10000$. We have sum of $r = 5000-\frac{73+137}{10001} = 50000-\frac{120}{10001}$. Thus answer is $50104 - \frac{120}{10001}$. (This seems wrong as seen from previous answers ) This is wrong. The right answer was given by NikoIsLife.
07.10.2018 15:47
Smita wrote: NikoIsLife wrote: I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$ You missed the case when no. Is like 0.12121212..... All numbers of period 1, 2 are included in this. Nothing was missed.
07.10.2018 15:54
Let $T_n$ denote the sum of all $n$-periodic numbers. Let $r_n = 0.\overline{a_1a_2a_3\dots a_n}$. We have \[\sum_{i=0}^n T_{2^i} = \text{Sum of all } r_{2^n} \text{ as } a_1, a_2, \dots, a_{2^n} \text{ vary over } [0,9]\]After a bit of algebra, we get $LHS = \frac{10^{2^n}}{2}$, so for $n \ge 1$, \[T_{2^n} = \sum_{i=0}^n T_{2^i} - \sum_{i=0}^{n-1} T_{2^i} = \frac{10^{2^n} - 10^{2^{n-1}}}{2}\]Setting $n = 3$, we get the answer is \[\frac{10^8-10^4}{2} = 49995000.\]
07.10.2018 16:44
I made a stupid mistake before. Here is a proper solution: Suppose $r = 0.\overline{abcdefgh}$ is a rational with period $8$. Now $(10^8-1)r = \overline{abcdefgh}$. Now sum it over all $a,b,\dots,h$ thus we get \[\sum r = \frac{(0+1+\dots +9)\cdot 10^7 \cdot (10^8-1)}{9\cdot (10^8-1)} = 5\cdot 10^7.\] We need to subtract the rationals with period $4$. Thus we get \[5\cdot 10^7 - 5\cdot 10^3 = \boxed{49995000}.\]
07.10.2018 17:18
5*(10**7 - 10**3 + 10 - 1) We first need to find all rationals with period 8 or 4 or 2 or 1 then substract it by all rationale with period 4 or 2 or 1 then add all with period 2 or 1 then substract with period 1
07.10.2018 17:26
TheDarkPrince wrote: I made a stupid mistake before. Here is a proper solution: Suppose $r = 0.\overline{abcdefgh}$ is a rational with period $8$. Now $(10^8-1)r = \overline{abcdefgh}$. Now sum it over all $a,b,\dots,h$ thus we get \[\sum r = \frac{(0+1+\dots +9)\cdot 10^7 \cdot (10^8-1)}{9\cdot (10^8-1)} = 5\cdot 10^7.\] We need to subtract the rationals with period $4$. Thus we get \[5\cdot 10^7 - 5\cdot 10^3 = \boxed{49995000}.\] My solution was the same. I just forgot to subtract the rationals with period 4 . Hope they don't cut much for that.
07.10.2018 18:03
Another way - Its easy to see that the number of rational numbers with period 8 is $Z = 10^8 - 10^4$. Also, we can divide these numbers into pairs such that the numbers in a pair add up to 1. Thus the answer is $Z/2$.
07.10.2018 18:15
NikoIsLife wrote: I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$ Duh, I did so much for this. Well done.
08.10.2018 09:43
Just count all cases of the form $0.\overline{abcdefgh}$ (allowing smaller periods) and then subtract the cases of the form $0.\overline{abcd}$ (again allowing smaller periods). Why is this correct? Let $S = \{0.\overline{abcdefgh}\mid a,b,c,d,e,f,g,h \in \{0,1,2,3,4,5,6,7,8,9\}\}$ If $F_i$ denotes the set of rationals between $0$ and $1$ with period $i$, then $$S = F_1 \cup F_2 \cup F_4 \cup F_8 $$Similarly, if $T = \{0.\overline{abcd} \mid a,b,c,d \in \{0,1,2,3,4,5,6,7,8,9\} \}$, then $$T = F_1 \cup F_2 \cup F_4$$ Thus $$F_8 = S - T$$ Using this, it is easy to see that the sum of rationals in $F_8$ is given by $$\sum_{abcdefgh} \frac{\overline{abcdefgh}}{99999999} - \sum_{abcd} \frac{\overline{abcd}}{9999}$$ $$= \sum_{i=0}^{99999999} \frac{i}{99999999} - \sum_{i=0}^{9999} \frac{i}{9999}$$$$=\frac{10^8}{2} - \frac{10^4}{2}$$
20.05.2020 11:11
Redacted
05.11.2020 22:16
srijonrick wrote:
Can anyone find the mistake in this solution? My answer is exactly 1 less than the correct answer $49995000$. The thing wrong with this solution is that while counting the numbers with period, you stopped at 99999998. So while counting the numbers with period 4, you should have stopped at 9998. But instead, while counting the numbers with period 4, you also counted 9999/9999. So you subtracted an extra 1. So your answer came to be 1 less than the correct answer. I hope this resolves your doubt.
14.09.2024 08:25
NikoIsLife wrote: I think the answer is: $$\sum_{i=0}^{99999999}\frac i{99999999}-\sum_{i=0}^{9999}\frac i{9999}=\boxed{49995000}$$ Why does that summation work? I don't understand. What is the motivation behind it? Edit: I understand it now.