# Challenge 77: Product-Pairing 2019 Omegas

Embed

**Published on Jan 24, 2019**- Congratulations to Minh Cong Nguyen, mark erena, iQuickdraw X, and Xu Chen Tan for successfully solving the last week's math challenge question! Minh Cong Nguyen 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.

For more Weekly Math Challenges:

usclip.net/p/PLpoKXj-PWCbaDXYHES37_zX4O-kCWxguM

マイマイひかり4 months agoMy answer is 040

The value of expression I yielded is 2028040

Pika2504 months agoStressing the importance of the "J not equal to K" in the product. If we allow J = K in each product, we would have Ω^J - Ω^J = 0, meaning the entire product is 0, which in turn would imply the entire sum, where all summands are 0s, is itself 0.

Swagato Das4 months ago^{+1}When are we gonna get it's solution....

LetsSolveMathProblems4 months agoIt should be posted within an hour. =)

The vast universe4 months agoHello, I wrote my answer on this video, it is 170, can you check the solution?

usclip.net/video/WxRF1yel1mU/video.html

Simon Armstrong4 months agoSo I think i took a slightly long and tedious method.

Answer is 170. Solution is a pdf at sasha.sector-alpha.net/~staircase/Challenge_77__Product_Pairing_2019_Omegas.pdf.

In summary I split the sum and product apart by rearranging and using omega^2020 = 1 to shift limits around.

Perform the sum by partial fractioning, then using sum or roots of unity and forcing the other term into real and imaginary parts.

Perform the remaining product by introducing a limit multiplying the product by (z-1)/(z-1) and then using the product of (z-z0) where z0 are all the 2020th roots of unity is z^2020-1.

Finally preform the limit, combine the terms and simplify to get a single number.

PhigNewton14 months agoI fixed my mistake from before, and I didn't see another comment with the same answer, so I might as well repost my answer. I answer is 010:

Part 1:

Looking at Product[Omega^k-Omega^j] from j=1 to 2019, j!=k, we can simplify this. Multiply and divide what the term would be if j=2020, and we get 1/(Omega^k-1)*Product[Omega^k-Omega^j] from j=1 to 2020, j!=k. We can take out Omega^k from each term in the product, getting (Omega^2019*k)/(Omega^k-1)*Product[1-Omega^(j-k)] from j=1 to 2020, j!=k. Substituting u in for j-k, we get a new product that's independent of k: (Omega^-k)/(Omega^k-1)*Product[1-Omega^(u)] from u=1 to 2019.

Part 2:

To find out the value of Product[1-Omega^(u)] from u=1 to 2019, we must rewrite the product as lim z-> 1 (1/(z-1)Product[z-Omega^(u)] from u=1 to 2020), giving us two polynomials dividing each other. The product is a polynomial with all of its roots corresponding to the 2020-roots of unity. This means that the whole product at the beginning of this part is equal to lim z->1([z^2020-1]/[z-1]). Using L'Hopital's Rule, we get lim z->1 (2020*z^2019/1) or just 2020.

Part 3:

Plugging in our results from Part 1 and Part 2 into our original equation, we get -2020*Sum[Omega^-k*(1/(1-Omega^k))] from k=1 to 2019. The(1/(1-Omega^k)) of the summation are the points on the circumference of a circle centered at z=1 being reflected across the circumference of a circle centered at z=0, both with radius 1. Since the former circle goes through the center of the latter, we get a series of points along the line 1/2+ai with symmetry across the real-line. The sum is now -2020*Sum[Omega^-k*(1/2+a*i)] from k=1 to 2019. Because of the symmetry across the real-line, the imaginary terms cancel out to 0i, so we have -1010*Sum[Omega^k] from k=1 to 2019. If we add and subtract what the term in the summation would be if k=0, we get 1010-1010*Sum[Omega^k] from k=1 to 2020. The summation is of all of the points around a circle centered at zero, so it equals zero in the end, leaving us with only 1010 as the answer.

I find this answer suspicious, considering how almost every other answer given so far involves (2020 choose 2), but oh well.

Kartik Sharma4 months agosorry for the link but now all links are open ...

Anubhab Ghosal4 months agoAns: 170 Full Answer: 2037170 Solution: Each summand equals 2020w^2019k/(w^k-1) by l'Hospital's rule. Answer=2020(sum(1/w^k-1/(w^k-1)))= -2020+ 2020choose2=2037170.

