How it Works › Forums › Advanced Problems (AMC 8 Problems 20-25 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.
January 24, 2017 at 9:14 pm #474AyushGuest
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!January 25, 2017 at 9:09 pm #475Yash AgarwalGuest
1. 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:
To 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:
To 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.January 25, 2017 at 9:20 pm #476Yash AgarwalGuest
2. 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:
I 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 AgarwalJanuary 30, 2017 at 6:10 pm #493Varsha KGuest
1. 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 KJanuary 31, 2017 at 8:39 pm #495AyushGuest
Great 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.February 5, 2017 at 10:55 am #496Sandeep KarjalaGuest
1. 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:
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
Leaves us with 5 possible paths.February 7, 2017 at 10:57 pm #497Ayush AgarwalGuest
Great job Sandeep! You have been awarded 10 points for your excellent work.