Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

These are a few examples of how "forbidden" procedures can lead us to the correct answer:

$$\displaystyle\frac{1\not4^1}{2\not8_2} = \frac{11}{22}=\frac{1}{2}$$

$$\displaystyle\frac{1\not3^1}{3\not9_3} = \frac{11}{33}=\frac{1}{3}$$

$$\displaystyle\frac{{\not3^1}0}{{\not6_2}0} = \frac{10}{20}=\frac{1}{2}$$

I am interested in the question does there exist a fraction such that it satisfies these $5$ requirements and such that it can be "solved" using this "technique"?

  1. The numerator and denominator have $n$ digits where $5\leq n\leq9$
  2. The number in numerator doesn`t end in $0$.
  3. The number in denominator deosn´t end in $0$.
  4. All digits in number in numerator are different.
  5. All digits in number in denominator are different.

EDIT1: The user found that it is possible for $n=5$, now I have a somewhat different version of the problem with modified first requirement:

1*. The numerator and denominator have $n$ digits where $6\leq n\leq9$

2.,3.,4.,5. Same as above.

I believe that now such fraction doesn`t exist and would be very pleased if someone shows that it is so or finds a counterexample in any of these two cases:

Case A) Only one cancellation is allowed.

Case B) More than one cancellation is allowed.

EDIT2: It seems that belief in non-existence of such fraction in the modified problem $6\leq n\leq9$ was a failure, below you can see that user Ivan Loh found the solution for the cases $n=6,7$ with one cancellation and solution for the case $n=8$ with two cancellations which is indeed more than I was asking, and, following his examples, I found the case for $n=8$ with one cancellation, it is $\displaystyle\frac {21945703}{65837109}=\frac {21945701}{65837103}=\frac {1}{3}$.

share|improve this question

4 Answers 4

up vote 3 down vote accepted

In case you still want a 5 digit example:

$$\frac{14573}{43719}=\frac{14571}{43713}=\frac{1}{3}$$

A 6 digit example:

$$\frac{194573}{583719}=\frac{194571}{583713}=\frac{1}{3}$$

In fact, let's add a $0$, so

$$\frac{1945703}{5837109}=\frac{1945701}{5837103}=\frac{1}{3}$$

If you want more than 1 cancellation, use

$$\frac{19457023}{58371069}=\frac{19457011}{58371033}=\frac{1}{3}$$

share|improve this answer
    
Amazing! Thank you! –  user67878 Mar 22 '13 at 15:18
    
May I ask how did you find these? Brute force? Some algorithm? Algebra? –  YatharthROCK Mar 23 '13 at 17:33
    
@YatharthROCK I was searching for a fraction satisfying the given restrictions and an additional one: Digits which do not cancel are relatively prime. The reason was because fractions like $$\frac{1234567809}{1234567809}=\frac{1234567801}{1234567801}=\frac{1}{1}$$ did not seem nice enough. With this additional restriction in mind, we clearly are not going to have much luck with $\frac{1}{1}$ or $\frac{1}{2}$. I next tried fractions which reduce to $\frac{1}{3}$, and with a bit of trial and error, got the 5 digit example. All other examples came from trying to add digits to that example. –  Ivan Loh Mar 24 '13 at 4:07

These are known as howlers. Not all fractions obey these laws.

For more info on how to generate them, look at this Dr. Math post.

For the example you need $\frac{31402}{62804}=\frac{1}{2}$.

share|improve this answer
    
