Friday, May 30, 2014

Wrong Cancellation Gone Right

I was working on a Project Euler problem a few years back. The problem is essentially asking for you to find all double digit fractions under $1$ where you cancel the same number on the top and bottom. Such as $$\frac{49}{98}=\frac{4\cancel{9}}{\cancel{9}8}=\frac{4}{8}$$ Of course this is an incorrect method, but curiously, the equality remains. I was able to easily solve the problem with brute force. It's not a particularly computationally intensive problem. But when I shared the fun problem and results with a roommate of mine, he posed an interesting follow-up question. Can we extend this cancellation any further? And basically, we found that $$\frac{4}{8}=\frac{49}{98}=\frac{499}{998}=\frac{4999}{9998}=\cdots$$ And it turns out that this worked for any number of $9$'s in that location and for any of the two digit fractions that were found. So, we generalize the problem:

For $a,b,c\in\mathbb{N}$ such that $0\leq a,b,c\leq 9$ $$\frac{a}{b}=\frac{10\cdot a+c}{10\cdot c + b} \implies \frac{a}{b}=\frac{10^n\cdot a + 10^{n-1}\cdot c + \cdots + 10 \cdot c +c}{10^n \cdot c + 10^{n-1}\cdot c + \cdots + 10\cdot c + b}$$ Or, in sigma notation $$\frac{a}{b}=\frac{10^n\cdot a + c\cdot \sum_{i=0}^{n-1}{10^i}}{c\cdot \sum_{i=1}^{n}{10^i} + b}$$ Through algebra (cross multiply, group and divide), our premise implies that $$c=\frac{9ab}{10a-b}$$ So, consider the right hand side of the conclusion and substitute the above equality for $c$. $$\frac{10^n\cdot a + c\cdot \sum_{i=0}^{n-1}{10^i}}{c\cdot \sum_{i=1}^{n}{10^i} + b}=\frac{10^n\cdot a + \frac{9ab}{10a-b}\cdot\sum_{i=0}^{n-1}{10^i}}{\frac{9ab}{10a-b}\cdot \sum_{i=1}^{n}{10^i} + b}$$ Multiply top and bottom by $10a-b$ and get $$\frac{\left(10a-b\right)10^n\cdot a + 9ab\cdot\sum_{i=0}^{n-1}{10^i}}{9ab\cdot \sum_{i=1}^{n}{10^i} + \left(10a-b\right)b}$$ Distribute into the parenthesis $$\frac{10^{n+1}\cdot a^2 - 10^n\cdot a b + 9ab\cdot \sum_{i=0}^{n-1}{10^i}}{9ab\cdot\sum_{i=1}^{n}{10^i}+10ab-b^2}$$ Factor out $-ab$ from two terms on the top and $ab$ from two terms on the bottom. $$\frac{10^{n+1}\cdot a^2 - ab\left[10^n - 9\cdot \sum_{i=0}^{n-1}{\left(10^i\right)}\right]}{ab\left[9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+10\right]-b^2}$$ Looking at the top brace, we have $n$ nines subtracted from the number $1$ followed by $n$ zeros, which is just $1$. For example $$\begin{array}{c} 10-9=1\\ 100-99=1\\ 1000-999=1\\ \vdots \end{array}$$ Then looking at the bottom brace, we have $$9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+10=9\cdot\sum_{i=1}^{n}{\left(10^i\right)}+9+1=9\cdot\sum_{i=0}^{n}{\left(10^i\right)}+1$$ which is now $n+1$ nines added to $1$ which will be a $1$ followed by $n+1$ zeros or $10^{n+1}$. For example $$\begin{array}{c} 9+1=10\\ 99+1=100\\ 999+1=1000\\ \vdots \end{array}$$ Substituting these in we get $$\frac{10^{n+1}\cdot a^2 -ab}{ab\cdot 10^{n+1} - b^2}$$ Finally, factor out $a$ on top and $b$ on the bottom and cancel the rest to get $$\frac{a\left(10^{n+1}\cdot a - b\right)}{b\left(10^{n+1}\cdot a - b\right)}=\frac{a}{b}$$ Therefore, if we can cancel the digits in the (incorrect) manner we did, we can add as many of this number as we'd like and still maintain equality.

No comments:

Post a Comment