# Challenge 73: Schröder Path Pattern Avoidance

Share
Embed
• Published on Dec 27, 2018
• Congratulations to attyfarbuckle, Luis Perez, Eric Schneider, Farzad Saeidi, Devansh Sehta, and Henry M. for successfully solving the last week's math challenge question! attyfarbuckle was the first person to solve the question.
Your support is truly a huge encouragement.
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:

• Simon 7 months ago

My calculations show 162.
A possible sequence is UUUUUUUUUDDDDDDDDD (both 2018 times). If you now take one block, let's call it [UD], the block can be anywhere between place 2015 and the last place in the sequence, without violating the rule to avoid paths UDUDUD and UDUUDD. (Note if you choose [DU] as block, you cannot place it at the end, since then the line dips below 0).
Also, define [HH] as block. We have 3 cases: 0, 1, and 2 [HH] blocks.
Case 1. With 0 blocks, we can cut the sequence of the 4036 entries into UUUU...UUU (2016 entries) and UDD[UD]DDDD (2020 entries). Block [UD] can be anywhere between, before, and after the 2017 D's and the 1 U, so we have 2018+1= 2019 possible positions.
Case 2. With one [HH] block in the sequence, there should be 1 U and 1 D less then in case 1. So with the same reasoning as above we have 2018 possible positions for [UD], and on top of that 4035 possible positions (between, before or after the 4034 U's and D's) for [HH]. Note that [HH] can be placed inside a [UD] block so no possibilities are lost here. This gives 2018*4035 possible combinations.
Case 3. With two [HH] blocks, there remain 2017 possible positions for [UD]. The first [HH] can be placed among the 4032 U's and D's, so 4033 possibilities. The second [HH] has 4034 possibilities. However since the order of 2 consecutive [HH]'s is not relevant, there remain 4033 unique possibilities to place the second [HH].
So in total this comes to 2019+4035*2018+4033*4033*2017 = 32814829162 combinations.

• nidal guesume 7 months ago

pdf of question?

I'm late to this one because I forgot what day it was! My solution is as follows. Step 1 is to misinterpret the symbology, missing the fact that HH = one double step, not two, then waste about an hour trying to work with 0,1,2... 5 horizontal steps instead of the actual constraint of 0,1 or 2. After that it gets easier. (d'oh!) It's not hard to see that we can ignore the HH's when thinking about the other constraints, only needing to count the number of places we can insert them later. The two UD constraints effectively mean that the path can have one hump or two (not unlike a camel). The 'one hump paths' are U^2018 D^2018 (one of those), U^2017 D^2017 with a single HH in any of 4035 places (so 4035 of those), or U^2016 D^2016 with two HH in 4033*4034/2 possibilities. Those add up to 8138597.
The other class of paths are all of the form U^n D D^x (UD) D^y where x and y are 0,1,2... max value. We can work out the max value by observing that n = 2017, 2016 or 2015 for the three possible number of HHs, and that n+1 = x + y + 2. The first case (n=2017) corresponds to 2017 possible places to put the UD. The n=2016 case has 2016 places to put UD, then 4035 places to put HH. Finally, n=2015 has 2015 places for UD, and 4033*4034/2 places for two HH. They add up to a large number ending in 992.
So the last digits are (992 + 597)mod 1000 = 589

• Kwekinator117 7 months ago

First consider when there are no HHs.
The sequence must start with U otherwise we dip below the axis.
k must be at most 2018 because if we have more than that, we can no longer reach 4036,0.
If k is 2018, then we must have 2018 corresponding Ds. This is a valid sequence.
Let k be 2017. We put a D after this string of Us. After this D, we can have no more than 1 U otherwise the sequence will contain UDUUDD. Therefore, the sequence must have exactly 1 U and the remainder of the sequence will be Ds.
Therefore, the sequence will be of the form : (2017)Us,(1 to 2017)Ds,U,(2017 to 1)Ds. This gives us 2017 additional valid sequences.
We will show that if k

• Rishav Gupta 7 months ago

Sir plz make a video on catlan numbers

• LetsSolveMathProblems  7 months ago

I may be able to make a video on Catalan numbers in the next few months. Is there a particular feature of Catalan numbers you wish me to cover?

• Rishav Gupta 7 months ago +1

Either 0HH,1HH or 2HH
When we have 0HH
We can make
When we make one change then only 1 path
And when two changes by removing one
D and placin it any where only on right part
We get 2017 paths
In total we get 2018 paths with 0HH
When we have one Hh we are adding one
HH anywhere on the path with semilength
2017 and 0Hh
We can do it in 2017×4035 ways
When we have 2Hh we are adding
2Hh anywhere on path with semilength 2016 and 0HH
We can do it by adding any one Hh and other on its right We can do it in
4033+4032 .......+3+2+1 ways
Thus total ways are 2016×4034×4033×0.5
Thus total paths possible are 16407415589
Thus last 3digits are 589

• Nicola C 7 months ago

