# Challenge 84: Pairs of Lattice Paths with Restrictions

Share
Embed
• Published on Mar 14, 2019
• Congratulations to Gabriel N., Benjamin Wang, Nitro Zox, Rishav Gupta, Varun Shah, adandap, Alex Edwards, Nicholas Parris, fmakofmako, and aby p for successfully solving the last week's math challenge question! Gabriel N. was the first person to solve the question.
Welcome, everyone! LetsSolveMathProblems presents one weekly math challenge problem every Wednesday (continental U.S. time). To participate, please comment your proposed answer and explanation below (or discuss potential solutions with other viewers), keeping in mind that your comment should be left unedited to win the recognition prize. Up to the first ten people with correct solutions are recognized in the next challenge video. The solution to a challenge problem is posted as a separate video the following Wednesday.
For more Weekly Math Challenges:

## Comments • 21

• The answer is 252.
We estimate S_n= 4*S_{n-1} - 2*I_{n}, since there are 4 new directions yielded by an unclosed pair of paths.
If a pair of paths is closed (i.e. both of them intersect after n path units), two directions are lost, therefore we subtract 2*I where I_{n} is the number of those closed pairs.
Experiments for small n leads to the assumption that I_{n} may be equivalent to C_{n}, the n-th Catalan number. I have no formal proof for this, but it may have something to do with *Dyck paths* . A Dyck path of length 2n is a path which starts at 0 and ends at 2n. It can never reach under the x-Axis and every step has to consist of one step to the right and one up or one down, so it consists of 2n steps.
There are exactly C_{n} ways of forming a Dyck path for a given n. Since closed pairs are of the length 2n in our case (n steps for each A,B), these two concepts might be related.
Nevertheless, assume I_{n}=C_{n}.
Then we have S_n= 4*S_{n-1} - 2*C_{n}.
By the proof in the Weekly Math Challenge Solution Video, we have the equality
S_n= 2nCn, where nCk is the binomial coefficient of n over k.
Therefore, S_5= 10C5 = 252

• Ganzrationaler Testudinadler 6 months ago

I totally mixed up the indices here. It should have said S_{n+1}=4*S_{n} - 2* I_{n}.

• attyfarbuckle 6 months ago

You can also get 252 by counting "mountain ranges". There is a bijection between pairs of paths & the set of all strings made up of upstrokes /// and downstrokes \\\ of length 10, with the downstrokes never exceeding the upstrokes, counting from left to right.
The expression for the number of mountain ranges comes from the reflection principle: basically any route from (0, 0) to (10, 0) that reaches y = -1 can be paired up with a route from (0, -2) to (10, 0) by reflecting the section of that route up to (x, -1) in the line y = -1. (Use the smallest value of x with (x, -1) on the route to get a 1-1 correspondence).
# arrangements of "/////\\\\\" = 10_C_5 - 10_C_4
# arrangements of "//////\\\\" = 10_C_4 - 10_C_3
# arrangements of "///////\\\" = 10_C_3 - 10_C_2
# arrangements of "////////\\" = 10_C_2 - 10_C_1
# arrangements of "/////////\" = 10_C_1 - 10_C_0
# arrangements of "//////////" = 10_C_0 = 1
The total sum telescopes to 10_C_5 = 252.
The mapping from pairs of paths to mountain ranges is done by interweaving terms from path B & path A.
B1, A1, B2, A2, B3, ...
Up steps in A & Down steps in B count as "/". Other steps count as "\".

• attyfarbuckle 6 months ago

I googled the phrase "counting mountain ranges" and the first few articles were about Catalan numbers. Maybe it's not so standard though. In the strings "/" is shorthand for a vector (1, 1) & "\" is for (1, -1).
A sequence of these symbols represents a random walk on the Cartesian plane from O to another point on the plane (a, b) with a>0, b>=0.
If the running total of "/" is ever less than the running total of "\" it corresponds to going below the x-axis and is invalid.
Dyck paths always finish on the x-axis, so are a special case of mountain ranges.
The critical bit is that each valid string corresponds to exactly one pair of paths & all path pairs have a corresponding string.
(0, -2) comes from the technique for deriving the formula for a number of random walks that don't cross a certain boundary.

