# Challenge 64: Can You Avoid This Dyck Path?

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.

Whipload Channel11 months ago^{+1}How is UUUDD not valid? It fits the def

LetsSolveMathProblems10 months agoThe 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.

Czeckie11 months agoThe 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 Mau11 months agoOk 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 C11 months agoThe 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 Gupta11 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 Barbarian11 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 Tomazella11 months agoI'm not adult enough for this problem

Alpe11 months ago^{+2}the answer is DUDUDUDUDUDUDUDU

Kevin Tong11 months agoThe 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

enisheadpay11 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

Minh Cong Nguyen11 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 =))

Yahweh11 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 tapa11 months ago^{+2}I dont know

Minh Cong Nguyen11 months agoThe answer is 80

Vishaal Ram11 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 Yang11 months ago^{+1}"... at least 4 since it contains *DU* in the middle" Very clear solution!

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

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

LetsSolveMathProblems11 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 C11 months ago^{+6}The answer is Jesus

NoName11 months ago^{+1}Jesus is always the answer