Page 1 of 2 12 LastLast
Results 1 to 15 of 20

Math Help - One VERY CHALLENGING QUESTION (no-one has been able to work this one out yet!)

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    51

    One VERY CHALLENGING QUESTION - STILL UNANSWERED, despite the 9 replies!!!

    The question, as an image, can be seen below:




    I have asked many mathematicians about this, and so far, an easy way of working this one out has not been found. I would be extremely grateful to anyone who could explain how to work this question out. Good luck!
    Last edited by yeah:); April 15th 2010 at 12:27 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by yeah:) View Post
    The question, as an image, can be seen below:




    I have asked many mathematicians about this, and so far, an easy way of working this one out has not been found. I would be extremely grateful to anyone who could explain how to work this question out. Good luck!
    Every number can be written as product of prime factors.

    1000000 = 2^6 \cdot 5^6.

    So I suppose you have 2x2x2x2x2x2x5x5x5x5x5x5.

    Then just split that up into 3 groups of numbers...

    Such as 2x2x2 2x2x2 and 5x5x5x5x5x5.

    Or 2x2, 2x2x2x2x5x5, 5x5x5x5

    Cant remember the exact formula to figure out how many of those there are though! Binomial stuff...

    --EDITED FOR FAIL--

    Plato is good at this sort of thing. So come on in and post up a solution Plato!



    EDIT: HAHAHA speak of the devil guess who was looking at this thread when I had finished posting this.
    Last edited by Deadstar; April 14th 2010 at 03:27 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Bleh scratch that binomial part.

    I think the number of non-unique ways is the solution to...

    x + y + z = 12.

    With x,y,z > 0 and are integers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Basically you are just forming three groups from twelve numbers (the prime factors of one million). I think Deadstar got the right idea but the answer is not given by this formula.

    You first choose a first group of n numbers, 0 < n < 11, so the number of combinations is \binom{12}{n}.

    Then you choose another group of k numbers, 0 < k < 11 - n, so the number of combinations is \binom{12}{k}.

    Finally you are left with a last group of 12 - n - k numbers, so the last number of combinations is \binom{12}{12 - n - k}.

    So, the number of ways of writing it is :

    \binom{12}{n} \times \binom{12}{k} \times \binom{12}{12 - n - k}

    With 0 < n < 11 and 0 < k < 11 - n.

    Unless there is a way of combining those binomials, I guess a quick exhaustive search through the 132 or so possibilities for n and k should get the answer.

    Unless I got it wrong of course ! Don't hesitate to tell me, I'm really unsure about this.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Bacterius View Post
    Basically you are just forming three groups from twelve numbers. I think Deadstar got the right idea but the answer is not given by this formula.

    You first choose a first group of n numbers, 0 < n < 11, so the number of combinations is \binom{12}{n}.

    Then you choose another group of [tex]k[tex] numbers, 0 < k < 11 - n, so the number of combinations is \binom{12}{k}.

    Finally you are left with a last group of 12 - n - k numbers, so the last number of combinations is \binom{12}{12 - n - k}.

    So, the number of ways of writing it is :

    \binom{12}{n} \times \binom{12}{k} \times \binom{12}{12 - n - k}

    With 0 < n < 11 and 0 < k < 11 - n.

    Unless there is a way of combining those binomials, I guess a quick exhaustive search through the 132 or so possibilities for n and k should get the answer.

    Unless I got it wrong of course ! Don't hesitate to tell me, I'm really unsure about this.
    Think that's probably on the right lines. But I think that's non-unique solutions.

    I.e. all the ways with 2x2x2 and 2x2x2 would appear in that.

    I think it can be solved easier with the post that I put up while (I presume) you were typing your reply. But again, nonunique solutions.

    Also, holy hell you're only 16! Smart kid...
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.

    Quote Originally Posted by Deadstar
    Also, holy hell you're only 16! Smart kid...
    Thanks
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Quote Originally Posted by Bacterius View Post
    Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.


    Thanks
    WOW! Thank you so much for your replies!!! All your solutions here seem so complicated to me, though!!! Is there any way of solving the problem that is shorter, or at least, could someone explain this to me in slightly more simple terms? Also, what is the actual final answer?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by Bacterius View Post
    Yeah I was thinking that nonunique solutions were going to break down my reasoning, I'm going to look at your second solution Deadstar.


    Thanks
    Ya You should be able to see what I'm getting it but basically x,y,z are the size of the groups of numbers.

    So 2x2 2x2x2 2x5^6 would have x=2, y=3, z=7...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Quote Originally Posted by yeah:) View Post
    WOW! Thank you so much for your replies!!! All your solutions here seem so complicated to me, though!!! Is there any way of solving the problem that is shorter, or at least, could someone explain this to me in slightly more simple terms? Also, what is the actual final answer?
    We don't know yet lol...

    But solving x+y+z=12 gives...

    x+y+z = 9 for x,y,x>0

    = {9+3-1 \choose 9} = {11 \choose 9} = 55 which seems way too low...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2009
    Posts
    51
    Quote Originally Posted by Deadstar View Post
    We don't know yet lol...

    But solving x+y+z=12 gives...

    x+y+z = 9 for x,y,x>0

    = {9+3-1 \choose 9} = {11 \choose 9} = 55 which seems way too low...
    I see... 55 does seem rather low...hopefully, someone can eventually lead this thread to a solution!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jan 2009
    Posts
    715
    We know those factors are the product of  2^s 5^t .

    Let  1000000 = 10^6 = xyz and  p,q,r be the maximum degrees of 2 or  5 of  x,y,z respectively .

    We should have  p+q+r = 6

    We have three cases :

    CaseI : three of them are distinct and the possible combinations are :

     6 = 0+1+5 = 0+2+4 = 1+2+3 so there are three possible combinations in this case .

    CaseII :  p=q we have

     6 = 0+0+6 = 1+1+4 = 3+3+0 also three combinations .

    CaseIII :  p=q=r which leads to only one possibility :  6 = 2+2+2


    I use  \binom{a~b~c}{A~B~C} to denote the degrees and if two are in the same column , we will write  10^6 as  (2^a 5^A) (2^b 5^B )( 2^c 5^C ) three factors .

    Suppose  (a,b,c)~ (A,B,C) are distinct

     \binom{a~b~c}{A~B~C} has 3! = 6 permutations so we should have  3! \times 3 \times 3 = 54 counts .



     \binom{a~b~c}{A~A~C} has  3!/2 = 3 permutations but since it is not convertable we should count  3 \times 3 \times 3 \times 2 = 54



     \binom{a~a~c}{A~A~C} we could count  2 \times 3 \times 3 = 18


     \binom{a~a~a}{A~B~C} we have  1\times 1 \times 3 \times 2 = 6

     \binom{a~a~a}{A~A~C} we have  1\times 1 \times 3 \times 2 = 6

     \binom{a~a~a}{A~A~A} we have  1


    Therefore , we have totally  54+54+18+6+6+1 = 139 possible ways to write but we have to limit the factors to be greater than one so let's first count how many combinations there are :

    Actually , that number is equal to the number of the different positive factors not exceeding  \sqrt{10^6} = 1000 which is  \frac{ 7\times 7 + 1}{2} = 25

    The answer should be  139 - 25 = 114
    Last edited by simplependulum; June 6th 2010 at 10:15 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    I have confirmed simplependulum's answer using brute force methods.

    Code:
    (2, 2, 250000)
    (2, 4, 125000)
    (2, 5, 100000)
    (2, 8, 62500)
    (2, 10, 50000)
    (2, 16, 31250)
    (2, 20, 25000)
    (2, 25, 20000)
    (2, 32, 15625)
    (2, 40, 12500)
    (2, 50, 10000)
    (2, 80, 6250)
    (2, 100, 5000)
    (2, 125, 4000)
    (2, 160, 3125)
    (2, 200, 2500)
    (2, 250, 2000)
    (2, 400, 1250)
    (2, 500, 1000)
    (2, 625, 800)
    (4, 4, 62500)
    (4, 5, 50000)
    (4, 8, 31250)
    (4, 10, 25000)
    (4, 16, 15625)
    (4, 20, 12500)
    (4, 25, 10000)
    (4, 40, 6250)
    (4, 50, 5000)
    (4, 80, 3125)
    (4, 100, 2500)
    (4, 125, 2000)
    (4, 200, 1250)
    (4, 250, 1000)
    (4, 400, 625)
    (4, 500, 500)
    (5, 5, 40000)
    (5, 8, 25000)
    (5, 10, 20000)
    (5, 16, 12500)
    (5, 20, 10000)
    (5, 25, 8000)
    (5, 32, 6250)
    (5, 40, 5000)
    (5, 50, 4000)
    (5, 64, 3125)
    (5, 80, 2500)
    (5, 100, 2000)
    (5, 125, 1600)
    (5, 160, 1250)
    (5, 200, 1000)
    (5, 250, 800)
    (5, 320, 625)
    (5, 400, 500)
    (8, 8, 15625)
    (8, 10, 12500)
    (8, 20, 6250)
    (8, 25, 5000)
    (8, 40, 3125)
    (8, 50, 2500)
    (8, 100, 1250)
    (8, 125, 1000)
    (8, 200, 625)
    (8, 250, 500)
    (10, 10, 10000)
    (10, 16, 6250)
    (10, 20, 5000)
    (10, 25, 4000)
    (10, 32, 3125)
    (10, 40, 2500)
    (10, 50, 2000)
    (10, 80, 1250)
    (10, 100, 1000)
    (10, 125, 800)
    (10, 160, 625)
    (10, 200, 500)
    (10, 250, 400)
    (16, 20, 3125)
    (16, 25, 2500)
    (16, 50, 1250)
    (16, 100, 625)
    (16, 125, 500)
    (16, 250, 250)
    (20, 20, 2500)
    (20, 25, 2000)
    (20, 40, 1250)
    (20, 50, 1000)
    (20, 80, 625)
    (20, 100, 500)
    (20, 125, 400)
    (20, 200, 250)
    (25, 25, 1600)
    (25, 32, 1250)
    (25, 40, 1000)
    (25, 50, 800)
    (25, 64, 625)
    (25, 80, 500)
    (25, 100, 400)
    (25, 125, 320)
    (25, 160, 250)
    (25, 200, 200)
    (32, 50, 625)
    (32, 125, 250)
    (40, 40, 625)
    (40, 50, 500)
    (40, 100, 250)
    (40, 125, 200)
    (50, 50, 400)
    (50, 80, 250)
    (50, 100, 200)
    (50, 125, 160)
    (64, 125, 125)
    (80, 100, 125)
    (100, 100, 100)
    
    114 ways found.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Our mathematical mind is finally at peace
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Jan 2009
    Posts
    715
    Thanks undefined ,

    I was afraid if the answer is wrong , all the steps i wrote will be thrown to the rubbish bin ... but how did you confirm this ? using your computer ? not using hands , right ?
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by simplependulum View Post
    Thanks undefined ,

    I was afraid if the answer is wrong , the steps i wrote will be thrown to rubbish bin ... but how did you confirm this ? using your computer ? not using hands , right ?
    Yep, using a computer. The code is a bit of a hodge-podge because I re-used old code for integer factorisation (using a smallest prime sieve algorithm). It was easier to re-use code, even though a method to get the factors of 10^6 wouldn't take many lines. After getting the factors, I just used three nested loops. No need to optimise with such small numbers.

    Code:
    import java.util.ArrayList;
    import java.util.Collections;
    
    public class ProdThreeFactors {
        
        static int L1 = 1000001;
        static int[] smallestP = new int[L1]; // smallest prime factor
        
        public static void init() {
            for (int i = 2; i < L1; i++)
                if (smallestP[i] == 0) {
                    smallestP[i] = i;
                    for (int j = i + i; j < L1; j += i)
                        if (smallestP[j] == 0) smallestP[j] = i;
                }
        }
        
        public static void main(String[] args) {
            long time = System.currentTimeMillis();
            int count = 0;
            init();
            ArrayList<Integer> facts = getFacts(1000000);
            for (int i = 1; i < facts.size(); i++)
                for (int j = i; j < facts.size(); j++)
                    for (int k = j; k < facts.size(); k++) {
                        long d1 = facts.get(i);
                        long d2 = facts.get(j);
                        long d3 = facts.get(k);
                        if (d1*d2 < 1000000 && d1*d2*d3 == 1000000) {
                            System.out.println("(" + d1 + ", " + d2 + ", " + d3 + ")");
                            count++;
                        }
                    }
            System.out.println("\n" + count + " ways found.");
            System.out.println("Elapsed: " + (System.currentTimeMillis() - time) / 1000.0 + " s");
        }
        
        public static ArrayList<Integer> getFacts(int n) {
            // returns list of factors of n in ascending order.
            ArrayList<Integer> ret = getFactors(n);
            Collections.sort(ret);
            return ret;
        }
        
        public static ArrayList<Integer> getFactors(int n) {
            // returns list of factors of n, not necessarily in ascending order.
            if (n >= L1) {
                System.out.println("Error: smallest prime sieve limit exceeded.");
                return null;
            }
            ArrayList<Integer> ret = new ArrayList<Integer>();
            if (n == 1) {
                ret.add(1);
                return ret;
            }
            ArrayList<Integer> primeFactors = canonicalise(factorise(n));
            getFactorsHelper(0, ret, primeFactors, 1);
            return ret;
        }
        
        public static void getFactorsHelper(int ind, ArrayList<Integer> factors,
                ArrayList<Integer> primeFactors, int prod) {
            if (ind == primeFactors.size()) {
                factors.add(prod);
                return;
            }
            int currPrime = primeFactors.get(ind), currPrimePow = 1;
            int multiplicity = primeFactors.get(ind + 1);
            for (int i = 0; i <= multiplicity; i++) {
                getFactorsHelper(ind + 2, factors, primeFactors, prod * currPrimePow);
                currPrimePow *= currPrime;
            }
        }
        
        public static ArrayList<Integer> canonicalise(ArrayList<Integer> pFacts) {
            // input is list of prime factors with duplicates allowed, not necessarily in
            // ascending order.
            // output is an even-sized list of primes p_i each followed by exponent a_i in
            // ascending order.
            // composition of functions is useful for factoring n = n_1 * n_2 * ... * n_r where
            // the n_i are known, to ease combining of lists for the n_i.
            if (pFacts == null || pFacts.isEmpty()) return pFacts;
            ArrayList<Integer> canon = new ArrayList<Integer>();
            Collections.sort(pFacts);
            while (!pFacts.isEmpty()) {
                int currPrime = pFacts.remove(0);
                int multiplicity = 1;
                while (pFacts.size() > 0 && pFacts.get(0).equals(currPrime)) {
                    pFacts.remove(0);
                    multiplicity++;
                }
                canon.add(currPrime);
                canon.add(multiplicity);
            }
            return canon;
        }
        
        public static ArrayList<Integer> factorise(int n) {
            // output is list of prime factors in ascending order, duplicates allowed.
            if (n < 1) return null;
            if (n < 2) return new ArrayList<Integer>();
            if (n >= L1) {
                System.out.println("Error: smallest prime sieve limit exceeded.");
                return null;
            }
            ArrayList<Integer> factors = new ArrayList<Integer>();
            int p = smallestP[n];
            factors.add(p);
            n /= p;
            while (n % p == 0) {
                factors.add(p);
                n /= p;
            }
            if (n == 1) return factors;
            factors.addAll(factorise(n));
            return factors;
        }
    }
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. A Challenging PDE question
    Posted in the Differential Equations Forum
    Replies: 5
    Last Post: August 30th 2011, 05:18 AM
  2. Challenging Calculus question
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 2nd 2010, 03:07 PM
  3. A Challenging Question
    Posted in the Advanced Statistics Forum
    Replies: 10
    Last Post: August 15th 2009, 06:03 PM
  4. Challenging question?
    Posted in the Algebra Forum
    Replies: 1
    Last Post: July 1st 2008, 02:34 AM
  5. Please help... challenging Integral Question
    Posted in the Calculus Forum
    Replies: 10
    Last Post: November 20th 2007, 06:06 PM

Search Tags


/mathhelpforum @mathhelpforum