• socerdemon8 6 months ago

I couldn't follow any of this. Could you define more clearly what exactly a mountain range is? What's not a mountain range? And what is (0,-2) ? everything is either up or right, not down.

• Nicola C 6 months ago +1

The answer is 252.
With some experimenting we notice that there are different types of configurations that differ for the distance between the final tips of A and B.
Let the distance of a configuration be the difference of the x-coordinates (or y-).
For example your illustrations of the cases of S₂ have, for example, distances 2, 0, 1, 0, 1, 1 from left to right.
Let's now call kₙ (where k is a number) the number of configurations that have distance (as defined above) k and length n.
We notice that a configuration of length n and distance 0 can be obtained in one way from every configuration of length n-1 and distance 1 and in one way from every configuration of length n-1 and distance 0.
In other words
0ₙ=0ₙ₋₁+1ₙ₋₁
Similarly, for 1n, kₙ=0, obviously.
So we can proceed by recurtion from the values of 0₁=1 and 1₁=1 and we get, for n=5,
0₅=42
1₅=90
2₅=75
3₅=35
4₅=9
5₅=1
Finally S₅=1₅+2₅+3₅+4₅+5₅=252 and we are done.
P.S. I'm sorry for inventing this strange notation with a lot of numbers, but i didn't know a better way to express it.

• Mushishi2872 6 months ago

Well this is pretty interesting, I used the same method to solve the problem. Even the notations are the same... hehe.
However, after reaching the formula:
0ₙ = 0ₙ₋₁ + 1ₙ₋₁
and kₙ = (k - 1)ₙ₋₁ + 2 kₙ₋₁ + (k + 1)ₙ₋₁ , 1 < k ≤ n
I tried to find a general solution for Sₙ = 0ₙ + 1ₙ + 2ₙ + ... + (n - 1)ₙ + nₙ.
By combining the formulas above we get:
Sₙ = (0ₙ₋₁ + 1ₙ₋₁) +
(0ₙ₋₁ + 2*1ₙ₋₁ + 2ₙ₋₁) +
(1ₙ₋₁ + 2*2ₙ₋₁ + 3ₙ₋₁) +
... +
(n - 2)ₙ₋₁ + 2*(n - 1)ₙ₋₁ + nₙ₋₁
(n - 1)ₙ₋₁ + 2*nₙ₋₁ + (n+1)ₙ₋₁
Sₙ = 2*0ₙ₋₁ + 4*1ₙ₋₁ + 4*2ₙ₋₁ + 4*3ₙ₋₁ + ... + 4*(n - 1)ₙ₋₁ + 3*nₙ₋₁ + (n + 1)ₙ₋₁
kₙ = 0 for k > n , therefore nₙ₋₁ = (n + 1)ₙ₋₁ = 0 so,
Sₙ = 2*0ₙ₋₁ + 4*1ₙ₋₁ + 4*2ₙ₋₁ + 4*3ₙ₋₁ + ... + 4*(n - 1)ₙ₋₁
= 4 (0ₙ₋₁ + 1ₙ₋₁ + 2ₙ₋₁ + ... + (n - 1)ₙ₋₁) - 2*0ₙ₋₁
= 4 Sₙ₋₁ - 2*0ₙ₋₁
We also observe that:
0ₙ₋₁ = Sₙ₋₁/n , my proof is a bit long so i won't write it here
Therefore: Sₙ = 4 Sₙ₋₁ - 2 Sₙ₋₁/n
= 2((2n - 1)/n) Sₙ₋₁
= 2²(2n - 1)(2n - 3)/(n(n - 1)) Sₙ₋₂ , (recursively)
= ...
= 2ᵏ(2n - 1)(2n - 3)...(2(n - k) + 1)/(n(n - 1)...(n - k + 1)) Sₙ₋ₖ , 1 ≤ k
For k = n
Sₙ = 2ⁿ(2n - 1)(2n - 3)...*5*3*1/(n(n - 1)...*3*2*1) S₀
Finally, by using:
i) 1*2*3*...*(n - 1)n = n!
ii) 1*3*5*...*(2n - 3)(2n - 1)=(2n)!/n! * 2⁻ⁿ
iii) S₀ = 0₀ = 1
We get: Sₙ = (2n)!/(n!)² , for n=5 , S₅ = 10!/(5!)² = 252
Anyways, when I see other people's solutions I feel like I always do it the hard way XD.

