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 (→‎See also: box)
m (→‎Solution 2)
 
(15 intermediate revisions by 11 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
A particle moves in the Cartesian Plane according to the following rules:
+
A particle moves in the [[Cartesian plane]] according to the following rules:
  
 
# From any lattice point <math> (a,b), </math> the particle may only move to <math> (a+1,b), (a,b+1), </math> or <math>(a+1,b+1). </math>
 
# From any lattice point <math> (a,b), </math> the particle may only move to <math> (a+1,b), (a,b+1), </math> or <math>(a+1,b+1). </math>
Line 6: Line 6:
  
 
How many different paths can the particle take from <math> (0,0) </math> to <math> (5,5) </math>?
 
How many different paths can the particle take from <math> (0,0) </math> to <math> (5,5) </math>?
 +
 +
__TOC__
  
 
== Solution ==
 
== Solution ==
−
This question appears to be lacking in "elegant" solutions.
+
=== Solution 1 ===
 +
The length of the path (the number of times the particle moves) can range from <math>l = 5</math> to <math>9</math>; notice that <math>d = 10-l</math> gives the number of diagonals. Let <math>R</math> represent a move to the right, <math>U</math> represent a move upwards, and <math>D</math> to be a move that is diagonal. [[Casework]] upon the number of diagonal moves:
 +
 
 +
*'''Case ''' <math>d = 1</math>: It is easy to see only <math>2</math> cases.
 +
*'''Case ''' <math>d = 2</math>: There are two diagonals. We need to generate a string with <math>3</math> <math>R</math>'s, <math>3</math> <math>U</math>'s, and <math>2</math> <math>D</math>'s such that no two <math>R</math>'s or <math>U</math>'s are adjacent. The <math>D</math>'s split the string into three sections (<math>-D-D-</math>): by the [[Pigeonhole principle]] all of at least one of the two letters must be all together (i.e., stay in a row).
 +
:If both <math>R</math> and <math>U</math> stay together, then there are <math>3 \cdot 2=6</math> ways.
 +
:If either <math>R</math> or <math>U</math> splits, then there are <math>3</math> places to put the letter that splits, which has <math>2</math> possibilities. The remaining letter must divide into <math>2</math> in one section and <math>1</math> in the next, giving <math>2</math> ways. This totals <math>6 + 3\cdot 2\cdot 2 = 18</math> ways.
 +
*'''Case ''' <math>d = 3</math>: Now <math>2</math> <math>R</math>'s, <math>2</math> <math>U</math>'s, and <math>3</math> <math>D</math>'s, so the string is divided into <math>4</math> partitions (<math>-D-D-D-</math>).
 +
:If the <math>R</math>'s and <math>U</math>'s stay together, then there are <math>4 \cdot 3 = 12</math> places to put them.
 +
:If one of them splits and the other stays together, then there are <math>4 \cdot {3\choose 2}</math> places to put them, and <math>2</math> ways to pick which splits, giving <math>4 \cdot 3 \cdot 2 = 24</math> ways.
 +
:If both groups split, then there are <math>{4\choose 2}=6</math> ways to arrange them. These add up to <math>12 + 24 + 6 = 42</math> ways.
 +
*'''Case ''' <math>d = 4</math>: Now <math>1</math> <math>R</math>, <math>1</math> <math>U</math>, <math>4</math> <math>D</math>'s (<math>-D-D-D-D-</math>). There are <math>5</math> places to put <math>R</math>, <math>4</math> places to put <math>U</math>, giving <math>20</math> ways.
 +
*'''Case ''' <math>d = 5</math>: It is easy to see only <math>1</math> case.
 +
 
 +
Together, these add up to <math>2 + 18 + 42 + 20 + 1 = \boxed{083}</math>.
 +
 
 +
=== Solution 2 ===
 +
Another possibility is to use block-walking and [[recursion]]: for each vertex, the number of ways to reach it is <math>a + b + c</math>, where <math>a</math> is the number of ways to reach the vertex from the left (without having come to ''that'' vertex (the one on the left) from below), <math>b</math> is the number of ways to reach the vertex from the vertex diagonally down and left, and <math>c</math> is the number of ways to reach the vertex from below (without having come to ''that'' vertex (the one below) from the left).
  
−
One method is to use casework: compute the number of paths with each possible number of diagonal moves.
+
Assign to each point <math>(i,j)</math> the triplet <math>(a_{i,j}, b_{i,j}, c_{i,j})</math>. Let <math>s(i,j) = a_{i,j}+ b_{i,j}+ c_{i,j}</math>. Let all lattice points that contain exactly one negative coordinate be assigned to <math>(0,0,0)</math>. This leaves the lattice points of the first quadrant, the positive parts of the <math>x</math> and <math>y</math> axes, and the origin unassigned. As a seed, assign to <math>(0,1,0)</math>. (We will see how this correlates with the problem.) Then define for each lattice point <math>(i,j)</math> its triplet thus:
 +
<cmath>\begin{align*}
 +
a_{i,j} &= s(i-1,j) - c_{i-1,j}\\
 +
b_{i,j} &= s(i-1,j-1) \\
 +
c_{i,j} &= s(i,j-1) - a_{i,j-1}.
 +
\end{align*}</cmath>
 +
It is evident that <math>s(i,j)</math> is the number of ways to reach <math>(i,j)</math> from <math>(0,0)</math>. Therefore we compute vertex by vertex the triplets <math>(a_{i,j}, b_{i,j}, c_{i,j})</math> with <math>0 \leq i, j \leq 5</math>.
 +
<asy>
 +
defaultpen(fontsize(8)+0.8+heavyblue); size(250);
  
−
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.
+
for(int i = 0; i<6; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5), gray+0.25); }
 +
