Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 AIME I Problems/Problem 13"

m
Line 8: Line 8:
  
 
== Solution ==
 
== Solution ==
−
{{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 <math>083</math> possible paths.
 +
 
 +
 
 
== See also ==
 
== See also ==
 
* [[2005 AIME I Problems/Problem 12 | Previous problem]]
 
* [[2005 AIME I Problems/Problem 12 | Previous problem]]

Revision as of 21:04, 17 January 2007

Problem

A particle moves in the Cartesian Plane according to the following rules:

  1. From any lattice point $(a,b),$ the particle may only move to $(a+1,b), (a,b+1),$ or $(a+1,b+1).$
  2. There are no right angle turns in the particle's path.

How many different paths can the particle take from $(0,0)$ to $(5,5)$?

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 $083$ possible paths.


See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_AIME_I_Problems/Problem_13&oldid=12229"