• Ganzrationaler Testudinadler 6 months ago

That's pretty good. The best thing is that you haven't used Catalan numbers.

• Ruben van Erkelens 6 months ago

When only looking at restriction one, the total number of paths is 2^n*2^n = 2^2n as both A and B can take 2 steps per increase of n. Taking into consideration restriction 2 and 3, we can see that 2 directions are restricted whenever A and B are at the same lattice point. A and B are at the same point if at n-1 they were at the same point and they both go right (which is an equal amount of times as at n-1) , or if B is one position lower as A, and A goes right and B goes up. Counting the possibilities we find that for n=0, 1 combination exists where A and B are at the same position, for n=1 1 combination, for n=2 2, n=3 5 and n=4 14. For each of these two directions are restricted, for which each follow up path has to be subtracted as follows: S_5 = 2^10 - 2*2^8*1 - 2*2^6*1 - 2*2^4*2 - 2*2^2*5 - 2*2^0*14 = 252

• Rishav Gupta 6 months ago

The answer is 252
For every path n-1 length we can get 4 paths of n length if the end points of A and B dont concide and 2 paths if A and B concides
If we think of no of conciding paths of length n-1
For A and B individual no of right and up steps will be equal
Thus we can prove that no of ways they will concide as C(n-1)
Thus total no of ways of n lengthed paths
Sn=4Sn-1-2Cn-1
From last weeks problem Sn=(2n choose n)
Thus S5=10C5=252

• Evyatar Baranga 6 months ago +1

252
its like last week's question!!!

looking at the line connecting the end of A and B, you get a diagonal (looks like: y = -x),
thet diagonal can do 4 things:
X) move right(A,B move right)
Y) move up (A,B move up) , only if length is bigger then 0
Z) expend(A up, B right)
W) shrink (A right, B up), only if length is bigger then 0
the word built from those 4 letters will describe a path of A and B , so the number of possible words is the number of possibilities.
if you were to build the a words with length n by adding a letter to the end of each word of length n-1:
if the diagonal length is 0, you can only get 2 words(X,Z), and otherwise you get 4 words.
by looking at a few iterations i can see that the number of words of length 0 is the catalan number = 1/(n+1)* (2n over n). (does not have a proof for that, sory, i tried a lot).
and if so, then the number of words of length n , Sn, is 4* S(n-1) (for each word of length n-1 there are 4 possibilities) minus 2*#words of length 0 in words of length n-1 (because they only have 2 possibilities instead of 4)
=> Sn = 4*S(n-1) - 2*C(n-1)
=> Sn = (2n over n) , by last week's problem.
=> S5 = (10 over 5) = 252
QED

• Serengeti Ghasa 6 months ago

Dear Sir,
My way of observation and explanation
If in case of Sₙ the all n unit of B are rightwards then there would be
2ⁿ way for A
from right side of B if any unit remain upwards then it will block 2 unit of so that wd be in decreasing 2 Nums upto left position
so Sₙ = 2ⁿ+(2ⁿ-2)+(2ⁿ-4)+........+6+4+2 =2(1+2+3..........2ⁿ⁻¹)=2ⁿ⁻¹×(2ⁿ⁻¹+1)
SO S₅=16×17=272
with love and respect
Prabhat Kumar Sahu

