Challenge 77: Product-Pairing 2019 Omegas

Share
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

Comments • 65

  • マイマイひかり
    マイマイひかり 6 months ago

    My answer is 040
    The value of expression I yielded is 2028040

  • Pika250
    Pika250 6 months ago

    Stressing 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 Das
    Swagato Das 6 months ago +1

    When are we gonna get it's solution....

  • The vast universe
    The vast universe 6 months ago

    Hello, I wrote my answer on this video, it is 170, can you check the solution?
    usclip.net/video/WxRF1yel1mU/video.html

  • Simon Armstrong
    Simon Armstrong 7 months ago

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

  • PhigNewton1
    PhigNewton1 7 months ago

    I 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 Sharma
    Kartik Sharma 7 months ago

    sorry for the link but now all links are open ...

  • Anubhab Ghosal
    Anubhab Ghosal 7 months ago

    Ans: 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 Banerjee
      Aswini Banerjee 6 months ago

      ......well well well are you curious to see the answer with solution

    • Aswini Banerjee
      Aswini Banerjee 6 months ago

      Quit it , it's not your cup of tee

    • Aswini Banerjee
      Aswini Banerjee 6 months ago

      Then why after all you posted the question there as you had already worked it out???

    • Aswini Banerjee
      Aswini Banerjee 6 months ago

      But it seems that the situation is much more critical than the previous

    • Anubhab Ghosal
      Anubhab Ghosal 6 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 Debortoli
    Pierlorenzo Debortoli 7 months ago

    hello from pizza e spaghetti

  • Francesco Debortoli
    Francesco Debortoli 7 months ago

    So 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 Tan
    Xu Chen Tan 7 months ago

    I 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 tapa
    el tapa 7 months ago

    I cannot wait to the Solution video, this looks interesting

  • Kartik Sharma
    Kartik Sharma 7 months ago

    drive.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 🔴🔵
    Smokie Bear 🔴🔵 7 months ago +3

    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 erena
    mark erena 7 months ago

    The 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

  • UbuntuLinux
    UbuntuLinux 7 months ago +8

    Me:
    74 - This is easy
    75 - Uhm this is a little bit hard
    77 - Wtf is this...

  • adandap
    adandap 7 months ago

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

  • Furious Fthefics
    Furious Fthefics 7 months ago

    I have done wrong

  • Rishav Gupta
    Rishav Gupta 7 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

  • Furious Fthefics
    Furious Fthefics 7 months ago

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

    • LetsSolveMathProblems
      LetsSolveMathProblems  6 months ago

      I 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 Mukhopadhyay
    Arunabha Mukhopadhyay 7 months ago

    019 ?

  • PhigNewton1
    PhigNewton1 7 months ago

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

    • LetsSolveMathProblems
      LetsSolveMathProblems  7 months ago

      Overall, 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 Dewan
    Bisham Dewan 7 months ago

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

    • LetsSolveMathProblems
      LetsSolveMathProblems  7 months ago

      Could 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 erena
    mark erena 7 months ago

    Is the answer 190? Can you verify that?
    If yes i will try to proof it

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

    • LetsSolveMathProblems
      LetsSolveMathProblems  7 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 Zox
    Nitro Zox 7 months ago +4

    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 balaji
      shashank balaji 6 months ago

      @LetsSolveMathProblems I didn't know about the second case. Thank you!

    • ThiagoFo888
      ThiagoFo888 7 months ago

      Wtf is this '-'

    • shashank balaji
      shashank balaji 7 months ago +1

      @Nitro Zox Yes. So, |w^k| = 1

    • Nitro Zox
      Nitro Zox 7 months ago

      @LetsSolveMathProblems is it 190 as i got 1010x2019

    • Nitro Zox
      Nitro Zox 7 months ago

      eq 1+i+i^2 = 1(i^3-1)/(i-1) = (1+i)/(1-i) = (1+i)^2/2 = 2i/2 = i

  • Carlos Olimpio
    Carlos Olimpio 7 months ago

    Maths

  • Carlos Olimpio
    Carlos Olimpio 7 months ago

    3