I know that majority of them doesn`t obey this law, but I want to know if there exist at least one fraction that follows above mentioned requirements such that it obeys the law. Thank you for the information. It also can be seen that this requirements significantly reduce the number of all possible combinations. –  user67878 Mar 22 '13 at 14:35
    
Feel free to do it! :) –  user67878 Mar 22 '13 at 15:07

5 digit numbers using more than one cancellations:

$$\frac{43201}{86402} = \frac{11101}{22202} = \frac{1}{2}$$

share|improve this answer
    
Only one cancellation is allowed, i forgot to mention that, I will edit the question now, but you have proved that if more than one cancellation is allowed then the answer is affirmative, well done! –  user67878 Mar 22 '13 at 14:39
1  
@Thus: You can choose to cancel in any or all of the four nonzero positions alone, and it will still work. (The point requirement for this to work is simply that there's no carry either into the position or out of it when calculating $43201\times 2$). –  Henning Makholm Mar 22 '13 at 14:47
1  
Isn't requiring it to cancel in just one step a WEAKER condition? –  Sean Ballentine Mar 22 '13 at 14:49
    
Brilliant! I didn´t actually see it. –  user67878 Mar 22 '13 at 14:50
    
@Thus even if you require the fraction to have only 1 possible cancellation (all other digits cannot cancel), it is still possible. –  Ivan Loh Mar 22 '13 at 14:52

I wrote some code to generate these kind of fractions. It's written in Python, so it's practically like pseudocode. Basically, I just brute-force over all numbers and simply validate whether it is a Howler fraction or not.

# -*- coding: utf-8 -*-
from fractions import Fraction, gcd

def digitify(x):
    return list(str(x))

def intify(digits):
    return int(float(''.join(map(lambda digit: str(digit), digits))))

def primes(max_ = None, req = None):
    x = 2
    while True:
        composite = None
        for divisor in range(2, x // 2):
            if (x % divisor) == 0:
                composite = True
                break
        if not composite:
            yield x
        x += 1

def factorize(x):
    factors = []
    x = int(x)

    for prime in primes():
        if x == 0 or x == 1:
            break

        if x % prime == 0:
            factors.append(prime)
            while x % prime == 0:
                x /= prime

    return factors

def validate(num, den, strict=False):
    frac = Fraction(num, den)
    num = digitify(num)
    den = digitify(den)

    # cancel last digits
    if (not strict) or (gcd(intify(num[:-1]), intify(den[:-1])) == 1):
        factors = factorize(gcd(int(num[-1]), int(den[-1])))
        for factor in factors:
            num_ = intify(num[:-1] + [int(num[-1]) / factor])
            den_ = intify(den[:-1] + [int(den[-1]) / factor])
            frac_ = Fraction(num_, den_)
            if frac_ == frac:
                return frac_

    # cancel first digits
    if (not strict) or (gcd(intify(num[1:]), intify(den[1:])) == 1):
        factors = factorize(gcd(int(num[0]), int(den[0])))
        for factor in factors:
            num_ = intify([int(num[0]) / factor] + num[1:])
            den_ = intify([int(den[0]) / factor] + den[1:])
            frac_ = Fraction(num_, den_)
            if frac_ == frac:
                return frac_

def find(n):
    start = 10 ** (n-1)
    stop = 10**n + 1

    for x in range(start, stop):
        for y in range(start, stop):
            if x == y:
                continue
            frac = validate(x, y)
            if frac:
                print(x, y, frac)

Executing $find(n)$ provides you with all the Howler fractions of size $n$, though it takes a bit if time to compute them all.

I improvised the algorithm a bit. Now, it takes a fraction finds valid equivalent fractions with the added restriction that the :

def find(frac):
    num = frac.numerator
    den = frac.denominator
    x = 1

    while True:
        x += 1
        num_ = num * x
        den_ = den * x
        frac = validate(num_, den_, strict=True)
        if frac:
            print(num_, den_, frac)

This gives more Howler fractions in significantly less time, although you can't find fractions of length $n$ upfront.

I ran the code on my machine but as soon as I started to paste the output on SE or any pastebin, Chrome froze. But you can run the code on your machine and try (It's Python 3 BTW).

Update: First few fractions of length 5 are here;

share|improve this answer
    
+1 for the effort! –  user67878 Mar 24 '13 at 13:39
    
@Thus I really wish I had a machine and this retarded GIL would go away from Python, then I could give you results. trying to leverage AppEngine now... –  YatharthROCK Mar 25 '13 at 10:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.