• Kunal Gaurav 6 months ago

S_5=252 because S_n = C(2n,n) where C(2n,n)= choosing n objects out of 2n objects . To analyse S_n let's consider S_(n-1) . To obtain S_n we have one path remaining(in S_(n-1) ) each for A and B . To make S_(n-1) of n paths there are 4 ways (2 ways for each A and B i.e forward or rightward for each A and B) hence we get 4 S_(n-1) , but among these there are unfavourable cases which we need to subtract.
1) Unfavourable case 1: After getting S_(n-1) at their common point of meeting when A moved rightward and B moved upward . The number of ways in which they can meet at a common point is C_(n-1) {where C_n is a Catalan number) we can prove that it's C_(n-1) by saying that each forward and upward path of A will be accompanied by B's forward and upward path such that distance between forward path of A and distance between forward path of B will be greater than or equal to 0 , same for their upward path, in a way forming pairs of forward-forward and upward-upward which is analogous to the number of ways of closing n-1 left brackets and n-1 right brackets to form a paranthesis which is C_(n-1)
2) Unfavourable case 2: after getting S_(n-1) at their common point when A and B both moved upward and the number of ways in which they can meet at a common point for S_(n-1) is C_(n-1) which we have already proved in the unfavourable case 1
Hence total number of unfavourable cases is C_(n-1) + C_(n-1) i.e 2C_(n-1)
Hence S_n = 4S_(n-1) - 2C_(n-1) , after solving this recursion using generating function we get S_n = C(2n,n)

• rain_deer 6 months ago

