Difference between revisions of "2005 AIME I Problems/Problem 13"
m (→See also: box) |
|||
| Line 16: | Line 16: | ||
== See also == | == See also == | ||
| − | + | {{AIME box|year=2005|n=I|num-b=12|num-a=14}} | |
| − | |||
| − | |||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] | ||
Revision as of 15:36, 4 March 2007
Problem
A particle moves in the Cartesian Plane according to the following rules:
- From any lattice point
the particle may only move to 
or 
- There are no right angle turns in the particle's path.
the particle may only move to 
or 
How many different paths can the particle take from 
to 
?
Solution
This question appears to be lacking in "elegant" solutions.
One method is to use casework: compute the number of paths with each possible number of diagonal moves.
Another possibility is to use block-walking and recursion: for each vertex, the number of ways to reach it is the number of ways to reach the vertex to its left not coming from down plus the number of ways to reach the vertex below it not coming from the left plus the number of ways to reach the vertex diagonally down and to the left from any direction. As a result, we find 28 ways to reach (5, 5) coming from below, 28 ways to reach it coming from the left and 27 ways to reach it coming diagonally for a total of 
possible paths.
See also
| 2005 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 12 |
Followed by Problem 14 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
