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.
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.

• 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

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

• Bigg Barbarian 8 months ago

1st) We observe p

• 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 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 8 months ago

53/149

• Hung Hin Sun 8 months ago

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 8 months ago

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 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

• David Franco 8 months ago

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 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 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 8 months ago

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

• LetsSolveMathProblems  8 months ago

What you wrote is more than sufficient. =)

• 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 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  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 8 months ago +1

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 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 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 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 8 months ago

@Walker Powell yep I just realized that lol

• 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 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 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 8 months ago

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 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 8 months ago

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

• 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 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 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 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 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.