label("$(0,0,0)$", (0,0), N);
 +
for(int i = 1; i<6; ++i) { label("$(0,0,1)$", (0,i), N); label("$(1,0,0)$", (i,0), N); label("$({"+string(i-1)+"},1,0)$", (i,1), N); label("$(0,1,{"+string(i-1)+"})$", (1,i), N);}
 +
real[] val={1,2,4,7};
 +
for(int i = 2; i<6; ++i) { label("$(1,{"+string(i-1)+"}, {"+string(val[i-2])+"})$", (2,i), N); label("$({"+string(val[i-2])+"},{"+string(i-1)+"}, 1)$", (i,2), N);}
  
 +
label("$(3,3,3)$", (3,3), N); label("$(9,9,9)$", (4,4), N); label("$(28,27,28)$", (5,5), N);
 +
label("$(4,5,6)$", (3,4), N); label("$(6,5,4)$", (4,3), N);
 +
label("$(5,8,11)$", (3,5), N); label("$(11,8,5)$", (5,3), N);
 +
label("$(13,15,18)$", (4,5), N); label("$(18,15,13)$", (5,4), N);
 +
</asy>
 +
Finally, after simple but tedious calculations, we find that <math>(a_{5,5}, b_{5,5}, c_{5,5}) = (28,27,28)</math>, so <math>s(i,j)=28+27+28 = \boxed{083}</math>.
  
 
== See also ==
 
== See also ==
Line 19: Line 56:
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 23:21, 28 July 2022

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

Solution 1

The length of the path (the number of times the particle moves) can range from $l = 5$ to $9$; notice that $d = 10-l$ gives the number of diagonals. Let $R$ represent a move to the right, $U$ represent a move upwards, and $D$ to be a move that is diagonal. Casework upon the number of diagonal moves:

  • Case $d = 1$: It is easy to see only $2$ cases.
  • Case $d = 2$: There are two diagonals. We need to generate a string with $3$ $R$'s, $3$ $U$'s, and $2$ $D$'s such that no two $R$'s or $U$'s are adjacent. The $D$'s split the string into three sections ($-D-D-$): by the Pigeonhole principle all of at least one of the two letters must be all together (i.e., stay in a row).