The sequence must have at least one UD subsequence and at most two, but if it has two, then the second has to be a "single" one, and be after the first big one, if not the sequence would contain UDUUDD
Furthermore, the sequence can contain at most 2 HHs, or it would contain HHHHHH.
Now we have to examine a bunch of cases, that i will denote as (m, n), where m is the number of UDs and n is the number of HHs.
Case 1,0: 1 (UUUU...DDDD...)
Case 1,1: 4035, we have to choose where the HH piece is, then everything is determined.
Case 1,2: C(4034,2), after we choose where the first HH is we have to choose it after the first one and the number of ways to do that is 4033+4032+...+1=C(4034,2).
Case 2,0: 2017, we just have to choose where the single UD is and it can be only in the second half.
Case 2,1: 4035*2016, we have to choose the HH first, then the UD, which can only be in the second half without one spot.
Case 2,2: C(4034,2)*2015, as above we have to choose the HHs and then the UD, which has now another spot not available.
Summing up we get (== is the congruent symbol)
s₂₀₁₈==1+35+17*33+17+35*16+17*33*15==589 (mod 1000) and we are done.

• Smokie Bear 🔴🔵 7 months ago +8

I believe the answer is 589.
The question asks for the last three digits, and there are three letters being used, U D H, so the third digit should be 3*3 which is 9.
This weekly math challenge covers two different years, 2018 and 2019, and the number 3 is used a lot in this challenge so the second digit should be 2^3 which is 8.
This challenge started in 2018 and the second digit was 8, since the ending digits of these two match, we can analyze the digits of the years to determine the answer. when the challenge goes to 2019, the numbers are now divisible by 3 because the digits of 2019 add up to 12, so the first digit is 3 plus 2 because it goes through 2 years. So the first digit is 5.
If anyone is reading this and believe my thinking is completely illogical, look at the letters used to show the paths. it spells it out for you. *DUH* “D U H”

• LetsSolveMathProblems  7 months ago +5

Overall, a flawless explanation! However, your reasoning that the second digit is 8 is unfounded. Although this Weekly Math Challenge does cover two years, its covers 2018 much more than 2019. Thus, to make a valid argument, you should have used weighted arithmetic mean or weighted geometric mean to find the base of the exponent: it does indeed turn out to be 2, but how you got to 2 relies too much on intuition (to the extent of being erroneous). I unfortunately cannot accept your answer.

• Vampianist3 7 months ago +3

This question is more than a mouthful, so the answer is as well......To begin with, answer is 589.
The three things to avoid give three rules:
1. Direction cannot be changed more than 2 times (avoid UDUDUD);
2. If you want to change direction 2 times, the second time must be UD (avoid UDUUDD);
3. No more than 2 flat moves (avoid HHHHHH),
which means either 1 change or 2 changes, with 2 changes having the second change 'UD'.
Now, if 1 change only (CASE I), we have the following:
0 HH: 1 case (U...UD...D with 2018 U's and D's)
1 HH: 4035 cases (U...UD...D with 2017 U's and D's and insert HH in between)
2 HH: 0.5 * 4034 * 4033 cases (U...UD...D with 2016 U's and D's, insert the first HH in between, insert the second HH anywhere to the right of the first HH)
if 2 changes (CASE II), we have the following:
0 HH: 2017 cases (U...UD...D with 2017 U's and D's and insert the block 'UD' anywhere to the right of the first D)
1 HH: 2016 * 4035 cases (U...UD...D with 2016 U's and D's, insert 'UD' according to CASE II, 0 HH and insert the HH according to CASE I, 1 HH)
2 HH: 0.5 * 2016 * 4034 * 4033 cases (U...UD...D with 2015 U's and D's, insert 'UD' according to CASE II, 0 HH and insert the two HH's according to CASE I, 2 HH)
Adding up and taking the last 3 digits give the result

• Zain Majumder 7 months ago +1

Define a peak as a switch from U to D in a path (ignoring HH moves). Then, there must be at least one peak and at most two peaks. If there are two peaks, then the second peak must be preceded by exactly one U (because the sequence must avoid UDUUDD). This limits it to two types of sequences, sequences with one peak and sequences with two peaks.
If there are no HH moves, then there is only one Schroder path of semilength n with one peak, and n-1 Schroder paths of semilength n with two peaks. If there is one HH move, then the number of paths can be calculated by finding the number of Schroder paths with semilength n-1 and multiplying by the number of ways to insert an HH move (which is 2n-1). A similar process can be done for two HH moves.
Then there are three cases:
Zero HH - 2018
One HH - 2017 * 4035
Two HH - 2016 * 4033 * 2017
The last three digits of 18 + (17*35) + (16*33*17) are 589.

• Zain Majumder 7 months ago

I thought I was first because I can't see the actual first persons solution due to USclip glitching. Now I'm disappointed :(

• Zain Majumder 7 months ago

I hope this is right lol

• Yahweh 7 months ago +1

the last three digits are 589

Ignoring the HH's for now, the sequence will have the form:
(a U's)(b D's)(c U's)(d D's)
where a

• Sudheer Thunga 7 months ago

Me first