Challenge 64: Can You Avoid This Dyck Path?

Share
Embed
  • Published on Oct 25, 2018
  • * On the final slide of the problem statement, perhaps I should have written "Let a Dyck path of length 2n be good..." instead of "Let a Dyck path be good..." to clarify the meaning of n in the second condition (although n appears in the first slide, a clarification that its meaning does not change through the slides was probably needed).
    Congratulations to Cobalt314, Jeremy Weissmann, Jaleb, Aswini Banerjee, Seth Harwood, Minh Cong Nguyen, Donovan B, Thomas Q, Bigg Barbarian, and adandap for successfully solving the last week's math challenge question! Cobalt314 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 • 23

  • Whipload Channel
    Whipload Channel 8 months ago +1

    How is UUUDD not valid? It fits the def

    • LetsSolveMathProblems
      LetsSolveMathProblems  7 months ago

      The definition states that we have to have n U's and n D's. That is, we must have the same number of U's and D's.

  • Czeckie
    Czeckie 8 months ago

    The answer is 080, more precisely the sum is 1018080.
    The conditions for good path force the words be of the form U^kD^jU^jD^k, with k>=j, j+k=n. For n=2m or 2m+1 there's m such words. Summing all together gives us the answer 1009^2 - 1

  • Adrien Mau
    Adrien Mau 8 months ago

    Ok soo
    You cannot start going down and finish going up or else at some point you crossed your '-1' line.
    So every Dyck Path starts with U and finishes with D. So avoiding UDUDUD si the same as avoiding DUDU. The n and n+1th terms are DU so basically we have to avoid having any other 'DU' before and after the n and n+1th terms

    So as soon as we start having 'D' before the nth terms all following terms should be D. But it's only possible if we have enough 'U' terms beforehand (or else we cross your '-1' line) . The same goes after the n+1th term.

    Let us consider a Dyck path of length 2n.
    From 2nd to n-1 term we have ... n-2 terms to place. The first half of them HAVE to be Us so that we always stay positive (you should too ;) ), the remaining term can be any number of Us followed by the remaining of Ds. I have to calculate the number of possibilities now.

    In this interval you have u Us and d Ds where u+d = n-2 and you have the first term U + remaining u Us that must overcome the number of D + the D in the nth position so the minimum number u of Us (in 2-n-1 term position) is the one where u >= d, and as u+d = n-2 this minimum number is so that umin >= n/2 - 1. If n is odd umin = n/2 - 0.5, if n is even umin = n/2 - 1.

    The right side will have the necessary number of Us left to have 2n Us in total, followed by the remaining Ds. (going with a D first will make a DU appear, remember). This side entirely determined once the left side has been chosen !

    So for an even n we have n-2 - umin possibilities => n/2 - 1.5 possibilities. For an odd n: n/2 - 1.
    The sum of an for n from 3 to 2018 is the sum of (a_2k + a_2k-1) for k from 2 to 1009.
    a2k = k - 1 and a(2k-1) = k-1
    So this sum is 2*sum(k-1)for k from 2 to 1009 = 2sum(k) from 1 to 1008
    = 1008*1009*2/2
    Aaaand I find 1017072
    Which must be wrong as everyone else has 1008 added to that. May have forgotten this while changing my variables... ^^ Still interesting exercice

  • Nicola C
    Nicola C 8 months ago

    The answer is 080.
    Let a "change" be the first time a U appears after some D's and vice versa.
    For example in UUUUDD there is a change at the first D.
    Let's investigate the structure of a good Dyck path: it has to start with a U, obviously and it has to end with a D, otherwise there would be n D's and n-1 U's before the last letter and that is a contradiction.
    Furthermore there are a D and a U in the middle, so a good path looks like this:
    U _ _ ...DU_ _ ...D(there is the same number of empty spaces on the left and on the right)
    There can be just 4 changes or less in the sequence: at least one before the central U (but only an odd number), one at the central U and at least one after that (but only an odd number.
    Since there can only be up to 4 changes, there will be just one before and after the central U and at that U.
    Let's investigate where the first change can be: since there must be more U's than D's before the central U, it can be in every spot after the center of the first section: for example if the first section is
    U _ _ _ DU
    the first change can be on the central D or just before.
    Then you have to notice that after the first change has been positioned, the last one has only one spot where it can be.
    So, in general, aₙ=floor(n/2) and the final sum is equal to 1+2+2+3+3+...+1008+1008+1009
    or 1010*1008
    which is congruent to 10*8=80 mod 1000 and we are done.

  • Rishav Gupta
    Rishav Gupta 8 months ago +1

    There will be a DU in middle and The sereis will start with U and end with D
    Now for n=3 we get no. of good dyck paths =1 for n=4,n=5 we get no of dyck paths =2 ,for n= 6&7 we get paths=3 and similarly sereis continues and thus required sum =
    1009+1+{2((1008)(1009)/2-1)}=1018080
    Thus answer is 080

  • Bigg Barbarian
    Bigg Barbarian 8 months ago +1

    080, since the total sum is 1018080.
    Since the Dyck path needs to avoid UDUDUD there can be at most 2 strings of positive length containingonly U's. Since a dyck path must contain at any time more or equal U's than D's the first of those strings needs to be at least of length ceil(n/2). since also the starting position of those two strings are fixed at position 1 and n+1, a_n = n-1-ceil(n/2)+1 = floor(n/2) for any n >= 3.
    Now it is easy to calculate sum (a_n from 3 to 2018) as 1018080, whose last three digits are 080.

  • Caio Tomazella
    Caio Tomazella 8 months ago

    I'm not adult enough for this problem

  • Alpe
    Alpe 8 months ago +2

    the answer is DUDUDUDUDUDUDUDU

  • Kevin Tong
    Kevin Tong 8 months ago

    The answer is 80
    Notice that the Dyke Path must start with U and end with D due to the increase/decrease condition. Furthermore, since the midpoint must be D, U, we can begin with a string of x Us, then a string of (n-x) D's to meet the 2nd condition. We must have x>n-x, so x is at least the ceiling of n/2, but cannot exceed n-1. Thus, there are n-ceil(n/2) dyke paths of length 2n.
    Summing gives 2016(2021)/2-(1008)(1011)=168-88=80 mod 1000

  • enisheadpay
    enisheadpay 8 months ago +1

    Analyzing the case for n=3 shows only one possible case. For n>3, there are multiple possible cases: Either beginning with (n-1) U's then having DU in the center (to fulfill requirement 2), then the remaining are D's. OR the first (n-2) are U's, then you have DDU (to fulfill 2), but by this time we have already UDU of requirement 1, and we must avoid DUD. We still have 1 U left to place, but it needs to either go in the beginning or the end to avoid DUD. If it goes in the end, that would mean we have gone below zero. we could also start with (n-3) U's, giving us DDDU, and two U's left to place. We can't have any U's at the end and we cant have DUD, so our only choice is to put them both at the beginning. If we have (n-k) U's at the start, we will end up with k D's then a U, then our only option is to put the remaining U's before the remaining D's. We can only do this procedure if k

  • ashwani kumar
    ashwani kumar 8 months ago

    Answer is 080

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

    The answer is 080
    Let Dyck be a good path of length 2n (n>=3), then Dyck must start with U and end with D, and the middles are "DU", so Dyck must contains at least 4 strings of Us and Ds. If Dyck contains 6 strings of Us and Ds then Dyck contains UDUDUD, so Dyck is not a good path. And Dyck start with U and end with D then Dyck can only have an even number of strings. Therefore, Dyck contains exactly 4 strings of Us and Ds. In other words, Dyck has the form of: x letters U + y letters D + z letters U + t letters D, where x,y,z,t are positives integers and x+z = y+t = n. Moreover, the middles of Dyck are "DU" then x+y=z+t=n.
    Therefore Dyck has the form of: x letters U + y letters D + y letters U + x letters D, and x>=y>=1, x+y=n
    Then it can be easy to find that for n=2k, then y can be from 1 to k, and we have a(2k)=k, and for n=2k+1, then y can be from 1 to k, we have a(2k+1)=k
    Therefore the sum of a(k) with k = 3...2018 = 1+2*2+2*3+2*4+....+2*1008 + 1009 = 2* (1+2+3+...+1009) - 1 - 1009 = 1009*1010-1010 = 1008*1010, which is equal to 8*10=80 modulo 1000. Hence, the last 3 digits of the sum is 080.
    P/S : I am the first to write the answer is 80, but I did not paste the full solution from my docs file, then Vishaal Ram
    gave the full solution with the right anwer lol, I guess he won this time =))

  • Yahweh
    Yahweh 8 months ago +3

    The answer is 080.
    The series must begin with U and end with D in order to begin and end at "zero" without going negative.
    The series can be thought of a series of alternating ascending and descending parts. Since the first component is U, the nth is D, the (n+1)th is U and the (2n)th is D, there are at least 2 ascending and descending components. If there were 3 ascending components the series would not avoid UDUDUD, so we know there are exactly two ascending and descending components: the series is of the form (U..U)(D..D)(U..U)(D..D).
    Let the first string of U have length X. We know then that the first string of D has length (n-X), since the midpoint of the series is a turning point. Since the number of U's and D's must be equal, the second string of U must have length (n-X) and the second string of D has length X.
    To prevent the series going negative, X must be at least ceiling(n/2). Also, X can be at most (n-1), to ensure the nth term is D. This gives (n-ceiling(n/2)) possibilities for each n, and summing these terms from n = 3 to 2018 gives 1018080.

  • el tapa
    el tapa 8 months ago +2

    I dont know

  • Minh Cong Nguyen
    Minh Cong Nguyen 8 months ago

    The answer is 80

  • Vishaal Ram
    Vishaal Ram 8 months ago +1

    Consider the consecutive blocks of Us and Ds in the Dyck path. For the path to not contain UDUDUD, it must have less than 6 blocks since otherwise we can simply choose one letter from each block. Note that the Dyck path contains an even number of blocks since it must start with U and end with D and the total number of blocks is at least 4 since it contains DU in the middle. Therefore, the path has exactly 4 blocks so the path is uniquely determined by the number of Us in the first block and the number of Ds in the second block, denoted as A and B respectively. Note that, A+B=n, A,B>=1, and B

    • Shenghui Yang
      Shenghui Yang 8 months ago +1

      "... at least 4 since it contains *DU* in the middle" Very clear solution!

  • Aswini Banerjee
    Aswini Banerjee 8 months ago

    The formula for a_n=(2n)!/{(n+1)!(n!)} SO, summing this from 3 to 2018 the last 3 digits will be 265

  • LetsSolveMathProblems
    LetsSolveMathProblems  8 months ago +8

    * On the final slide of the problem statement, perhaps I should have written "Let a Dyck path of length 2n be good..." instead of "Let a Dyck path be good..." to clarify the meaning of n in the second condition (although n appears in the first slide, a clarification that its meaning does not change through the slides was probably needed).

  • LetsSolveMathProblems
    LetsSolveMathProblems  8 months ago +16

    * Due to a busy personal schedule, the solution to the last week's challenge will be posted tomorrow or Friday. You have my sincerest apology. This school year has been the busiest year of my life in terms of academic work and extracurricular activities (and I firmly believed the last year could never be beaten), and it pains me that I have so little time to pursue my passion for education in USclip. There are many videos I have planned (other than regular Weekly Math Challenge videos), and I hope to craft those ideas into concrete videos as soon as my schedule clears up. Again, I apologize for the lack of content lately. Thank you so much for using your spare time to watch my videos! It means a world to me. =)

  • Zamir C
    Zamir C 8 months ago +6

    The answer is Jesus

    • NoName
      NoName 8 months ago +1

      Jesus is always the answer