If both $R$ and $U$ stay together, then there are $3 \cdot 2=6$ ways.
If either $R$ or $U$ splits, then there are $3$ places to put the letter that splits, which has $2$ possibilities. The remaining letter must divide into $2$ in one section and $1$ in the next, giving $2$ ways. This totals $6 + 3\cdot 2\cdot 2 = 18$ ways.
  • Case $d = 3$: Now $2$ $R$'s, $2$ $U$'s, and $3$ $D$'s, so the string is divided into $4$ partitions ($-D-D-D-$).
If the $R$'s and $U$'s stay together, then there are $4 \cdot 3 = 12$ places to put them.
If one of them splits and the other stays together, then there are $4 \cdot {3\choose 2}$ places to put them, and $2$ ways to pick which splits, giving $4 \cdot 3 \cdot 2 = 24$ ways.
If both groups split, then there are ${4\choose 2}=6$ ways to arrange them. These add up to $12 + 24 + 6 = 42$ ways.
  • Case $d = 4$: Now $1$ $R$, $1$ $U$, $4$ $D$'s ($-D-D-D-D-$). There are $5$ places to put $R$, $4$ places to put $U$, giving $20$ ways.
  • Case $d = 5$: It is easy to see only $1$ case.

Together, these add up to $2 + 18 + 42 + 20 + 1 = \boxed{083}$.

Solution 2

Another possibility is to use block-walking and recursion: for each vertex, the number of ways to reach it is $a + b + c$, where $a$ is the number of ways to reach the vertex from the left (without having come to that vertex (the one on the left) from below), $b$ is the number of ways to reach the vertex from the vertex diagonally down and left, and $c$ is the number of ways to reach the vertex from below (without having come to that vertex (the one below) from the left).

Assign to each point $(i,j)$ the triplet $(a_{i,j}, b_{i,j}, c_{i,j})$. Let $s(i,j) = a_{i,j}+ b_{i,j}+ c_{i,j}$. Let all lattice points that contain exactly one negative coordinate be assigned to $(0,0,0)$. This leaves the lattice points of the first quadrant, the positive parts of the $x$ and $y$ axes, and the origin unassigned. As a seed, assign to $(0,1,0)$. (We will see how this correlates with the problem.) Then define for each lattice point $(i,j)$ its triplet thus: \begin{align*} a_{i,j} &= s(i-1,j) - c_{i-1,j}\\ b_{i,j} &= s(i-1,j-1) \\ c_{i,j} &= s(i,j-1) - a_{i,j-1}. \end{align*} It is evident that $s(i,j)$ is the number of ways to reach $(i,j)$ from $(0,0)$. Therefore we compute vertex by vertex the triplets $(a_{i,j}, b_{i,j}, c_{i,j})$ with $0 \leq i, j \leq 5$. [asy] defaultpen(fontsize(8)+0.8+heavyblue); size(250); for(int i = 0; i<6; ++i) { draw((0,i)--(5,i)^^(i,0)--(i,5), gray+0.25); } label("$(0,0,0)$", (0,0), N); for(int i = 1; i<6; ++i) { label("$(0,0,1)$", (0,i), N); label("$(1,0,0)$", (i,0), N); label("$({"+string(i-1)+"},1,0)$", (i,1), N); label("$(0,1,{"+string(i-1)+"})$", (1,i), N);} real[] val={1,2,4,7}; for(int i = 2; i<6; ++i) { label("$(1,{"+string(i-1)+"}, {"+string(val[i-2])+"})$", (2,i), N); label("$({"+string(val[i-2])+"},{"+string(i-1)+"}, 1)$", (i,2), N);} label("$(3,3,3)$", (3,3), N); label("$(9,9,9)$", (4,4), N); label("$(28,27,28)$", (5,5), N); label("$(4,5,6)$", (3,4), N); label("$(6,5,4)$", (4,3), N); label("$(5,8,11)$", (3,5), N); label("$(11,8,5)$", (5,3), N); label("$(13,15,18)$", (4,5), N); label("$(18,15,13)$", (5,4), N); [/asy] Finally, after simple but tedious calculations, we find that $(a_{5,5}, b_{5,5}, c_{5,5}) = (28,27,28)$, so $s(i,j)=28+27+28 = \boxed{083}$.

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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

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