How it Works › Forums › Advanced Problems (AMC 8 Problems 2025 and beyond) › Advanced Combinatorics on the Grid Problems!
 This topic has 6 replies, 1 voice, and was last updated 3 years ago by Ayush Agarwal.

AuthorPosts

AyushGuest
Here are the advanced problems for the next week! These are MUCH more difficult than AMC 8 Problems but you can make progress on them if you attended the lecture. Each of these problems is worth 10 points to your leaderboard score! If you don’t understand one of the questions, feel free to post in the questions forum here.
1. How many paths are there from (0, 0) to (2, 2) given that at each point you can only
move 1 unit right or up (Just like problem 1) and you must stay below the line y = x?
What about (3, 3). These numbers are called the Catalan Numbers and are given by the
closed form C_n = (2n choose n)/(n+1)2. How many sequences of letters A, B are there such that at any point in the sequence,
the number of Bs is less than the number of A’s. The length of the sequence is 4. Can
you generalize to n. (HINT: How does this relate to problem 1?)3. If a mouse is stuck at a corner of a cube and there is a block of cheese on the opposite
vertex. How many paths are there such that mouse eats the block given that the mouse
does not revisit any vertex he has already visited?Remember that you can post your solutions below to these problems and I will keep a running leaderboard for the top 10 students who participate the most! I especially appreciate the same problem being solved in different ways!
Yash AgarwalGuest1. There are two paths from (0,0) to (2,2) if we have to stay behind the line y = x. Here are the two possible combinations:
RRUU
RURUTo prove this further, we can use the Catalan Number formula. (2n choose n)/n+1. Here, n=2. 4 choose 2 = 6. 6/3 = 2.
There are five paths from (0,0) to (3,3). Here are the five possible combinations:
RRRUUU
RURURU
RRUURU
RRURUU
RURRUUTo prove this further, we can use the Catalan Number formula. (2n choose n)/n+1. Here, n=3. 6 choose 3 = 20. 20/4 = 5.
As you can see, you cannot just do n*2 choose n, since all points have to be under the line y = x. So, the answers are 2 and 5 .
This response was written by Yash Agarwal.
Yash AgarwalGuest2. There are 6 sequences possible for the number of A’s always being greater than or equal to the number of B’s. One thing we do know for certain is that we have to start with an A. So, we can consider this as a 3 letter sequence with the number of A’s always being at least 1 less than the number of B’s. The 6 sequences are:
ABB
BAB
BAA
AAA
ABA
AABI do not think we can generalize to n since there is no pattern or sequence. If the length is 2, the number of sequences is 2. If 3, then 3. If 4, then 6. If 5, then 10. …
This response was written by Yash Agarwal
Varsha KGuest1. We first make one of those graphs you taught us to make in our last meeting.
In this case, n=2.(2n choose n)/n+1= (4 choose 2)/2+1 = 6/3 = 2 paths.
1a. What about (3,3)?
In this case, n=3.
(2n choose n)/n+1= (6 choose 3)/3+1 = 20/4= 5 paths.Solved by Varsha K
AyushGuestGreat work Yash and Varsha! You both have earned 10 points to your total!
One comment for Varsha though, try to find a way to count them without using the formula to verify that the formula is correct. Also, Yash rethink your solution to the letters question because the number of B’s must be less than the number of A’s AT ALL POINTS in the sequence.Sandeep KarjalaGuest1. There are 2 paths from point (0,0) to (2,2), under the line of y=x. As we have said last time in math circle we need 2R (Rights) and 2U (Ups) for us to get to the point (2,2).
The possible paths were 6.(Including lines on y=x)The paths are:
1.RRUU
2.RURU
3.URUR
4.URRU
5.RUUR
6.UURR
In this problem it doesn’t let us go one the line y=x. So that means our first move cannot be U or RUU. That eliminates #s 3,4,5,6. That leaves us with 2 paths.
You can also do it with the Catalan number formula:(2n choose n)/n+1.In this case n=2.
(4 choose 2)/3.4 choose 2 is 6. And, 6/3=2. Leaves us again with 2 possible paths.
For the possible paths from (0,0) to (3,3) below the line of y=x.
We can use the Catalan number formula to be more efficient.
(2n choose n)/n+1
In this case n=3.
(6 choose 3)= 20
20/(3+1)
20/4
=5Leaves us with 5 possible paths.
Ayush AgarwalGuestGreat job Sandeep! You have been awarded 10 points for your excellent work.

AuthorPosts