a path ends together (T) if the last point of A and B intersect otherwise they're apart (A)
a (T) path can be extended by either (A right, B right) or (A up, B right)
a (A) path can be extended by either (A right, B right) or (A up, B right) or (A up B upor (A right, B up)
S_1 = |{T, A}| = 2
S_2 = {{ 2T, 4A }| = 6
...
S_n = |{ 2^(n-1)T, 4^(n-1)A}| = 2^(n-1) + 4^(n-1)
S_5 = 272

• Smokie Bear 🔴🔵 6 months ago +3

The answer is 252.
We are given that S2=6, indicating that something with the digits of “2” and “6” like 260 will be involved in the answer.
We are given S2 and we want to find S5, since S refers to a sum, if we add 2 and 5 we get 7. Since each step is of length 1 unit. Then 7 + 1, or 8, will be involved in the answer.
Since we have only done addition so far, it is logical and correct to assume that the problem would involve subtraction as well. So 260 minus 8, or 252 is the answer.
You might believe that it would make more sense to add the numbers instead of subtract them. *but*, adding the numbers will give us 268, while subtracting gives us 252. Since on Verizon fios tv, 252 is the Nickelodeon channel and is much superior and significant than whatever is on the 268 channel, 252 must be the correct answer.

• Jeremy Weissmann 6 months ago

Smokie Bear ✔️ I can only pray that this proof can be presented and more fully elaborated in its own video, because it truly deserves that!

• Jeremy Weissmann 6 months ago

From the looks of Gabriel's solution, I should have attempted last week's problem!
My solution is as follows. First I note that, by induction, at each step of the path, A and B are on a line with slope -1. When they move in the same direction, they stay the same distance apart; when they move in opposite directions, they either move one multiple of sqrt(2) closer or further apart.
Thus, letting D(k,n) denote the number of n-step paths possible when A and B start k multiples of sqrt(2) apart, we note for instance:
• if k ≥ n, then D(k,n) = 4^n -because any moves are possible
• D(0,n+1) = D(0,n) + D(1,n) -because when k = 0, point B can only move right
• if k ≥ 1, then D(k,n+1) = D(k-1,n) + 2·D(k,n) + D(k+1,n) -corresponding to the possibilities of moving in opposite or the same directions
With these simple recurrence relations, we can fill in a table:
n\k 0 1 2 3
---------------------------
0 1 1 1 1
1 2 4 4 4
2 6 14 16 16
3 20 50 62 64
4 70 182
5 252
So S_5 = D(0,5) = 252.

• Gabriel N. 6 months ago +1

Answer: S_5 = 252
In general, S_n = C(2n,n);
Where C(n,k) is the choose function.
Proof: We will use the Catalan number C_n. Given S_n, each point can give rise to 2 different vectors, leaving 4 combinations. But, it the points are connected at the end, there are only 2 possibilities. Analyzing this further, we get that there are C_n ways to connect the point after n steps using the Catalan recursion. Therefore, S_(n+1)= 4S_n-2C_n.
With S_1 = 2, the recursion is solved by S_n= C(2n,n).
QED

• Evyatar Baranga 6 months ago

wow well done Gabirel

• Jeremy Weissmann 6 months ago

Gabriel N. The induction argument is beautiful. I’ll have to do some research to understand how you find a closed form for the recursion but the argument itself is perfection.

• Philip Yao 6 months ago

Note that this is NOT and elegant solution. consider all possibilities of B. the first move cannot be up as the origin counts as an intersection and A can’t be below B. the other 4 moves leave 16 combinations for B. if you guessed it, yes. Find all combinations of A that works with each combination of B and add all of the combinations up. I’ll write the combinations as r for right, and u for up. I’ll list each of the combinations.
case 1 for B: r u u u u. the only 2 solutions for A are u u u u u and u u u u r so 2
case 2 for B: r u u u r. after 3 u moves, A can move in both directions in the next 2 moves. 2*2=4
case 3 for B: r u u r u. we add all of the solutions for A in case 2 as all of the combinations work. after 2 u moves, you can do 1 r, but not 2. the 4th move has to be a u. the last move is free. 4+2=6
case 4 for B: r u u r r. The first 2 moves are u moves, and for the other 3, you can go both directions. 2^3=8
case 5 for B: r u r u u. after the first u move, you are allowed to do an r move. if you do an r move, you have 2 go up until the last move (which you can go both directions). same if you go up twice, 3 times, and 4 times. 2*4=8
case 6 for B: r u r u r. if you do u r u, you can use both directions for the last 2 moves. 2*2=4. if you go up twice, the last 3 moves are free. 2^3=8 4+8=12
case 7 for B: r u r r u. doing u r r gives 2 combinations, u r u gives 4, and u u gives 8. 2+4+8=14
case 8 for B: r u r r r. going up once gives 4 moves when you go both directions. 2^4=16
case 9 for B: r r u u u. starting with an r move gives 2 solutions, u then r gives 2, u u r gives 2, and 3 u moves gives 4 solutions. 2+2+2+4=10
case 10 for B: r r u u r. doing an r move gives 4 solutions, u then r gives 4 solutions as well, and 2 u moves gives 8. 4+4+8=16
case 11 for B: r r u r u. r u r gives 2 solutions, u r r gives 2, r u u gives 4, u r u gives 4, and u u gives 8. 2+2+4+4+8=20
case 12 for B: r r u r r. u gives 16 solutions, and r u gives 8. 16+8=24
case 13 for B: r r r u u. r r gives 2 solutions, r u r gives 2 solutions, u r r gives 2 solutions, r u u gives 4, u r u gives 4, and u u gives 8. 2+2+2+4+4+8=22
case 14 for B: r r r u r. starting with a u move gives 16 solutions, r then u gives 8, and r r u gives 4. 4+8+16=28
case 15 for B: r r r r u. all of the solutions of case 14 plus another situation for A. r r r u gives 2 solutions. 28+2=30
case 16 for B: r r r r r. this one is easiest. You can go both directions in all 5 moves. 2^5=32
add up all of the solutions for each case, and you have your answer. 2+4+6+8+8+12+14+16+10+16+20+24+22+28+30+32=252
NOTE: this is my first time doing this and I fully understand if this solution doesn’t count. I hope it does though