Browse · MathNet
PrintMongolian Mathematical Olympiad
Mongolia counting and probability
Problem
Find the number of words using letters and letters with the following properties: i) Among the first letters of the word, number of 's is not less than number of 's for any satisfying the condition ; ii) Among the last letters of the word, number of 's is not less than number of 's for any satisfying the condition .
Solution
In a rectangular grid, let's call right move the route from point to point and up move the route to point from to point . Furthermore when we will count number of routes always will mean every route consists of only right and up moves. Now consider correspondence between words using letters a, b and shortest routes in a grid. Let the up move represents letter and the right move represents letter . Note that desired number equals to the number of shortest routes from to that not pass line segment , , where , , .
We will use the following lemma. Lemma: Let be natural numbers. The number of shortest routes from to that not pass line segment equals to , where . Proof: The total number of shortest routes from to is . Now we find the number of shortest routes that pass line segment and subtract it from . Let consider a route that pass and first up moves of the route that above the line segment . It is obvious that there were right moves and up moves before first passing. Now we change every right move by up move and every up move by right move after first passing. Thus we get new route from to .
Note that every route from to that pass -r corresponds to a route from to . It is easy to see the correspondence is bijective. Since the number of routes from to equals to , we have desired number equals to . The lemma is proved.
Let's now solve our problem. If we denote number of routes from to that pass , number of routes from to that pass , number of routes from to pass both , , total number of routes from to then our task will be finding value of . By the lemma proved above we get . Since a route from to is the same as a route from to , we conclude that . Every route that pass both , corresponds to a route from to and this correspondence is bijective. Number of routes is Since total number of routes from to equals to , desired number is .
We will use the following lemma. Lemma: Let be natural numbers. The number of shortest routes from to that not pass line segment equals to , where . Proof: The total number of shortest routes from to is . Now we find the number of shortest routes that pass line segment and subtract it from . Let consider a route that pass and first up moves of the route that above the line segment . It is obvious that there were right moves and up moves before first passing. Now we change every right move by up move and every up move by right move after first passing. Thus we get new route from to .
Note that every route from to that pass -r corresponds to a route from to . It is easy to see the correspondence is bijective. Since the number of routes from to equals to , we have desired number equals to . The lemma is proved.
Let's now solve our problem. If we denote number of routes from to that pass , number of routes from to that pass , number of routes from to pass both , , total number of routes from to then our task will be finding value of . By the lemma proved above we get . Since a route from to is the same as a route from to , we conclude that . Every route that pass both , corresponds to a route from to and this correspondence is bijective. Number of routes is Since total number of routes from to equals to , desired number is .
Final answer
binom(20142015,2014) - 2binom(20142015,2013) + binom(20142015,2012)
Techniques
Enumeration with symmetryInclusion-exclusionCounting two waysRecursion, bijection