Challenge 61: Comparing Polynomials

Share
Embed
  • Published on Oct 4, 2018
  • Congratulations to Hung Hin Sun, Kevin Tong, Minh Cong Nguyen, Aswini Banerjee, Joseph Ho, Rajat Khandelwal, Albanovaphi7, and Haradhan Datta for successfully solving the last week's math challenge question! Hung Hin Sun was the first person to solve the question.
    Your support is truly a huge encouragement.
    Please take a second to subscribe in order to send us your valuable support and receive notifications for new videos!
    Every subscriber and every like are wholeheartedly appreciated.
    Welcome, everyone! My channel hosts one weekly math challenge question per week (made by either myself, my family, or my friends), which will be posted every Wednesday. Please comment your proposed answer and explanation below! If you are among the first ten people with the correct answer, you will be recognized in the next math challenge video. The solution to this question and new question will be posted next Wednesday.

Comments • 33

  • LetsSolveMathProblems
    LetsSolveMathProblems  8 months ago +3

    *Due to an ambiguity in the statement of the problem, both 7/19 and 3/7 will be accepted (given that the explanation is adequate, of course). You have my sincere apology. Ambiguity arises in two different places. The first one is conspicuous: I should have written "uniformly random" instead of an ambiguous term "random." The second one is rather subtle. There are two ways of interpreting how p and q are picked: first interpretation is that a pair (p,q) is picked from the set of all pairs (p,q) such that p

    • adandap
      adandap 8 months ago

      Two different right answers and neither of them the one I got. Fantastic. I guess I am not worthy. :)

  • Bigg Barbarian
    Bigg Barbarian 8 months ago

    The answer is 3/7.
    1st) We observe p

  • Luca Rossetti
    Luca Rossetti 8 months ago

    #A means the number of elements in A
    If #Rp=1 we have four polynomials (you can choose the root in 4 different and for each case you have only One polynomial: (x-root)^4)
    If #Rp=2 we have 18 polynomials (you can choose the roots in two ways and for each set of roots you have three polynomials)
    In the same way you can calculate 12 polynomials with three roots and 1 polynomial with 4 roots.
    #P4= 35
    P(p=q) = sum over i [P(p=q|#Rp=i)* P(#Rp=i)], where i = 1,2,3,4
    P(p=q)=1*4/35 + 1/3 * 18/35 + 1/3 * 12/35 + 1 * 1/35 = 15/35 = 3/7

  • taflo1981
    taflo1981 8 months ago

    The probability is 7/19.
    There are 35 elements in P_4: 4 polynomials with exactly one root (4 ways to choose the root), 18 with exactly two different roots (4C2 = 6 choices for the roots and 3 choices for the multiplicities, namely [3,1], [2,2], and [1,3]), 12 with exactly three different roots (4C3 = 4 choices for the roots and 3 choices for which one has multiplicity two), and finally 1 polynomial with four different roots.
    Five of these polynomials are uniquely defined by their set of roots. Each of the other 30 polynomials shares its set of roots with two other elements of P_4. Thus, there are 5+30*3 = 95 possible pairs (p,q).
    The pair (p,q) is chosen randomly (it has not been stated in the question, but I will assume that it's chosen uniformly at random from the set of all pairs that satisfy both p

  • mrKreuzfeld
    mrKreuzfeld 8 months ago

    53/149

  • Hung Hin Sun
    Hung Hin Sun 8 months ago

    The answer is 7/19
    For Rp=Rq, we consider the four cases of set Rp having 1,2,3,4 elements, the corresponding number of pairs are 4x1x1=4, 6x3x3=54, 4x3x3=36 and 1x1x1=1. The total number is 95. Then the number of pairs with p and q being the same is 4x1+6x3+4x3+1x1=35. Hence the answer is 35/95=7/19.

  • Kenny Yip
    Kenny Yip 8 months ago

    7/19 is the answer
    P(p=q | p = q) = P(p=q) / P(p=q)
    There are 35 such polynomials in P4. To see that consider a+b+c+d=4, for non-negative integral solutions of a,b,c,d. It amounts to the permutation of 4 balls and 3 separators, so 7!/(3!4!) = 35. Therefore, P(p=q) = 1/35.
    Next, we look into the structure of the equivalent classes induced by (p

  • SeongKyun Jung
    SeongKyun Jung 8 months ago

    Total cases where Rp=Rq is 1(p and q have 4 roots)+36(choose p with 3 roots-12 cases × choose q with the same roots-3 cases)+18(choose p such that p is the square of a polynomial-6 cases × choose q with the same 2 roots-3 cases)+36(choose p with 2 roots but is the cube of a polynomial × a 1degree -12 × choose q with same roots- 3) +4 (1 root only) = 95
    Of those, the cases where p and q are identical is the same as the distinct cases available for p which is 35
    Therefore the answer is 35/95=7/19.

  • David Franco
    David Franco 8 months ago

    the answer is 3/7
    I get as follow:
    the problem can be see as
    P4 = (x-1)^e1 * (x-2)^e2 * (x-3)^e3 * (x-4)^e4
    such as
    0

  • iQuickdraw X
    iQuickdraw X 8 months ago

    Rp=Rq, think of the cases of Rp having 1,2,3,4 elements
    (4+4*3/2*3+4*3+1)/(4+4*3/2*9+4*9+1)=7/19

  • pichutarius
    pichutarius 8 months ago

    35/95 = 7/19
    using classic definition of probability,
    1. there are 95 ways to choose p and q such that p and q has same "distinct roots" , ie: p>=q , q>=p.
    2. there are 35 ways to choose p and q such that p and q have same roots , ie: p,q are same polynomial.
    3. 35/95 = 7/19 . the answer was double checked using some coding, so it should be correct, unless i misunderstood the question. (honestly, its quite confusing)
    more working on request (usclip.net/video/blQNNAL-900/video.html&lc=z22cclfxiq3mv5lr104t1aokg31hzdtxvcgpqge3oxwebk0h00410.1538620197593981)
    1. group by 1,2,3,4 distinct roots. each having
    (1 dist root) B(4,1) = 4
    (2 dist root) B(4,2) * 3 * 3 = 54
    (3 dist root) B(4,3) * 3 * 3 = 36
    (4 dist root) B(4,4) = 1
    which sum to 4 + 54 + 36 + 1 = 95
    2. group by 1,2,3,4 distinct roots. each having
    (1 dist root) B(4,1) = 4
    (2 dist root) B(4,2) * 3 * 1 = 18
    (3 dist root) B(4,3) * 3 * 1 = 12
    (4 dist root) B(4,4) = 1
    which sum to 4 + 18 + 12 + 1 = 35
    3. 35/95 = 7/19
    this is not a full explanation, just to prove i know where the numbers came from. a full explanation might be "too large to fit into the margin" : )

    • pichutarius
      pichutarius 8 months ago

      thanks.
      btw B(n,k) means binomial coefficient or choose function (n choose k)

    • LetsSolveMathProblems
      LetsSolveMathProblems  8 months ago

      What you wrote is more than sufficient. =)

  • adandap
    adandap 8 months ago

    I think the answer is 5/9. We want to calculate the conditional probability that p=q given that R_p = R_q. There are 15 possible R_p. Of those, five of them guarantee that p = q: {1}… {4} and {1,2,3,4} Of the others {1,2}…. {3,4} (six of those) and {1,2,3}… {2,3,4} (four of those) there is a one in three chance that p=q since they each correspond to three different polynomials. So our required answer is
    Pr = 5/15 * 1 + 10/15 *1/3 = 25/45 = 5/9.

  • pichutarius
    pichutarius 8 months ago +1

    35/95 = 7/19
    using classic definition of probability,
    there are 95 ways to choose p and q such that p and q has same "distinct roots" , ie: p>=q , q>=p.
    there are 35 ways to choose p and q such that p and q have same roots , ie: p,q are same polynomial.
    the answer was checked using some coding, so it should be correct, unless i misunderstood the question. (honestly, its quite confusing)

    • LetsSolveMathProblems
      LetsSolveMathProblems  8 months ago +1

      I need you to show a little bit more work on how you obtained 95 and 35 OR post a snippet of your program with a little explanation underneath it. =) (Repost your comment instead of replying to this one.)

  • Minh Cong Nguyen
    Minh Cong Nguyen 8 months ago +1

    The answer is 7/19.
    First, we are assuming that P4 is the set of all monic polynominal in x of degree 4 with all 4 real roots and each real roots is either 1,2,3, or 4. In other words if p∈P4 then p=(x-a)(x-b)(x-c)(x-d) where a,b,c,d is 1,2,3, or 4.
    With that assumption, P4 is the set of exactly 35 of polynominals, belonged to 15 groups (which can be grouped as 5 groups of 1 and 10 groups of 3), corresponding to the following value of (a,b,c,d):
    (1,1,1,1)
    (2,2,2,2)
    (3,3,3,3)
    (4,4,4,4)
    (1,2,3,4)
    (1,1,1,2) (2,2,2,1) (1,1,2,2)
    (1,1,1,3) (3,3,3,1) (1,1,3,3)
    (1,1,1,4) (4,4,4,1) (1,1,4,4)
    (2,2,2,3) (3,3,3,2) (2,2,3,3)
    (2,2,2,4) (4,4,4,2) (2,2,4,4)
    (3,3,3,4) (4,4,4,3) (3,3,4,4)
    (1,1,2,3) (2,2,1,3) (3,3,1,2)
    (1,1,2,4) (2,2,1,4) (4,4,1,2)
    (1,1,3,4) (3,3,1,4) (4,4,1,3)
    (2,2,3,4) (3,3,2,4) (4,4,2,3)

    For p,q∈P4 , p

  • Walker Powell
    Walker Powell 8 months ago

    If p leq q and q leq p, then R_p = R_q, so the have the same roots. The only difference in the polynomials can come in the multiplicity of the roots. We now count how many polynomials satisfy this property counting by number of distinct roots:
    4 roots: 1
    3 roots: 3 (3 choices for multiplicity 2 root)
    2 roots: 3 (1 of 2+2 multiplicity and 2 of 1+3 multiplicity)
    1 root: 1
    So for p with 1,2, or 4 distinct roots, p=q and for 3 distinct roots, p=q with probability 1/3. We now need to find the probabilities that we draw a p of each distinct root count. We now count polynomials in P_4 with each number of distinct roots.
    4 roots: 1
    3 roots: 4*3*2/2 = 12 (1+1+2 multiplicities)
    2 roots: 4*3/2 + 4*3 = 18 (2+2 and 3+1 multiplicities)
    1 root: 4
    Total: 35
    So we have
    P(p=q) = 1/35+12/35*(1/3)+18/35*(1/3)+4/35 = 15/35 = 3/7

  • Benjamin Wang
    Benjamin Wang 8 months ago

    To try to answer this properly, I thought answer is 7/13. I thought there are 65 ways for polynomial to have four roots satisfying conditions. This comes from 1*1+4*6+6*6+4*1 (the terms come from 4, 3, 2, and 1 distinct roots). And then there are 35 ones giving exactly p=q. This comes from 1+3*4+3*6+1*4 (similar as above).

  • ChickenBird
    ChickenBird 8 months ago

    I believe there are 69 possible sets of Rp and thus 69 sets of Rq, the likelihood that Rp=Rq = 1/69^2 or 1/4761

    • ChickenBird
      ChickenBird 8 months ago

      @Walker Powell yep I just realized that lol

    • Walker Powell
      Walker Powell 8 months ago

      You are trying to find the probability that if 2 polynomials with the same roots NOT COUNTING MULTIPLICITY are the same

  • Walker Powell
    Walker Powell 8 months ago

    If p leq q and q leq p, then R_p = R_q, so the have the same roots. The only difference in the polynomials can come in the multiplicity of the roots. We now count how many polynomials satisfy this property counting by number of distinct roots:
    4 roots: 1
    3 roots: 3 (3 choices for multiplicity 2 root)
    2 roots: 1 (both roots have multiplicity 2)
    1 root: 1
    So for p with 1,2, or 4 distinct roots, p=q and for 3 distinct roots, p=q with probability 1/3. We now need to find the probabilities that we draw a p of each distinct root count. We now count polynomials in P_4 with each number of distinct roots.
    4 roots: 1
    3 roots: 4*3*2 = 24 (1+1+2 multiplicities)
    2 roots: 4*3 + 4*3 = 24 (2+2 and 3+1 multiplicities)
    1 root: 4
    Total: 53
    So we have
    P(p=q) = 4/53*(1)+24/53*(1)+24/53*(1/3)+1/53*1 = (4+24+8+1)/53 = 37/53

    • Walker Powell
      Walker Powell 8 months ago

      I messed up the counts of 3 and 2 counts as well as that there are 3 q's that equal p for 2 roots. There are 4*3*2/2 = 12 3 root polynomials and 4*3/2+4*3 = 18 2 root polynomials, for a total of 1+4+12+18 = 35 polynomials. Therefore the answer is 1/35+12/35*(1/3)+18/35*(1/3)+4/35 = (1+4+6+4)/35 = 15/35 = 3/7. I will repost my comment.

  • Cobalt314
    Cobalt314 8 months ago

    Answer: 3/7
    We can count 35 possible distinct ways to give a polynomial 4 roots, each of which comes from the set {1,2,3,4}. Of these 35 polynomials, only one has all 4 of these roots, 12 have 3 distinct roots, 18 have 2 distinct roots, and 4 have four of the same root. Now, if p

  • Benjamin Wang
    Benjamin Wang 8 months ago

    On second thought, the probability is zero. Since if the polynomials have no roots, all the conditions are satisfied (every root is 1,2,3, or 4; Rp=Rq). Since there are an infinite number of such, it is almost impossible for two polynomials to be equal.

    • Benjamin Wang
      Benjamin Wang 8 months ago

      Thank you. If roots are in C then of course. Haha i'm way too tired for this

    • LetsSolveMathProblems
      LetsSolveMathProblems  8 months ago +1

      p must have roots due to Fundamental Theorem of Algebra. You may assume that every coefficient of p is a complex number.

    • Cobalt314
      Cobalt314 8 months ago

      Yes, this is true. However, as p is a degree 4 polynomial, it necessarily has to have at least one root (at least in the complex numbers, which I assume is what LSMP meant to use as the domain).

    • Benjamin Wang
      Benjamin Wang 8 months ago

      My point is, if p has no roots, than the statement "every root of p is either 1, 2, 3, or 4" is (vacuously) true. Sorry it's 2am here and all my answers might be hallucinating.

    • Cobalt314
      Cobalt314 8 months ago

      We know that these polynomials have roots in {1 2 3 4} because they're in P_4. The task is, given you know they have said roots, to figure out how likely it is they're the same polynomial.

  • Benjamin Wang
    Benjamin Wang 8 months ago

    Answer should be 1/8. We know R_p=R_q. We know cases: n different roots where n = 1 2 3 4.
    4: one possible polynomial; 3: 3x3 possible; 2: 3*6; 1: 1*4. There fore 32.
    Answer is 1/32+ 9/32*1/9 + 18/32*1/18 + 4/32* 1/4 = 1/8.