# Challenge 61: Comparing Polynomials

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.

LetsSolveMathProblems8 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

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

Bigg Barbarian8 months agoThe answer is 3/7.

1st) We observe p

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

taflo19818 months agoThe 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

mrKreuzfeld8 months ago53/149

Hung Hin Sun8 months agoThe 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 Yip8 months ago7/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 Jung8 months agoTotal 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 Franco8 months agothe 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 X8 months agoRp=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

pichutarius8 months ago35/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" : )

pichutarius8 months agothanks.

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

LetsSolveMathProblems8 months agoWhat you wrote is more than sufficient. =)

adandap8 months agoI 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.

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

LetsSolveMathProblems8 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 Nguyen8 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 Powell8 months agoIf 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 Wang8 months agoTo 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).

ChickenBird8 months agoI 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

ChickenBird8 months ago@Walker Powell yep I just realized that lol

Walker Powell8 months agoYou are trying to find the probability that if 2 polynomials with the same roots NOT COUNTING MULTIPLICITY are the same

Walker Powell8 months agoIf 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 Powell8 months agoI 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.

Cobalt3148 months agoAnswer: 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 Wang8 months agoOn 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 Wang8 months agoThank you. If roots are in C then of course. Haha i'm way too tired for this

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

Cobalt3148 months agoYes, 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 Wang8 months agoMy 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.

Cobalt3148 months agoWe 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 Wang8 months agoAnswer 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.