2037170 is the number of diagonals in a 2020-gon. This is true in general.

And, by the way, your weekly challenges are not that challenging(don't mean to be rude), so you should also host some monthly challenges for really challenging and interesting questions. For example, prove that there is no function f from NU{0}toNU{0}, such that f(f(n))=n+k for all n in NU{0} where k is a fixed positive odd integer. This is probably an old IMO Problem

Aswini Banerjee4 months ago......well well well are you curious to see the answer with solution

Aswini Banerjee4 months agoQuit it , it's not your cup of tee

Aswini Banerjee4 months agoThen why after all you posted the question there as you had already worked it out???

Aswini Banerjee4 months agoBut it seems that the situation is much more critical than the previous

Anubhab Ghosal4 months ago@Aswini Banerjee If you have not noticed, last question was posted on Stack Exchange after I answered it here. And I posted the answer and the question simultaneously on stackexchange.

Pierlorenzo Debortoli4 months agohello from pizza e spaghetti

Francesco Debortoli4 months agoSo w = e^(pi*i/1010) = e^(2*pi*i/2020). Let's fix k for a moment. So we have product from j=1, j!= k, to 2019 of (w^k - w^j). We can factor out the w^k. So we get w^k*(product from j = 1, j!=k, to 2019 of (1 - w^(j-k))). Notice we get the product ranging all over the 2020 roots of unity except 1 and w^(-k). So let's write w^k/(1-w^(-k))*(1-w)*(1-w^2)*(1-w^3)...(1-w^(2019)). We have 1-x^2020 = (x-1)(x-w)...(x-w^2019) so -(1+...+x^2019) = (x-w)*...*(x-w^2019). For x = 1 we get that our product is equal to -2020*w^k/(1-w^(-k))... remember that at the beginning of our sum we had a minus sign... so now we are looking for 2020*(sum from k = 1 to 2019 of w^k/(1-w^(-k)). Let's sum w^k/(1-w^(-k))+w^(-k)/(1-w^(k)) = w^k + w^(-k) + 1 Remember we are ranging from 1 to 2019 so we can pair up 1 to -1, ... but 1010 remains alone. So our sum becomes 2020*(1009+(-1)/(1-(-1)) = 2020*(1009-1/2) = 2037170, so our final answer is 170

Xu Chen Tan4 months agoI just found some magic. Let n=2020.

Well known that

x^n-1 = product(0 to n-1) (x-w^k)

product(1 to n-1, not k) (x-w^j)

= (x^n-1)/(x-1)(x-w^k)

= (nx^(n-1))/(x-1+x-w^k) by L' H when x = w^k

= -n w^-k/(1-w^k)

= -n ( w^k/(1-w^k) + 1 + w^-k )

(magic step 1)

Let x_k = w^k/(1-w^k)

Then w^k = (x+1)/x

Since the roots of x^n-1 are precisely w^k, the roots of

(x+1)^n/x^n - 1 are precisely x_k.

(x+1)^n - x^n = nx^(n-1) + n(n-1)/2 x^(n-2) + ... is a degree n-1 polynomial with x_k as it's n-1 roots. Hence sum(x_k) = -(n-1)/2 by vieta's. (magic step 2)

Sum of 1 is obviously n-1.

Sum of w^-k is -1 since it's all roots of unity except 1.

So total sum is

-(-n)( -(n-1)/2 + (n-1) + (-1) )

= n(n-3)/2

2020*2017/2 ends in 170.

el tapa4 months agoI cannot wait to the Solution video, this looks interesting

Kartik Sharma4 months agodrive.google.com/file/d/19MEOgb1K4Mi9DuvzCq3nUVjyh9_yyeES/view?usp=drivesdk

drive.google.com/file/d/1UPmzOctoVApVHDXSDtPoMdYJYCaWHrsq/view?usp=drivesdk

drive.google.com/file/d/15PB6UvH7J7X1vr86WjHutoz04V1kbZSk/view?usp=drivesdk

My solution

The answer is 170

1010(2017)

Smokie Bear 🔴🔵4 months ago^{+2}The answer is 170 because this is week 77 and e is to the power of 1010 and the last three digits are 010 which is just 10. So 77 * 10 is 770, then you have to subtract 600 due to the Lagrange error bound to get the final answer as 170

mark erena4 months agoThe answer is 170.

I used the fact that w is 2020th root of unity and rewrote the product after dealing with a limit and l'hopital's rule. I also used some root properties and after everything I got 2020*(1009+1/2-1)= 2020*(1009 -1/2)= 2020* 1008,5=2037170. Thus 170

UbuntuLinux4 months ago^{+8}Me:

74 - This is easy

75 - Uhm this is a little bit hard

77 - Wtf is this...

adandap4 months agoWithout a whole lot of confidence, the answer is 190.

First, pull a factor of exp(i w^k) out of each term in the product to get exp(2018 i k pi/1010) which is taken out of the j-dependent part. Then, for the remaining product (which looks like (1-exp(j-k) omega) ), for any value of k (except for 1010, which I'll deal with in a minute) the product contains 1008 pairs of the form (1-exp(i a) ) * (1-exp(-i a) ) which is 4 sin^2(a/2), as well as one term of the form (1 - exp(+- i pi))=2 and one of the form (1 - exp(-i k pi/1010) ). Adding the terms pairwise (for example the k=1 and k= 2019 terms, or 2 and 2018) the unpaired terms then pair up to give 2^2019 Prod(sin^2(n pi/2020) - where the product runs from n=1 to 1009. The k=1010 term is similar, but everything pairs up to give 2^2018 times the same product of sines^2. Then the k summation is simply a geometric series and can be evaluated to give s = x (1-x^2019)/(1-x) where x = exp(i*2018*pi/1010). s is also known as -1, so the overall answer is (1009 * 2^2019 + 2^2018) * product of sines. Analytically, we're done, but we need a number.

Now, the product is a number of order 10^(-605) and the 1009*2^2019 + 2^2018 is ~ 10^610, so precision is tricky. But I think I tortured Mathematica into telling me that the product of the two is 2039190, which is 190 mod(1000).

Man, that was a lot of algebra, and the Z^2020-1 solution below is soooo much nicer! I'll try that next.

Trishan Mondal4 months agoI have done wrong

Rishav Gupta4 months ago^{+2}The answer is 170

The hint is in title of video

First

z^2020-1=(z-w)(z-w^2)(z-w^3)...(z-w^2020)

Since e^2pi/2020 is 2020th root of unity

z^2020-1/(z-1)(z-w^k)=our required product at w^k=z

Now by applying l hospitals rule

On lhs

We get

2020w^2019k/w^k-1since there is - sign before

We get

2020w^2019k/1-w^k

Now let us put 2020 aside and compute

w^2019k/1-w^k

On multiplyin above and below by w^k

We get 1/w^k(1-w^k)

By breaking partial fractions we get

1/(1-w^k)+1/w^k

Summing

1/w^k=w^2020-k

=w^2019+w^2018......w

Sum of roots =0 since coof of z^2019=0

Thus w^2020+w^2019.....w=0

w^2019+w^2018......w=-1

Now summing

1/1-w^k

1/1-w^1+1/1-w^2.... 1/1-w^2019

On pairing 1st and last term

1/1-w+1/(1-1/w)

1/1-w+w/w-1=1

Similarly we get 1009 1s and middle term that is 1/1-w^2010=1/1-e^ipi=1/2

Thus result is2020× (1009+(1/2)-1)

2020×(1009-1/2)=2037170

Thus answer is 170

Trishan Mondal4 months agodrive.google.com/file/d/1dbm4lkw4074lM0Eo7F3xbLfx3nSee0Dn/view?usp=drivesdk

LetsSolveMathProblems4 months agoI could not read your solution because its access mode is not set to public. Starting with the next challenge, you should make your answer public if you link it via Google Drive.

Arunabha Mukhopadhyay4 months ago019 ?

PhigNewton14 months agoThe answer is -190. I found a better solution than the one I had:

Part 1:

Looking at Product[Omega^k-Omega^j] from j=1 to 2019, j!=k, we can simplify this. Multiply and divide what the term would be if j=2020, and we get 1/(Omega^k-1)*Product[Omega^k-Omega^j] from j=1 to 2020, j!=k. We can take out Omega^k from each term in the product, getting (Omega^k)/(Omega^k-1)*Product[1-Omega^(j-k)] from j=1 to 2020, j!=k. Substituting u in for j-k, we get a new product that's independent of k: (Omega^k)/(Omega^k-1)*Product[1-Omega^(u)] from u=1 to 2019.

Part 2:

To find out the value of Product[1-Omega^(u)] from u=1 to 2019, we must rewrite the product as lim z-> 1 (1/(z-1)Product[z-Omega^(u)] from u=1 to 2020), giving us two polynomials dividing each other. The product is a polynomial with all of its roots corresponding to the 2020-roots of unity. This means that the whole product at the beginning of this part is equal to lim z->1([z^2020-1]/[z-1]). Using L'Hopital's Rule, we get lim z->1 (2020*z^2019/1) or just 2020.

Part 3:

Plugging in our results from Part 1 and Part 2 into our original equation, we get -2020*Sum[Omega^k/(1-Omega^k)] from k=1 to 2019. Since, for every k, every -k is also being included in the sum, we can further reduce the sum to -2020*Sum[1/(1-Omega^k)], from k=1 to 2019. The terms in the summation are the points on the circumference of a circle centered at z=1 being reflected across the circumference of a circle centered at z=0. Since the former circle goes through the center of the latter, we get a series of points along the line 1/2+ai with symmetry across the real-line. The average of these points is 1/2, so when they all add together, they equal 1/2*2019. Plugging this value back into the original formula, we get the final answer -2020*2019/2, or -(2020 choose 2).

This is my first challenge, and I just subscribed, so I hope I made a good first impression.

LetsSolveMathProblems4 months agoOverall, an outstanding solution. I find your geometric arguments quite lovely. However, your solution contains two errors, both of them somewhat subtle. Here is the more severe error (the other error is a small mistake on picking the right sign; the final result should be positive): notice that when you "take out Omega^k from each term in the product," you are not taking out Omega^k, but rather Omega^(k*2019). By the way, welcome to the channel! =)

Bisham Dewan4 months agoThe value of the given expression is 2037170, hence the last three digits are 170. Here w is the 2020th roots of unity, so expressing the given expression as the product of its roots and differentiate and after that put values of powers of w gives the result.

LetsSolveMathProblems4 months agoCould you repost another comment that shows a little bit more work? I need to see a few more steps explicitly written out (perhaps a few concrete formulas) before granting recognition.

mark erena4 months agoIs the answer 190? Can you verify that?

If yes i will try to proof it

adandap4 months ago^{+1}I can calculate the answer by hand in the limit as 2019-->3. Does that count? :)

But seriously, I almost have an answer I'd like to check. How do you get Mathematica to do a product where j takes all values except k? I tried a For loop with the compound test j != k; j

LetsSolveMathProblems4 months ago^{+2}I defined a function using an "If" method and computed sum/product of that function. Here's an example of "If" method: If[ x < 0, -x, x ] is the absolute value function. You have a condition followed by what happens if that condition is true, and then what happens if that condition is false.

Nitro Zox4 months ago^{+5}380.

Here consider the equation z^2020-1 = (z-1)(z-w).....(z-w^k)....(z-w^2019) (since w is the 2020th root of 1). Now, divide both sides by (z-1)(z-w^k) . Hence :

(z^2020-1)/(z-1)(z-w^k) = (z-w)(z-w^2)..... (z-w^2019). The RHS of the equation is the required product when z=w^k . As this product exists, we take the limiting value on LHS. Hence Using L hospital rule on LHS (As we need to put z=w^k 0/0 form) . Thus we get that the product is equal to -2020w^2019k/1-w^k. Taking the 2020 outside the summation, now we need to find summation of w^2019k/1-w^k. This looks like an infinite Gp( a/1-r) . Hence in expanded form we get summation of w^2019k + w^2020k ....... to infinite terms. Lets consider a general w^rk. Summing this up we get w^r(1-w^2019r)/(1-w^r). Taking the w^r inside the bracket, we get w^r - w^2020r / 1-w^r. But notice that w^2020 = 1 hence w^2020r =1 . So for any r , the sum of w^rk from 1 to 2019 is -1. Hence , we get 1+1+1..... 2019 times. So the actual answer is 2020x2019 = 4078380.

shashank balaji4 months ago@LetsSolveMathProblems I didn't know about the second case. Thank you!

ThiagoFo8884 months agoWtf is this '-'

shashank balaji4 months ago^{+1}@Nitro Zox Yes. So, |w^k| = 1

Nitro Zox4 months ago@LetsSolveMathProblems is it 190 as i got 1010x2019

Nitro Zox4 months agoeq 1+i+i^2 = 1(i^3-1)/(i-1) = (1+i)/(1-i) = (1+i)^2/2 = 2i/2 = i

Carlos Olimpio4 months agoMaths

Carlos Olimpio4 months ago3